TIL 240311

hyeo71·2024년 3월 11일

2024 내배캠 AI 트랙

목록 보기

49/108

DP(Dynamic Programming)

복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법

문제를 여러 개의 하위 문제로 나누어 각 하위 문제를 계산하고 계산한 값을 저장, 후에 같은 하위 문제가 나왔을 경우 저장된 값을 사용하여 간단하게 해결

부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 적은 시간으로 풀고 싶을 때 사용

하위 문제의 수가 기하급수적으로 증가할 때 유용

적용할 수 있는 조건

큰 문제가 여러 작은 문제로 쪼개질 수 있을 때
여러 작은 문제에 중복되는 연산이 많을 때
최적 부분 구조(Optimal Substructure)

※ 최적 부분 구조: 부분 문제의 최적 결과값을 사용해 전체 문제의 최적 결과를 낼 수 있는 구조

DP 문제 푸는 방법

하위 문제의 결과값을 변수에 저장
변수 간 점화식 만들기(ex. fibonacci - f(n)=f(n-1)+f(n-2))

Memoization

TopDown 방식
하위 문제의 해결 결과만을 저장

Tabulation

DownTop 방식
Memoization과 달리 문제에 필요하지 않아도 일단 계산하고 저장

※ 대부분의 DP 문제는 Tabulation 방식이 권장

DP vs Greedy

DP는 가능한 모든 방법을 고려해야 된다는 단점을 가지고 있다.
DP는 Greedy에 비해 시간적으로는 효율적이지 못할 수는 있지만, 결과에 대해서는 효율적인 값을 구할 수 있다.

baekjoon

2748. 피보나치 수 2

피보나치 수 2
분류: 수학, DP

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

def fib(n):
    f = [0, 1, 1]

    for i in range(3, n + 1):
        f.append(f[i - 1] + f[i - 2])

    return f[n]


n = int(input())
print(fib(n))

피보나치 점화식: f(n)=f(n-1)+f(n-2)
f 라는 리스트에 피보나치 값을 저장하여 재귀를 사용하지 않고 필요할 때 f 리스트에서 값을 가져와서 사용

9095. 1, 2, 3 더하기

1, 2, 3 더하기
분류: DP

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수

def plus_cnt(n):
    cnt_list = [0, 1, 2, 4]

    for i in range(4, n + 1):
        cnt_list.append(cnt_list[i - 1] + cnt_list[i - 2] + cnt_list[i - 3])

    return cnt_list[n]


for i in range(int(input())):
    n = int(input())
    print(plus_cnt(n))

점화식: f(n)=f(n-1)+f(n-2)+f(n-3)

1463. 1로 만들기

1로 만들기
분류: DP

정수 N이 주어졌을 때, 세 개의 연산을 사용하여 1을 만드는 연산의 최솟값

x = [0, 0, 1, 1]
n = int(input())

for i in range(4, n + 1):
    x.append(x[i - 1] + 1)
    if i % 3 == 0:
        x[i] = min(x[i // 3] + 1, x[i])
    if i % 2 == 0:
        x[i] = min(x[i // 2] + 1, x[i])


print(x[n])