안녕하세요. 한국기술교육대학교 알고리즘 소모임 씨앗
23년도 회장 은재민입니다.
오늘부터 3주동안 씨앗 활동 내용을 업로드할 예정입니다.

중간고사가 끝난 후에 나머지 4,5,6주차 활동을 진행하고 업로드하겠습니다.

씨앗은 알고리즘 소모임으로,
주 마다 하나의 주제를 선정하고 강의를 진행합니다.
강의 후엔 주제에 맞는 예제를 풀어보고 연구하는 시간을 갖습니다.

DP란 무엇인가?

1주차 주제는 Dynamic Programming, DP입니다.
동적 계획법이라고도 합니다.

전혀 dynamic하지 않지만, 처음으로 고안하신 교수님이 연구비를 받기 위해
멋있는 이름을 붙이다보니 dynamic programming이라고 지었다고 합니다.

어쨌든 DP란, 하나의 큰 문제를 작은 문제들로 나눠서 차례차례 해결하며
문제의 최종해에 도달하는 방법을 말합니다. 한번에 이해가 가시나요?

아직 이해가 잘 가지 않을 것 같습니다.
피보나치 함수를 예로 들어보죠.

피보나치 수열의 20번째 항을 구하려면 어떻게 해야할까요?

피보나치 수열의 정의에 따라
fibonacci(20) = fibonacci(19) + fibonacci(18)
fibonacci(19) = ...
fibonacci(18) = ...
...
fibonacci(2) = fibonacci(1) + fibonacci(0)   까지 도달해야합니다.
우리가 현재 아는 값은 0번쨰, 1번째 항 뿐이기 때문이죠.

흔히 이 과정을 프로그래밍하는데 재귀함수를 사용합니다.

하지만 이 과정에서 같은 값을 너무나 많이 호출하게 됩니다.
fibonacci(0)이 호출되는 횟수는 지수함수의 형태로 증가하죠.

즉, 시간효율성이 굉장히 떨어집니다. 시간복잡도 : O(2의 n제곱)

그렇기에 또다른 방법을 제시할 수 있습니다.

0번째 항부터 값을 저장해가면서 20번째 항까지 다가가는 것이죠.

fibo(0) = 1
fibo(1) = 1
fibo(2) = fibo(1) + fibo(0) = 2
. . .
fibo(19) = fibo(18) + fibo(17) = 4181 + 2584
fibo(20) = fibo(19) + fibo(18) = 6765 + 4181 = 10946

이번엔 어떤가요? 시간복잡도를 공부하신 분들이라면
이 프로그램에 시간복잡도가 O(n)이라는 것을 아실 수 있을겁니다.
중복되는 값들을 저장해 놓고 호출하는 방법으로 해결했기 때문입니다.

이와 같은 방법의 핵심은 목표에 도달하는데 필요한 작은 답들을 구하고 저장함으로서,
같은 계산을 반복하지 않고 호출해서 사용하는 것입니다.
이것을 메모지에이션(memoziation)이라고 부르고
메모지에이션을 사용하는 알고리즘 설계를 DP라고 하는 것입니다.

따라서, DP를 사용하여 해결하는 문제들은 2가지 특징을 가지고 있습니다.

첫째, 최종해를 구하기 위해 그 아래에 작은 문제들을 풀어야 하는 경우

쉽게 생각해서 n번째 항을 f(n)이라고 할 때 점화식의 형태를 띄는 경우를 말합니다.
피보나치 함수의 정의가 f(n) = f(n-1) + f(n-2) 인 것처럼 말이죠.

둘째, 작은 문제들의 답이 계속해서 필요한 경우

바로 이 부분을 해결하기 위해 메모지에이션을 사용하는 것입니다.

해결방법

우리는 문제를 풀 떄, 문제의 최적해를 어떻게 구할 지에 대해 고민합니다.

수학 계산식의 형태를 띈다면 수학 문제가 되는 것이고
최적 부분 구조와 탐욕적 선택속성을 만족한다면 그리디,
탐색이 필요하다면 선형이냐 비선형이냐..등등

일정한 사고과정을 통해 적절한 해결법을 선택하는 것입니다.

DP의 경우엔 점화식이 가장 중요한 포인트입니다.
점화식을 도출해야만 프로그램을 구현할 수 있고
무엇보다 점화식이 존재한다는 것을 눈치채야만 DP를 적용할 생각을 하게 되기 때문이죠.

점화식을 도출했고, DP를 택했다면, 그 다음은 구현입니다.
아래 코드를 보겠습니다.

N = int(input())
# 1. 배열을 하나 만들기
DP = [0] * (N + 1)
# 2. 초기값 넣기
DP[0] = 0
DP[1] = 1
# 3. 답을 구할 때까지 반복!
for i in range(2,N + 1):
    DP[i] = DP[i-1] + DP[i-2] : continue
# 4. 결과출력
print(DP[N])

DP방식으로 구현한 피보나치 N번째 항을 구하는 프로그램입니다.
점화식을 사용하는 게 보이시나요?

코드를 하나씩 살펴보죠.
입출력은 당연한거고, 초기값 대입도 피보나치의 정의에 의해 꼭 필요한 과정입니다.
특이점이 있다면 코드의 1, 3번이 되겠네요.

첫번째, 메모지에이션의 구현

코드에서 1.배열 만들기 는
메모지에이션을 위한 자료구조 선택입니다. 어떻게 저장할 것인지 선택하는 것이죠.
이 코드에서는 1차원 리스트를 사용하지만
자료의 수, 성격에 따라 적합한 자료구조는 달라집니다.

두번째, 구현 방식의 선택

3번. 반복문은 최종해에 도달하기 위해 입력된 N까지 반복하는 과정입니다.
이 문제에서는 반복문을 통해 0부터 N번째 항까지 구하도록 구현하였지만
문제 형태에 따라 N번쨰 항부터 0번쨰 항까지 접근하기도 하고, 재귀호출을 사용하기도 합니다.

이렇게 접근 방향에 따른 구현방식을 탑-다운, 바텀-업, 2가지로 분류합니다.

top-down : 큰 쪽에서 작은 쪽으로 접근
bottom-up : 작은 쪽에서 큰 쪽으로 접근
( 탑다운, 바텀업에 대한 자세한 내용은 구글로! )

끝으로

이 글을 잘 읽어보신 분들이나 공부해보신 분들은 아시겠지만,
DP는 알고리즘 계획법이라기보단
하나의 문제 해결 개념에 가깝습니다. 정해진 방식은 거의 없고
메모지에이션 이라는 개념을 적용시키는 것 뿐입니다.

점화식을 도출하고 적절한 방식으로 프로그램을 구현할 수 있다면
기본적인 DP문제들은 어렵지 않게 해결하실 수 있을 것 같습니다.

아래 예제들은 DP로 해결할 수 있는 예제들입니다.
큰 어려움 없이 해결할 수 있는 문제들이니 꼭 풀어보시면 좋겠습니다. 감사합니다!
(모든 해설은 작성자 본인이 작성했습니다. 오해없으시길 바랍니다.)

예제

난이도 下

백준 1003번 : 피보나치 함수

백준 10844번 : 쉬운 계단 수
10844번 파이썬 해설 : 링크

백준 9461번 : 파도반 수열

난이도 中

백준 2011번 : 암호코드
2011번 파이썬 해설 : 링크

백준 2225번 : 합분해
2225번 파이썬 해설 : 링크

난이도 上

백준 2629번 : 양팔저울
2629번 파이썬 해설 : 링크

백준 1256번 : 사전
1256번 파이썬 해설 : 링크