동적계획법과 분할정복 기본개념

2022-02-13

Coding_test_training(20220213)

[학습자료]

패스트 캠퍼스 “알고리즘 / 기술면접 완전 정복 올인원 패키지 Online.” 강의를 공부하고 정리한 내용입니다.

** URL : https://fastcampus.co.kr/dev_online_algo

[학습내용]

동적계획법 = Dynamic Programming

(1) 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 답을 활용해서 보다 큰 크기의 부분 문제를 해결하여 최종적으로 전체 문제를 해결하는 알고리즘

(2) 상향식 접근법으로, 가장 최하위 해답을 구한 후, 이를 저장하고, 해당 결과값을 이용해서 상위 문제를 풀어가는 방식

(3) Memoization 기법을 사용함

Memoization 이란 프로그램을 실행할때 이전에 계산한 값을 저장하여, 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기법

(4) 문제를 잘게 쪼갤 때, 부분 문제는 중복되어, 재활용됨 예시) 피보나치 수열

(5) 한마디로 정의하면 큰문제가 있으면 큰문제를 잘개 쪼개서 그 잘개 쪼갠 문제들을 해결한 다음에 그 작은문제의 결과값을 가지고 큰 문제를 해결하는 방식이다. 작은문제의 결과값들이 중요한데 이 결과값을 동적계획법에서는 Memoization 기법을 이용해서 저장을 한다. 큰 문제를 해결하기 위해 여러개의 작은문제들로 나누었는데 이 작은 문제를 해결한 값을 상위문제에서 바로 사용하면 되는데 만약에 상위문제 전에 중간크기 정도 되는 문제가 예를 들어서 두개가 있는데 이게 이 작은 문제의 답을 사용한다고 하면 계산을 두번해야하기 때문에 일부러 그러지 않으려고 저장하는 것이다.

분할정복 = Divide and Conquer

(1) 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘

(2) 하양식 접근법으로, 상위의 해답을 구하기 위해, 아래로 내려가면서 하위의 해답을 구하는 방식으로 일반적으로 재귀함수로 구현한다.

(3) 문제를 잘게 쪼갤 때, 부분 문제는 서로 중복되지 않음 예시) 병합 정렬, 퀵 정렬 등

동적계획법과 분할정복의 공통점 : 문제를 잘게 쪼개서, 가장 작은 단위로 분할하는 방식
동적계획법과 분할정복의 차이점

(1) 동적 계획법

부분 문제는 중복되어, 상위 문제 해결 시 재활용됨

Memoization 기법 사용 (부분 문제의 해답을 저장해서 재활용하는 최적화 기법으로 사용)

(2) 분할 정복

부분 문제는 서로 중복되지 않음

Memoization 기법 사용 안함

동적계획법의 대표예시 : 피보나치 수열

아래와 같은 수열이 피보나치 수열이다.

n = 0 이면 0

n = 1 이면 1

n이 1보다 크면 F(n-1) + F(n-2)

ex) 
F(0) = 0
F(1) = 1
F(2) = 1
F(3) = 2
F(4) = 3
F(5) = 5
F(6) = 8
F(7) = 13

...

이 피보나치 수열이 왜 동적계획법이냐면 예를 들어서 F(6)을 구하기 위해서 F(4)의 답과 F(5)의 답을 더해야 하기 때문이다. F(4)을 구하기 위해서는 F(2)의 정답과 F(3)의 정답을 또 더해야 한다.

따라서 피보나치 수열을 해결하기 위해서는 F(0), F(1) 등 작은 문제들로 쪼개야 하고 이 작은 문제들을 사용하는 중간 크기의 문제들도 다수가 있고, 이 작은 문제를 풀어야 중간 문제를 풀 수 있고, 이 중간 문제를 풀어야 상위문제를 풀 수 있다.

동적계획법 문제를 풀때는 위에 “n이 1보다 크면 F(n-1) + F(n-2)”와 같이 이웃하는 두개의 항 사이에 성립하는 관계식인 점화식을 빠르게 찾아야 한다는 것이다.

이거를 동적계획법으로 실제 코드로 구현하면 아래와 같다.

def fibo_dp(num):
    cache = [ 0 for index in range(num + 1)] ## STEP 1) 빈껍데기 리스트 만들기 : memorization 기법 적용
    cache[0] = 0 ## STEP 2) 초기값 설정하기
    cache[1] = 1
    
    for index in range(2, num + 1): ## STEP 3) 점화식 구현하기
        cache[index] = cache[index - 1] + cache[index - 2]
    return cache[num]

fibo(10)

만약에 재귀용법으로 피보나치 수열을 푼다고 하면 아래와 같이 코드를 구현하면 된다.

동적계획법과 다르게 재귀용법으로 피보나치 수열을 풀게 되면 재귀용법 특성상 수열의 크기가 커질수록 메모리 스텍이 엄청나게 필요할 것이다. 이런 비효율성이 있다.

def fibo(num):
    if num <= 1:
        return num
    return fibo(num - 1) + fibo(num - 2)

fibo(10)

 quick sort 기본개념 GCP IAM 및 Role 정보를 추출하는 python 스크립트 예시 