이번 스터디 그룹 모임의 주제는 "Dynamic Programming"이다.

이 알고리즘은 굉장히 빠른 연산 속도와 새로운 사고방식을 할 수 있게 해준 고마운 알고리즘이다.

이번 글에서는 [Baekjoon Online Judge] 사이트에 있는 문제들을 풀고 스터디 그룹원들과 함께 리뷰해 보는 과정에서 배운 점들에 대해 기록해 본다.

Dynamic Programming (DP)

순차적으로 된 의사 결정의 최적화 문제를 정식화함으로써 얻어지는 문제 취급 이론 및 수법.

정의가 조금 어려운 말로 되어있는데, 개인적으로 이해한 바를 요약하자면 이렇다.

• 중간 계산 결과를 저장하여 반복되는 계산은 다시 계산하지 않고 저장된 결과를 불러와 계산 속도의 최적화를 이루는 방법

예를 들어 피보나치 수열의 n번째 수를 구하는 코드를 재귀함수와 Dynamic Programming 방식으로 각각 구현하면 아래와 같은 시간 복잡도를 갖게된다.

• 재귀: $O(2^n)$
• Dynamic Programming: $O(n)$

이렇게 큰 속도차이를 보이는 이유를 코드 진행 방식으로 보면 보다 쉽게 알 수 있는데,
우선 재귀함수로 구현한 코드를 아래와 같다.

def fib(n):
  if n == 0  or n == 1:
    return n
  else:
    return fib(n - 1) + fib(n - 2)

$n >= 2$ 일때, 코드 하단에 fib(n - 1) + fib(n - 2) 에서 fib(n - 1)이 반복되면 fib(n - 2)에 필요한 계산까지 이미 하기 때문에 결국 fib(n - 2)를 진행하면서 fib(n - 1)에서 한 같은 계산을 여러번 반복하게 되어 시간 복잡도가 $O(2^n)$에 이르게 된다.

반면, Dynamic Programming으로 구현한 코드는 아래와 같다.

def fibonacci(n):
  if n == 0 or n == 1:
    return n
  f = [0, 1]
  for i in range(2, n+1):
    num = f[i- 1] + f[i - 2] # 코드 2
    f.append(num)
  return f[n]

f라는 변수에 계산 결과를 저장하여 이미 저장된 계산 결과를 이용해 새로운 계산을 진행한다.

정리하자면,
재귀 함수는 2 이상인 $n$번째 수를 구하기 위해 1부터 $n-1$까지의 수를 계산하고 다시 1부터 $n-2$까지의 수를 계산한 후 둘을 더하여 답을 찾는 과정을 $n$번 가까이 반복한다.

Dynamic Programming의 경우는 1부터 $n$번째 수를 구하기 위해 $n$번의 계산으로 답을 바로 찾는다.

이러한 Dynamic Programming은 동적 프로그래밍, 동적 계획법으로 불리기도 한다.

문제 풀이

RGB거리 [문제 링크]

문제 요약

1번 집부터 $n$번째 집까지 순서대로 빨간색, 녹색, 파란색으로 집을 칠하는 데 각각 다른 비용이 들어간다. 직전 집과 같은 색으로 칠하지 않으면서 모든 집을 칠하는 최소 비용을 구하는 문제.

문제 풀이

1번 집부터 각각의 색을 칠하는 경우의 비용과 이전 집이 다른 색을 칠 했을 경우의 비용 누적액을 더하여 다시 누적시키며 $n$번째 집까지 각 색상을 칠하는 경우의 누적 비용 중 최솟값을 반환하면 된다.

• 1번집은 이전 집이 없으므로 각 색상 비용을 저장하고 2번 집은 빨간색을 칠할 경우의 비용은 1번 집의 파란, 녹색 중 저렴한 비용과 더해 누적시키는 방식.

