이진 탐색 알고리즘 Q www.acmicpc.net/problem/18238 18238번: ZOAC 2 2019년 12월, 두 번째로 개최된 ZOAC의 오프닝을 맡은 성우는 누구보다 화려하게 ZOAC를 알리려 한다. 작년 ZOAC의 방식은 너무 식상하다고 생각한 성우는 문자열을 보여주는 새로운 규칙을 고안해 www.acmicpc.net A 이진 탐색 알고리즘을 이용하여 풀었다. 원판이 왼쪽, 오른쪽 둘다 돌 수 있다는 것만 주의하면 된다. 코드 def binary(array, target, start, end): #이진 탐색 알고리즘 while start target: end = mid - 1 else: start = mid + 1 return None array = ['A','B','C','D','E'..
다이나믹 프로그래밍 알고리즘 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] + ..
