다이나믹 프로그래밍 알고리즘 Q www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net A 점화식을 세우는 것이 중요하다. n-1, n-2번째를 생각하였을때의 점화식으로 답이 안나오면 n = 1일때부터 차근차근 생각해보자. 코드 import sys n = int(sys.stdin.readline()) d = [0] * 1001 d[1] = 1 d[2] = 2 for i in range(3, 1001): d[i] = d[i-1] + d[i-2] print(d[n] % 10007)
다이나믹 프로그래밍 알고리즘 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..
