[알고리즘 지식 공부] Dynamic Programming이란?

서론

안녕하세요. 개발자 제라스입니다~ 👋🏻🤖👋🏻

오늘은 알고리즘 문제를 풀면서 어느 누구나 한번 쯤 들어봤을 그 놈..!! DP.

이 DP 아닙니다...ㅎㅎ 죄송티비..

동적 계획법! 흔히들 Dynamic Programming(줄여서 DP~)이라고 알고 있죠?

이 친구를 한번 알아보겠습니다.

 

저도 사실 4년 전 알고리즘 공부를 잠깐 찍먹하던 시절이 있었는데요.

이때 싸지방에서 알고리즘 공부를 하면서 DP 공부가 가장 어려웠던 것 같아요.

특히 알고리즘 문제에서 어떤 부분을 보고 '아! 이건 DP로 풀어야 하는 문제구나!'를 파악할 수 있는지 감이 안 오더라구요.

 

그래서! 오늘 함께 이 DP에 대한 포스팅을 해보고자 합니다.

그럼 오늘도 긴 글 읽어주실 분들께 감사의 인사를 전하며 시작해보겠습니다!

Dynamic Programming 넌 누구냐?

사실 이름부터 간지나잖아요?

Dynamic부터가 그냥 압권이죠.

 

근데 사실 이거 이름이 1950년대에 Richard Bellman 씨가 멋지게 이름 붙이고 싶어서 붙인 이름입니다.

그냥 별 뜻이 없습니다 ㅋㅋㅋ

별 거 읎네잇~~~

그럼 진짜 이게 뭔 뜻인지 봅시다.

 

먼저 이 방식은 전체 문제를 한번에 해결하지 않고 작은 문제들로 쪼개어 해결하고, 이 해결한 것들을 활용해서 전체 문제를 해결하는 방식입니다.

 

즉,

1. 전체 문제를 작은 문제들로 쪼갤 수 있어야 한다.

2. 그 작은 문제들의 해결값을 활용하는 방식이어야 한다.

이렇게 볼 수 있습니다.

 

근데 이 2가지 방식으로 푼다고 해도 중요한 건 다음 2가지 조건을 만족하면서 풀어야 한다는 것입니다.

 

조건 1. 큰 문제를 작은 문제들로 쪼갰을 시 동일한 작은 문제들이 여러번 등장해야 한다.

 

이 조건은 무슨 말이냐면,

우리가 보통 Divide and Conquer(분할 정복) 문제를 풀 때도 마찬가지로 쪼개서 그 결과들을 합해나가면서 전체 문제의 해결방법을 구하잖아요?

근데 DP는 이 작은 문제들 중 겹치는 것들이 존재하고 그것들을 재활용해야 한다는 거에요.

 

즉, 이전에 해결한 문제들이 있으면 그걸 다시 재활용하는 방식! 이걸 우리는 메모이제이션(Memoization)이라고 합니다.

간단히 말하면 작은 문제의 해답을 구했으면 그 해답을 미리 메모해두는 거에요.(이래서 '메모'이제이션)

그러고 나중에 똑같은 문제가 나오면 그대로 쓰는 거죠.

 

그래서 우리는 이 메모이제이션을 적극 활용하는 걸 DP라고 하고요.

이걸 쓰려면 중복된 작은 문제들이 존재해야 하죠.

그래야 재사용하는 방식을 쓸 테니까요!

 

즉, '작은 문제들을 조합해서 큰 문제를 푼다.'에서 그치지 않고 '중복된 작은 문제들을 조합해서 큰 문제를 푼다'가 DP의 핵심 중 하나입니다.

 

이때 전자를 최적 부분 구조(optimal substructure, 작은 문제의 해결책의 합으로 큰 문제를 해결할 수 있는 구조)라고 하고

후자를 중복 부분 문제(overlapping subproblems, 큰 문제를 나누었을 때 작은 문제가 여러 개 반복되는 문제)라고 합니다.

 

이런 점에서 분할정복과 차이가 있다고 볼 수 있죠.

 

조건 2. 큰 문제의 해결방법은 작은 문제들의 해결방법들의 합으로 구성되어야 한다.

이건 뭐냐?

우리가 작은 문제들을 풀었어요.

근데 이것들만 가지고 큰 문제의 해결방법을 해결할 수 없고 다른 값이 또 필요하다면 이건 의미가 없는거에요.

그때마다 자꾸 예외처리나 해결을 해줘야 하니까요.

 

즉, 우리는 작은 문제 몇개를 해결해줬으면 그거를 Trigger로 다른 큰 문제들도 순차적으로 촥촥촥 해결되길 원하는 거죠.

그게 중간에 끊긴다? 문제풀기 힘들어지죠...😩😩

Dynamic Programming 문제 해결 절차

