👀 'Do it! 알고리즘 코딩테스트 with Python(김종관 저)'을 공부하고 정리한 내용입니다.

1. 개념

동적 계획법은 복잡한 문제를 여러개의 간단한 문제로 분리하여 부분의 문제를 해결함으로써 최종적으로 문제의 답을 구하는 방법을 뜻합니다.

동적 계획법의 원리와 구현 방식
1. 큰 문제를 작은 문제로 나눌 수 있어야 한다.
2. 작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결괏값은 항상 같아야 한다.
3. 모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하며 추후 재사용활 때는 이 DP 테이블을 이용한다.
4. 동적 계획법은 Memoization(Top-down approach)과 Tabulation(Bottom-up) 방식이 있다.

피보나치 수열 풀이를 예로들어 이해해봅시다.

2. Memoization(Top-down approach)

메모이제이션은 부분문제를 풀었을 때 이 문제를 저장해두고 다음에 같은 문제가 나왔을때 재계산 없이 값을 이용하는 것을 말합니다. N번째를 위해 N-1과 N-2번째 피보나치 수열의 값의 필요할 때 이를 기억해두었다가 값을 추출하는 것입니다. 이러한 방식은 불필요한 연산과 탐색이 줄어들어 시간 복잡도 측면에서 이점이 있습니다.

F = {1:1, 2:1}

def fib(n):
	if n in F:
    	return F[n]  # 꺼내쓰기
    else:
    	F[n] = fib(n-1) + fib(n-2)   # 저장
        return F[n]

3. Tabulation(Bottom-up)

위에서 아래로 내려오션서 풀 수 있으면 그 반대인 아래서 올라가면서 풀 수도 있지 않을까요.
테이블을 이용한 타뷸레이션 방법은 할 수 있습니다.

재귀식으로 상향식 해법을 찾아 반복문으로 전환하는 것인데, 이렇게 하면 중복 부분 문제가 해결 됩니다.

F = {}

def fib(n):
	F[1] = f[2] = 1
    for i in range(3, n+1):
    	F[i] = f[i-1] + f[i-2]
    return F[n]

BOJ 1463 1로 만들기

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

입출력예

# N을 입력받습니다.
N = int(input())

# D 배열을 초기화합니다. 이 배열은 최소 연산 횟수를 저장할 것입니다.
D = [0] * (N + 1)

# 초기화: 1을 1로 만드는 연산 횟수는 0입니다.
D[1] = 0

# 2부터 N까지의 숫자에 대해 연산 횟수를 계산합니다.
for i in range(2, N + 1):
    # 현재 숫자를 1 빼는 연산을 수행한 경우의 연산 횟수를 저장합니다.
    D[i] = D[i - 1] + 1
    
    # 현재 숫자가 2로 나누어 떨어지면, 2로 나누는 연산을 고려하여 연산 횟수를 업데이트합니다.
    if i % 2 == 0:
        D[i] = min(D[i], D[i // 2] + 1)
    
    # 현재 숫자가 3으로 나누어 떨어지면, 3으로 나누는 연산을 고려하여 연산 횟수를 업데이트합니다.
    if i % 3 == 0:
        D[i] = min(D[i], D[i // 3] + 1)

# 결과적으로 N을 1로 만들기 위한 최소 연산 횟수를 출력합니다.
print(D[N])