최근 알고리즘 공부를 하면서 점화식의 늪에 빠져있다. (정확히는 동적 계획법)
점화식은 다이나믹 프로그래밍(Dynamic Programming, 이하 동적 계획법)에서 사용되는 방식이자 개념 중 하나인데, 보통 알고리즘 문제를 풀 때 그냥 점화식이라는 수학적 개념이 있구나 정도로만 알고 있었다.
막상 실제로 적용해보니 어떤 문제에서 동적 계획법을 적용해서 풀어야 할지 잘 감이 오지 않았다. 문제를 단순히 보면 생각나는 1차원적이면서도 단순무식한 접근법들이 떠오르는데, 이를 적용할 경우 대부분 시간초과가 발생한다.
몇 번의 삽질을 하면서 비로소 점화식에 대한 개념이 잡혔고, 왜 동적 계획법이 필요한지 피부로 체감하게 되었다.
알고리즘에 대한 기본 개념은 있는 개발자이지만, 다이나믹 프로그래밍이 무엇인지 "정확히" 모른다는 가정 하에, 하나하나 개념부터 하나하나 살펴보도록 하자.
동적 계획법은 왜 필요할까? (알고리즘은 왜 필요한걸까?)
동적 계획법이 필요한 이유는 중복 계산을 줄여서 시간 복잡도를 낮추기 위해서다.
그렇다면 왜 시간 복잡도를 낮춰야 할까? 왜 알고리즘 문제들에서는 제한된 시간 안에 풀지 못한 문제는 성공 처리가 안될까?
상식적으로 생각해보면 이상하다.
우리가 사용하고 있는 컴퓨터에서는 while 문으로 무한 루프에 빠지지 않는 이상 컴퓨터가 연산을 못 따라가는 경우가 거의 없기 때문이다.
이럴 때 알고리즘 공부의 초심을 돌이켜 볼 필요가 있다.
알고리즘이 왜 필요할까? 막말로 주먹구구식으로도 한 땀 한 땀 문제를 풀고자 하면 할 수 있다.
물론 컴퓨터의 계산은 빠르지만, 알고리즘을 풀다 보면 망각하는 사실이 있다.
컴퓨터는 '알고리즘만' 계산하는 기계가 아니다.
모든 명령어와 구동 과정에서 끊임없이 계산을 하고 있고, 그 기술이 너무나도 발전한 나머지 인간이 느끼기에 컴퓨터가 느끼는 알고리즘 계산의 '부채'가 적기 때문이다. 하지만 계산의 영역이 확대된다면 시간이 너무 많이 필요하거나 메모리 공간이 부족한 문제가 발생할 수 있다. 컴퓨터를 사용하는 환경이 너무나도 쾌적했기 때문에 이러한 버벅거림이나 기다림은 사용자에게 큰 불편함으로 다가온다.
그리고 매번 일일이 계산해서 문제를 풀어야 한다면, 우린 비슷한 유형의 문제들을 해결할 때도 너무나도 많은 시간이 걸릴 것이다.
알고리즘 풀이법은 일종의 도구라고 생각한다.
우린 인간이니, 도구를 사용함에 따라 우리의 노력을 보다 고차원적인 부분에 '효율적'으로 집중할 수 있게 된다. 우리가 매번 수학 문제지에 네모의 피라미드를 그리고 있었다면, 우리는 아직도 매일 밭을 갈고 수확하는 농경 사회에 있었을 수도 있지 않았을까? 라는 비약된 추측을 해본다.
매우 기초적인 부분이지만, 근본적인 부분이라 생각한다. 동적 계획법을 찾아볼 때 나는 위와 같은 의문을 다시 한번 가졌었다. 멍청한 질문이었지만, 납득이 안된다면 끊임없이 자신에게 물어보도록 하자.
다시 돌아와, 동적 계획법은 연산 속도의 한계, 제한된 메모리 공간, 한정적인 데이터 개수 등 여러 제약에서 효율적으로 메모리 공간을 관리하며 빠르게 연산할 수 있기 때문에 사용한다.
동적 계획법의 핵심 개념
동적 계획법은 어떻게 효율적인 메모리 관리와 빠른 연산 속도를 모두 챙길 수 있을까?
가장 핵심적인 개념은 메모이제이션(Memoization) 기법에 있다.
메모이제이션이란, 한 번 연산한 결과를 메모리 공간에 기록해 두고 같은 식을 다시 호출했을 때 메모한 결과를 그대로 가져오는 기법이다.
프론트엔드, 특히 React 사용자라면 꽤 익숙한 방식이다. 서버와의 연산을 통해 저장된 결괏값을 메모리 공간에서 미리 저장하고 가져오는 것이 매번 연산을 거쳐 랜더링하는 것보다 빠르기 때문이다.
국민 수학문제, 피보나치 수열을 통해 좀 더 자세히 알아보자.
def fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2) # 중복 계산 발생
print(fib(10)) # 55
해당 파이썬 코드는 단순 재귀 방식을 구현한 코드다.
함수를 호출하여 n이 1이 아니라면 반복적으로 같은 함수를 구하고 또 구하는 방식으로, 같은 값을 여러 번 계산해야 한다. 예를 들어, fib(10)을 계산하려면 fib(9), fib(8), ..., fib(1)와 같은 방식으로 여러 번 호출해야 한다. 입력이 커질수록 연산량도 기하급수적으로 증가하고, 반복 호출이기 때문에 O(n2) 복잡도를 가지고 있다. 대충 더럽게 오래 걸린다는 뜻
이때 다음과 같이 메모이제이션 기법을 적용할 수 있다.
memo = {}
def fib(n):
if n <= 1:
return n
if n in memo:
return memo[n] # 저장된 값 사용
memo[n] = fib(n-1) + fib(n-2)
return memo[n]
print(fib(10)) # 55
위 방법을 통해 memo 딕셔너리를 사용하여 한 번 계산한 값은 저장하여 재사용이 가능하게 된다. 중복 계산이 사라졌기 때문에 시간 복잡도도 O(N)으로 감소해 이전에 비해 더욱 빠른 연산 속도를 가졌다.
간단한 코드 몇 줄 추가로 이중 루프에서 단일 루프로 바뀌었다.
fib(30)을 구한다고 했을 때, 약 10억 회의 연산을 30회의 연산으로 줄여버린 것이다. 만약 입력값 n이 1000이라고 한다면 1000배 이상의 효율 차이가 발생한다. 10억 개의 네모 피라미드... 상상만 해도 끔찍하지 않은가? 컴퓨터도 이런 연산은 버거워한다.
그래서 점화식이 뭔데?
사실 우리는 앞선 예시에서 이미 점화식을 적용했다.
점화식(Recurrence Relation, 漸化式)이란, 수열에서 이웃하는 두 개의 항 사이에 성립하는 관계를 나타낸 관계식을 의미한다.
처음 이 설명을 봤을 때 이해가 잘 안 됐다. 말 그대로 점진적(漸)으로 변화(化)하는 공식이라는 뜻으로, 쉽게 설명하자면 작은 값에서 점점 커지는 패턴을 따라가면서 값을 구하는 식을 의미한다. 이때, 패턴이란 점차적으로 변해가는 양상을 의미한다고 볼 수 있다.
작은 값에서 점점 커지는 패턴, 즉 피보나치 수열에서 사용했던 것과 같이 재귀적으로(순차적으로) 값을 구하는 과정과 같다.
점화식에서의 한자는 불이 붙는다는 뜻의 '점화'와는 다르지만, 비슷한 흐름으로 이해해도 괜찮다. 작은 값에서 시작해서 점점 커지는 연산 구조가 불이 차례대로 옮겨붙듯이 퍼지는 과정과 유사하기 때문이다.
점화식이 중요한 이유는 문제의 큰 흐름을 작게 나눌 수 있기 때문이다. 즉, 큰 문제를 작은 문제로 나눌 수 있다.
앞선 피보나치 수열의 예시를 따라가보자.
fib(10) → fib(9) + fib(8)
fib(9) → fib(8) + fib(7)
fib(8) → fib(7) + fib(6)
...
fib(10)은 fib(9) + fib(8)로, fib(9)는 다시 fib(8)+fib(7)로 나뉜다. 이 과정이 반복되면 결국 수많은 fib(1)로 이루어진 식들의 조합이 되고, fib(10)은 총 몇 개의 fib(1) 또는 fib(2)로 이루어져 있는가로 볼 수 있다.
동시에 한 가지 패턴을 더 인식할 수 있다.
작은 문제에서 구한 정답들(fib(1), fib(2)는 작은 문제를 포함한 큰 문제에서도 동일하게 적용할 수 있다. 이는 곧 하나의 "패턴"으로 볼 수 있다.
수학적 개념이라 추상적이지만, 결국 우리는 '언제 점화식이 적용가능한지'에 초점을 두어야 한다.
반복되는 패턴으로 증가하는 수의 관계가 보인다면 점화식이 적용될 수 있다는 뜻이고, 이는 곧 동적 계획법이 적용 가능하다는 말과 같기 때문이다.
Top-Down 방식 vs Bottom-Up 방식
동적 계획법을 코드로 구현할 때 가능한 방법은 두 가지가 있다.
재귀 호출과 Memoization 기법을 적용한 Top-Down 방식과 반복문으로 작은 값부터 계산하고 DP 테이블에 저장하는 Bottom-Up 방식이 있다.
피보나치 수열 예시를 통해 계속해서 알아보자.
memo = {} # 메모이제이션을 위한 딕셔너리
def fib(n):
if n <= 1:
return n
if n in memo: # 이미 계산한 값이면 바로 반환
return memo[n]
memo[n] = fib(n - 1) + fib(n - 2) # 계산 후 저장
return memo[n]
print(fib(10)) # 55
앞서 사용했던 예시와 같은 코드로, Top-Bottom 방식을 적용했다.
위 코드에서는 재귀(Recursion) 기반으로 문제를 쪼개서 해결하고, 중복 계산을 피하기 위해 Memoization 기법을 사용했다.
def fib(n):
dp = [0] * (n + 1) # DP 테이블
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2] # 점화식 적용
return dp[n]
print(fib(10)) # 55
위 코드는 Bottom-Up 방식의 예시다.
Top-Bottom 방식과 달리, 메모리가 미리 할당된 DP 테이블을 생성하고, 계산 가능한 모든 경우에 대한 값을 테이블에 채워 넣는다.
접근법에서 중요한 차이가 있는데, Top-Bottom 방식은 "큰 문제를 작은 문제로 나누는 방식"이고, Bottom-Up 방식은 "작은 문제를 먼저 해결하고, 이를 바탕으로 큰 문제를 해결하는 방식"이다.
또한, Top-Bottom 방식은 함수 호출이 많아서 스택 오버플로우 위험이 있다. 하지만 필요할 때만 계산하기 때문에 Bottom-Up 방식처럼 모든 경우를 계산할 필요가 없다. 즉, Bottom-Up 방식에 비해 약간의 리스크가 있지만, 작은 문제를 필요할 때만 계산하는 경우에는 Top-Down 방식이 더 유리하다.
반대로 말하면 계산해야 할 수 n이 크고 연산량이 많다면 (즉, 재귀 호출이 많고 스택 오버플로우 위험이 있다면) Bottom-Up 방식이 더 적절하다. 실제로 알고리즘 문제를 풀 때는 Bottom-Up 방식으로 더 자주 접근하는 것 같다.
Bottom-Up 방식 적용해 보기
대표적인 문제 중 하나인 '1로 만들기' 문제를 풀어보자.
정수 N이 주어졌을 때, 다음과 같은 연산을 할 수 있다.
- X가 3으로 나누어 떨어지면, 3으로 나눈다.
- X가 2로 나누어 떨어지면, 2로 나눈다.
- 1을 뺀다.
정수 N을 1로 만들기 위한 연산을 사용하는 횟수의 최솟값을 출력하는 프로그램을 구현해야 한다.
세 가지 조건이 주어졌고, 수의 관계성이 보이는 것 같다. 이때, n에서 시작하는 경우의 수를 비교하자면 다음과 같이 점화식을 구성할 수 있다.
# +1을 해야 연산 횟수가 한 번 더 적용된 것을 알 수 있음
dp[n] = min(dp[n-1] + 1, dp[n//2] + 1, dp[n//3] + 1)
이 점화식을 토대로 Bottom-Up 방식으로 접근하여 코드를 작성해 보자. 단, 2 또는 3으로 나누어 떨어졌을 때 비교를 해야 하기 때문에 코드적으로 접근할 때는 비교 방식을 좀 더 세분화해야 한다.
x = int(input()) # 입력값 (x를 1로 만들기)
dp = [0] * (x + 1) # DP 테이블 (최소 연산 횟수를 저장할 리스트)
for i in range(2, x + 1): # 2부터 x까지 반복
dp[i] = dp[i - 1] + 1 # (1을 빼는 연산) 기본적으로 i-1에서 +1 연산
if i % 2 == 0: # (2로 나누어 떨어질 때)
dp[i] = min(dp[i], dp[i // 2] + 1) # i//2에서 오는 경우와 비교하여 최소값 선택
if i % 3 == 0: # (3으로 나누어 떨어질 때)
dp[i] = min(dp[i], dp[i // 3] + 1) # i//3에서 오는 경우와 비교하여 최소값 선택
print(dp[x]) # 결과 출력 (x를 1로 만드는 최소 연산 횟수)
이때, DP 테이블 구성을 보면 다음과 같이 될 것이다.
| 1 | 초기값 | 0 |
| 2 | dp[1] + 1 = 1 (1을 뺌) | 1 |
| 3 | dp[2] + 1 = 2, dp[1] + 1 = 1 (3으로 나눔) | 1 |
| 4 | dp[3] + 1 = 2, dp[2] + 1 = 2 (2로 나눔) | 2 |
| 5 | dp[4] + 1 = 3 | 3 |
| 6 | dp[5] + 1 = 4, dp[3] + 1 = 2, dp[2] + 1 = 2 (3으로 나눔) | 2 |
| 7 | dp[6] + 1 = 3 | 3 |
| 8 | dp[7] + 1 = 4, dp[4] + 1 = 3 (2로 나눔) | 3 |
| 9 | dp[8] + 1 = 4, dp[3] + 1 = 2 (3으로 나눔) | 2 |
| 10 | dp[9] + 1 = 3, dp[5] + 1 = 4 (2로 나눔) | 3 |
이렇게 하면 10의 경우에 10 → 9 → 3 → 1로 3번 만에 만들 수 있다.
참조
- Dynamic Programming or DP
- DP recurrence relationship help
- Dissecting Dynamic Programming - Top Down & Bottom Up
- Dynamic Programming Algorithms
- 점화식 - 위키백과
- Recurrence Relation - Wikipedia
'개발자 일기 > 알고리즘 공부' 카테고리의 다른 글
| [Python]백준#28702-FizzBuzz (0) | 2025.02.05 |
|---|---|
| [프로그래머스 JS] 숫자 짝꿍 (2) | 2023.10.14 |
| [프로그래머스 JS] 삼총사 (0) | 2023.09.29 |
| [프로그래머스 JS] 콜라 문제 (2) | 2023.09.25 |
| [프로그래머스 JS] 옹알이 (2) (0) | 2023.08.22 |
댓글