결국 마지막 $n$번째 집의 각 색상별 누적액은 이전 집들이 모두 앞 집과 다른 색을 칠하면서 $n$번째 집이 각 색상을 칠하는 경우 발생하는 최소 비용이다.

그 각 색상별 최소 비용들 중에 다시 최소 비용을 고르면 모든 집을 앞 집과 다르게 칠하는 최소 비용이 되는 것.

n = int(input())
R, G, B = 0, 0, 0
for i in range(n):
  r, g, b = map(int,sys.stdin.readline().split())
  R, G, B = r+min(G,B), g+min(R,B), b+min(R,G)
print(min(R, G, B))

정수 삼각형 [문제 링크]

문제 요약

숫자 피라미드 맨 위층부터 각 층에 수 중 하나를 선택하여 가장 아래층까지 내려오면 합할 때 나올 수 있는 최댓값 구하기. 단, 아래 층 수 중에서는 대각선 왼쪽 또는 오른쪽 수 중에서만 고를 수 있다.

문제 풀이

RGB거리 문제와 마찬가지로 가장 위에서 부터 각 수를 고를 경우의 최댓값을 저장하면서 내려오면 가장 아래층의 각 수를 고를 경우마다의 최댓값이 나온다. 이 값들을 최댓값을 구하면 답.

전깃줄 [문제 링크]

문제 요약

두 전봇대 A, B에 맨 위 1번 위치부터 10번 위치까지 서로 전깃줄들 연결되어 있는데 서로 교차하는 경우의 전깃줄은 제거해야 한다. 제거해야 하는 전깃줄의 최소 개수를 구하는 문제.

문제 풀이

A 전봇대의 연결된 B 전봇대의 위치를 A 전봇대 기준 1번부터 나열한 후 나오는 B 전봇대의 각 위치 수열 중 증가하는 가장 긴 부분 수열(Longest Increasing Subsequence)의 개수를 전체 전깃줄 수에서 빼면 답.

단, LIS를 구하기 위해 DP방식을 사용하여 각 숫자마다 만들 수 있는 가장 긴 증가하는 부분 수열의 수를 저장하여 다른 숫자에서 부분 수열을 만들때 포함되는 수의 수열 계산은 생략하도록 한다.

평번한 배낭 [문제 링크]

문제 요약

넣은 수 있는 무게가 제한 된 가방에 무게와 가치가 각각 다른 물품들을 넣어 만들 수 있는 최대 가치를 구하는 문제

문제 풀이

제한되는 무게가 될 때까지 각 물건을 넣을 경우와 넣지 않을 경우의 가치를 비교하며 그 중 최대 가치가 나오는 경우를 저장하며 저장된 최대 가치와 다음 물건을 넣을 경우와 넣지 않을 경우의 가치를 비교해 나가는 방식으로 모든 물건을 차례로 비교한다.

느낀 점

DP를 알기 전까지 이런 류의 문제는 항상 지금 내가 계산해나가는 과정의 결과가 답으로 향하는 길인지 알 수 없었다. 그래서 모든 경우의 수로 계산을 전부 마치고 그 계산 결과 중 조건에 맞는 경우를 택하는 Brute Force 방식만이 최선이라고 생각했다.

이렇게 중간과정을 저장하여 계산 수 자체를 줄이는 방법.
그리고 조건에 맞게 그 계산 과정을 누적해가며 결과를 방법.
이를 통해 모든 경우의 수 중에 최적의 경우만을 추려서 적은 계산을 하여 답을 구하는 방식.

너무나도 효율적인 최적화 그 자체인 것 같다.

이러한 방식을 주어진 조건에 벗어나지 않게 구현하기 위해 생각하는 과정이 지금은 낯설고 어렵지만 익숙해지면 굉장히 효율적인 프로그래밍을 할 수 있는 나로 발전할 수 있을 것 같다.

꾸준히 이런 문제들을 접하면서 DP 사고방식에 익숙해지도록 해야겠다.