다이나믹 프로그래밍 알고리즘 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 테이블을 두개 만들어서 문제를 해결했다. 코..
