코딩테스트10 [알고리즘] 최단경로 - 다익스트라 알고리즘 (Dijkstra's algorithm) 동빈나님의 이코테 강의를 보고 제 생각을 더해 정리해 보았습니다. 풀이 언어는 파이썬을 사용했습니다. 목차 최단 경로 문제 다익스트라 알고리즘 우선순위 큐를 사용한 다익스트라 알고리즘 최단 경로 문제 최단 경로 문제 중 한 시작점으로 부터 다른 노드 까지 가는데 비용이 얼마나 걸리는 지를 구할 때 사용하는 알고리즘이 다익스트라 알고리즘 입니다. 기본적으로 최단 경로 문제는 방향이 있고 가중치가 있는 그래프가 주어집니다. 따라서 위의 그래프는 다음과 같이 입력을 받습니다. 6 11 1 1 2 2 1 3 5 1 4 1 2 3 3 2 4 2 3 2 3 3 6 5 4 3 3 4 5 1 5 3 1 5 6 2 코드에선 다음과 같은 2차원 배열로 구현 됩니다. [[], [(2, 2), (3, 5), (4, 1)], .. 2021. 3. 10. [백준] 14501: 퇴사 파이썬 리뷰 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 풀이는 해당 블로그를 참고했습니다. dp 계산을 N부터 시작하는 방법을 사용해야 했습니다. 뒤에서 부터 계산을 해보면 다른 동적 계획법과 풀이 방법은 비슷합니다. 파이썬 코드 import sys readline = sys.stdin.readline N = int(readline()) T, P = [], [] for _ in range(N): t, p = map(int, readline().split()) T.append(t) P.append(p) d = [0] * (N+1) for i in range(N - 1, -1, -1): # i일에 상담을 하는 것이 퇴사일을 넘기면 상담을 하지 않음 if i .. 2021. 2. 14. [백준] 2133: 타일 채우기 파이썬 리뷰 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 풀이는 블로그 1, 블로그 2 를 참고했습니다. d(i-4) * 2 + ... + d(0) * 2 부분이 이해하기 힘들었습니다. 점화식은 역시 그려봐야 이해가 됩니다... 파이썬 코드 N = int(input()) d = [0]*31 d[0] = 1 for i in range(2, N+1, 2): d[i] = d[i-2] * 3 for j in range(0, i-2, 2): d[i] += d[j] * 2 print(d[N]) 2021. 2. 13. [백준] 10844: 쉬운 계단 수 파이썬 리뷰 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 방법은 해당 블로그를 참조하자 dp 테이블을 각 자리수 마다 한줄 씩 2차원 배열로 설정한다. (행 : 자릿 수, 열 : 0~9) 테이블에는 해당 숫자가 맨 앞에 있을 때 가능한 경우의 수를 저장한다. 예를 들어, dp[2][1]에는 백의 자리 숫자가 1인 경우의 수가 저장돼있다. 101, 121, 123 dp[2][1]을 저장했을 때를 생각해보자, dp[1][0]과 dp[1][2]를 더한 값이 dp[2][1]에 저장된다. 맨 앞의 숫자가 1이라면 그 뒤에 올 수 있는 숫자는 당연히 0 또는 2이다. 2이 맨 앞에 있을 때 경우의 수는 dp[1][2]에 저장 돼 있다. 0.. 2021. 2. 4. 이전 1 2 3 다음
