알고리즘7 [백준 11779번] 최소비용 구하기 2 (Python) 해당 문제를 풀기 위해 다익스트라 개념에 대해 먼저 알고 있어야한다. 2024.03.28 - [CS/Algorithm] - [알고리즘 개념 정리] 다익스트라 최단 경로 알고리즘 (Python) 또한 해당 문제의 1단계인 최소비용 구하기를 풀고 풀면 좋을 것 같다. 이전 문제 풀이 : [백준 1916번] 최소비용 구하기 문제 링크 [백준 11779번] 최소비용 구하기 2 문제 요약 N개의 도시가 있고, 한 도시에서 출발해 다른 도시에 도착에 도착하는 M개의 버스가 있다. A번째 도시에서 B번째 도시까지 가는데 드는 최소 비용과 경로 출력하기 (도시의 개수 1 2024. 3. 30. [백준 1916번] 최소비용 구하기 (Python) 해당 문제를 풀기 위해 다익스트라 개념에 대해 먼저 알고 있어야한다. 2024.03.28 - [CS/Algorithm] - [알고리즘 개념 정리] 다익스트라 최단 경로 알고리즘 (Python) 문제 링크 [백준 1916번] 최소비용 구하기 문제 요약 N개의 도시가 있고, 한 도시에서 출발해 다른 도시에 도착에 도착하는 M개의 버스가 있다. A번째 도시에서 B번째 도시까지 가는데 드는 최소 비용을 출력하기 (도시의 개수 1 2024. 3. 29. [백준 2293번] 동전 1 (Python) 문제 링크 [백준 2293번] 동전 1 문제 요약 n가지 종류의 동전으로 합이 k원이 되는 경우의 수 구하기 접근 방법 정리 DP를 풀 때 중요하다고 강조했던 2가지를 생각해서 접근한다. 1. 큰 문제를 작은 문제로 나눠 작은 문제의 합으로 풀 수 있는지를 고민해야하고 2. 동일한 작은 문제를 반복적으로 해결할 수 있는지 고민 1번에 해당하는 것은 합이 k원을 구하는 큰 문제에서 각 금액을 만들 수 있는 경우의 수를 차례대로 계산해나가는 것이다. 2번에 해당하는 것은 1번으로 구해놓은 정보를 바탕으로 반복문을 수행해 DP 배열을 업데이트 한다. 코드 n, k = map(int, input().split()) nums = [int(input()) for _ in range(n)] dp = [0 for i .. 2024. 3. 27. [알고리즘 개념 정리] 다이나믹 프로그래밍 (Python) [이것이 코딩 테스트다 with Python] 28강 다이나믹 프로그래밍 개요를 듣고 정리한 내용입니다. 다이나믹 프로그래밍 (= 동적 계획법) - 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다. - 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. 메모이제이션 : 한번 계산한 결과를 메모리 공간에 메모하는 기법이다. 즉, 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다. 값을 기록해 놓는다는 점에서 캐싱이라고도 한다. - 다이나믹 프로그래밍의 구현은 일반적으로 2가지 방식(top-down과 bottom-up)으로 구성된다. top-down(메모이제이션) 방식 (=하향식): 재귀함수를 이용함 bottom-up 방식 (=상향식): 반복문을.. 2024. 3. 27. [백준 11404번] 플로이드 (Python) 2024.03.25 - [CS/Algorithm] - [알고리즘 개념 정리] 플로이드 워셜 (Python) 플로이드 워셜을 학습한 뒤 풀은 플로이드 워셜을 활용하는 문제를 풀었다 🐥 문제 링크 [백준 11404번] 플로이드 문제 요약 도시들 사이의 최단 거리를 구하는 문제로, 도시 간 이동 비용을 최소화하는 것이 목표 첫번째 줄에 도시의 개수 n이 주어진다 (2 2024. 3. 26. [알고리즘 개념 정리] 플로이드 워셜 (Python) [이것이 코딩 테스트다 with Python] 31강 플로이드 워셜 알고리즘을 듣고 정리한 내용입니다. 플로이드 워셜 알고리즘 - 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산하는 알고리즘이다. - (다익스트라 알고리즘과 마찬가지로) 단계별로 거쳐가는 노드를 기준으로 알고리즘을 수행한다. 다만, 다익스트라 알고리즘과 달리 매 단계마다 방문하지 않은 노드 중에 최단거리를 갖는 노드를 찾는 과정이 필요하지 않다. - 2차원 테이블에 최단거리 정보를 저장한다. - 다이나믹 프로그래밍 유형에 속하며, 시간 복잡도는 O(n³)이다. - 노드의 갯수가 적은 경우에 사용이 적합하며, 노드와 간선의 갯수가 많은 경우에는 다익스트라 알고리즘을 활용해야하는 경우가 많다. 실제로도 .. 2024. 3. 25. 이전 1 2 다음
