다이나믹 프로그래밍 알고리즘 Q www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net A 다이나믹 프로그래밍을 이용하여 풀었으며, 점화식을 만드는데 애먹었다. 코드 import sys n = int(sys.stdin.readline()) array = list(int(sys.stdin.readline()) for _ in range(n)) d = [0] * 11 #DP 테이블 초기화 d[1] = 1 d[2] = 2 d[3] = 4 for i in range(4, 11): #범위가 중요!! n이 아니라 11까지 d[i] = d[i-1] + d[i-2] + d[i-..
다이나믹 프로그래밍 알고리즘 Q www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net A 다이나믹 프로그래밍을 이용하여 풀었다. 주의할 점은 DP 테이블의 크기를 입력받는 n으로 설정하지 말고 n의 최대 크기를 보고 정수로 설정하자. 코드 import sys n = int(sys.stdin.readline()) d = [0] * (10**6 + 1) #DP 테이블 초기화 d[1] = 0 d[2] = 1 d[3] = 1 for i in range(4, n + 1): d[i] = d[i-1] + 1 #-1을 뺀 경우 if i % 2 == 0: d[i] = min(d[i//2] + ..
정렬 알고리즘 Q www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net A sorted()를 사용했다. 주의할 점은 길이순으로 한번 정렬하고 사전순으로 한번 더 정렬해야 한다. 코드 import sys n = int(sys.stdin.readline().rstrip()) #단어의 갯수 N 입력 array = [0] * n for i in range(n): array[i] = sys.stdin.readline().rstrip() #단어들 입력 a = se..
다이나믹 프로그래밍 Q www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net A 다이나믹 프로그래밍을 이용할 경우, 규칙을 찾는 것이 중요하다. 밑에 메모리 초과한 코드를 보면, 그냥 DP 테이블 초기화한 다음 거기에 다 저장하려 했어서 메모리 초과가 일어났다. 그리고 중요한 점은 N은 40보다 작은 자연수 또는 0 이라는 점이다. DP 테이블을 n + 1 의 크기로 만드는 것이 아니라 41의 크기로 만들어야 하며, 점화식을 위한 반복문 또한 마찬가지이다. 0과 1의 갯수가 각각 피보나치 수열을 따르고 있으므로 DP 테이블을 두개 만들어서 문제를 해결했다. 코..
최단 경로 알고리즘 Q www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net A 플로이드 워셜 알고리즘을 이용하여 풀었다. 코드 INF = int(1e9) n, m = map(int, input().split()) graph = [[INF] * (n + 1) for _ in range(n + 1)] for a in range(n + 1): for b in range(n + 1): if a == b: graph[a][..
최단 경로(Shortest Path) 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 여러 유형이 있는데, 그 중 다익스트라 알고리즘과 플로이드 워셜 알고리즘을 공부하겠다. 1. 다익스트라 알고리즘 (1) 이론 다익스트라(Dijkstra) 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구하는 알고리즘이다. '음의 간선'이 없을 때 정상적으로 동작한다. 동작원리는 다음과 같다. 1) 출발 노드를 설정한다. 2) 최단 거리 테이블을 초기화한다. 3) 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. 4) 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다. 5) 3, 4번을 ..