먼저 해결 절차부터 보시면

1. 문제를 해결하는 해가 이미 있다고 가정합니다.

2. 종료 조건을 설정합니다.

3. 과정 1,2를 활용해 점화식을 세웁니다.

 

몽말인지 모르겠죠... 하나씩 살펴볼게요!

 

1. 문제를 해결하는 해가 이미 있다고 가정합니다.

일단 문제를 해결하는 결과가 있다고 생각하는 겁니다.

for문이 다 돌고 나면 마지막까지 값이 채워질 거고 마지막에 나온 값을 우리는 정답이라고 부르는 겁니다.

 

2. 종료 조건을 설정합니다.

이게 언제까지나 반복되진 않겠죠?

그래서 우리는 어떨 때 종료가 된다는 것을 설정할 겁니다.

우리는 결국 정답이 나와야하니까요.

그 끝을 생각해두는 겁니다.

 

3. 과정 1,2를 활용해 점화식을 세웁니다.

솔직히 말하자면 이게 제일 중요하죠.

일단 반복되는 풀이 방식을 유추해야 하고, 더 중요한 것은 이전에 있는 값을 어떻게 활용할 지가 중요하니까요.

그래서 점화식을 세우는게 사실 가장 어렵기도 합니다.

 

그럼 점화식은 어떻게 짜야하는지 살펴봅시다.

 

점화식을 구해주세요...!

점화식 구현에는 크게 두가지 방식이 있습니다.

하나는 그냥 무작정 반복문만 쓰는 방식(재귀 활용)이고,

다른 하나는 메모이제이션을 쓰는 방식(재귀 + 메모이제이션 활용)입니다.

 

사실 메모이제이션을 쓰면 메모리를 잡아먹긴 하지만 그리 크지만 않다면 보통 막무가내 반복문 쓰는 것보다는 좋은 편입니다.

 

재귀 활용

이 경우엔 다음과 같이 팩토리얼 값을 구하는 걸 예시로 들게요.

factorial(N):
	if(N==1):
    	return 1
    else:
    	return factorial(N-1) * N

이런게 단순히 재귀를 활용한 예시에요. 쉽죠???

그럼 메모이제이션으로 풀면 뭐가 다른지 봅시다.

 

재귀 + 메모이제이션 활용

dp = [0] * N # dp라는 메모지를 미리 만들어두고,
dp[1] = 1 # N=1일 땐 1인 걸 미리 아니까 적어둡니다.

factorial(N):
	# dp 노트에 메모되어 있으면 그걸 활용하고,
	if dp[N-1] != 0:
    	return dp[N-1] * N	
	# 안 적혀있다면 재귀를 활용하는 거죠.
	else:
    	return factorial(N-1) * N

 

차이가 느껴지시나요?

미리 적어둘 배열 dp를 만들어두느냐 마느냐 차이입니다.

이렇게 하면 만약 이미 계산했던 내용이 나오면 그걸 활용하는 거죠.

 

근데!!

사실 팩토리얼은 메모이제이션을 써도 효율이 나지 않아요.

왜냐??

단 한번도 중복된 작은 문제를 해결하지 않기에 메모되어있는게 항상 없는거죠.

즉, 우리가 위에서 공부한 최적 부분 구조일 뿐 중복 부분 문제는 아니라는 겁니다.

 

이제는 차이를 아시겠나요? ㅎㅎㅎ

마무리

오늘은 동적 프로그래밍, Dynamic Programming, DP에 대해서 알아보았습니다.

어떨 때 쓰는지가 중요한데 정말 말 그대로 중복된 작은 문제로 쪼개어서 합쳤을 때 문제를 풀 수 있는 경우!

그때 DP를 쓰는 겁니다.

 

또한, 메모이제이션이 핵심인데 이걸 잘 쓰는 게 중요합니다.

이거 없으면 홍철없는 홍철팀과도 같은 거죠...

 

그럼 오늘은 이 정도까지 알아보고 다음에는 DP를 활용해서 최장 증가 부분 수열, 최장 공통 부분 수열을 풀어보도록 하겠습니다.

이 둘이 정말 대표적이고 중요한 문제거든요🙂🙂

 

그럼 오늘도 긴 글 읽어주셔셔 감사드리며 다음에는 더 좋은 포스팅으로 돌아오겠습니다.

참고

https://hongjw1938.tistory.com/47

알고리즘 - Dynamic Programming(동적 계획법)

- 코딩 테스트 합격자 되기 - 파이썬 편

---

아직 꼬꼬마 개발자입니다.

더 나은 설명이나 코드가 있다면 언제든 환영입니다.

적극적인 조언과 피드백 부탁드립니다!

 

그럼 오늘도 개발 가득한 하루되세요!

- Xerath -

🤖🤖🤖🤖🤖🤖🤖