이코테 2021 - 동적 계획법 (Dynamic Programming)

Dynamic Programming

 

: 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법

> 쉽게 말하면, 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다.

 

다이나믹 프로그래밍은 일반적으로 두가지 방식으로 구현할 수 있다.

: 탑다운방식(위 → 아래), 보텀업 방식 (아래 → 위)

 

조건

1) 최적 부분 구조 (Optimal Substructure)

   : 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있음

 

2) 중복되는 부분 문제 (Overlapping Subproblem)

  : 동일한 작은 문제를 반복적으로 해결

 

 

 

Dynamic : 동적 - 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당

DP알고리즘의 대표적인 예시 : 피보나치 수열

단순 재귀 코드로 만들면

def fibo(x):
	if x == 1 or x == 2:
    	return 1
    return fibo(x)

fibo(4)

> 이와 같이 만들 수 있다.

 

그러나 이렇게 만들면 아래와 같은 문제를 야기할 수 있다.

하위 함수들이 계속 반복해서 중복되고 있다.

 

1) 탑다운 다이나믹 프로그래밍 소스코드

d= [0] * 100

def fibo(x):
	if x==1 or x==2:
    	return 1
        
    if d[x] != 0:
    	return d[x]
    
    d[x] = fibo(x-1) + fibo(x-2)
    return d[x]

fibo(99)

 

 

 

2) 보텀업 다이나믹 프로그래밍 소스코드

d= [0] * 100

d[1]= 1
d[2]= 1
n= 99

for i in range(3, n+1):
    d[i] = d[i-1] +d[i-2]

d[n]

 

 

이렇게 DP 방식을 사용하면 아래와 같은 구조로 동작하여 중복을 없앨 수 있다.

 

 

 

 

적용

 

"""
7[0,0]
    +3[1,0]
        +8[2,0]
            +2[3,0]
                +4[4,0]
                +5[4,1]
            +7[3,1]
                +5[4,1]
                +2[4,2]
        +1[2,1]
            +7[3,1]
                +5[4,1]
                +2[4,2]
            +4[3,2]
                +2[4,2]
                +6[4,3]
    +8[1,1]
        +1[2,1]
            +7[3,1]
                +5[4,1]
                +2[4,2]
            +4[3,2]
                +2[4,2]
                +6[4,3]
        +0[2,2]
            +4[3,2]
                +2[4,2]
                +6[4,3]
            +4[3,3]
                +6[4,3]
                +5[4,4]
    
"""

def solution(triangle):
    floor = len(triangle)
    max_sum = 0
    
    def dp(row, col, total):
        nonlocal max_sum
        if row == floor-1:
            max_sum= max([max([triangle[row][col], triangle[row][col+1]])+total, max_sum])
            return 0
        dp(row+1, col, total+triangle[row][col])
        
        if row != floor-2:
            dp(row+1, col+1, total+triangle[row][col])
    
    # 꼭대기 부터 시작
    dp(0,0,0)
    
    return max_sum

 

> 정확도에서 틀렸길래, 1층일 경우를 고려하지 않아서 그런가? 하였음

def solution(triangle):
    floor = len(triangle)
    max_sum = 0
    
    def dp(row, col, total):
        nonlocal max_sum
        if floor == 1:
            max_sum= triangle[0][0]
            return 0
        
        if row == floor-1:
            max_sum= max([max([triangle[row][col], triangle[row][col+1]])+total, max_sum])
            return 0
        dp(row+1, col, total+triangle[row][col])
        
        if row != floor-2:
            dp(row+1, col+1, total+triangle[row][col])
    
    # 꼭대기 부터 시작
    dp(0,0,0)
    
    return max_sum

 

> 그래도 정확도 평가에서 실패가 뜬다..

> 자세히 보니 시간 초과가 떠서 비효율적으로 보이는 코드를 쉽게 바꿔보았다.

def solution(triangle):
    floor = len(triangle)
    max_sum = 0
    
    def dp(row, col, total):
        nonlocal max_sum
        if floor == 1:
            max_sum= triangle[0][0]
            return 0
        
        if row == floor-1:
            max_sum= max([triangle[row][col]+total, max_sum])
            return 0
        
        dp(row+1, col, total+triangle[row][col])
        dp(row+1, col+1, total+triangle[row][col])
    
    # 꼭대기 부터 시작
    dp(0,0,0)
    
    return max_sum

 

> 위 코드에서는 생각해보니 1층의 경우를 따로 빼지 않아도 됐다

> 그래서 다시 수정

def solution(triangle):
    floor = len(triangle)
    max_sum = 0
    
    def dp(row, col, total):
        nonlocal max_sum
        
        if row == floor-1:
            max_sum= max([triangle[row][col]+total, max_sum])
            return 0
        
        dp(row+1, col, total+triangle[row][col])
        dp(row+1, col+1, total+triangle[row][col])
    
    # 꼭대기 부터 시작
    dp(0,0,0)
    
    return max_sum

> 제길,, 그냥 방식이 틀린거 같다

 

 

찾아보니 이 방식 자체가 계속해서 아래 단계 아이들을 계속 불러오고 있었다.

전형적인 DP의 주의점..

 

 

탑다운 방식 말고 바텀업 방식을 사용하면?

def solution(triangle):
    answer = 0
    
    for row in range(len(triangle)-1,0,-1): # row= 4, 3, 2, 1
        for col in range(row):
            triangle[row-1][col] += max(triangle[row][col], triangle[row][col+1])
    
    answer= triangle[0][0]            
            
        
    return answer

> 휴우,,, 겨우 통과 됐다.. 

 

설명해보면

    7
   3 8
  8 1 0
 2 7 4 4
4 5 2 6 5

 

여기서 아래서 부터 큰값을 더해서 

 

     7
    3 8
   8 1 0
 7 12 10 10
4  5  2  6  5

 

↓

     7
    3 8
  20 13 10
 7 12 10 10
4  5  2  6  5

↓

     7
    23 21
  20 13 10
 7 12 10 10
4  5  2  6  5

↓

     30
    23 21
  20 13 10
 7 12 10 10
4  5  2  6  5

 

> 예시의 최대값은 30으로 설명할 수 있다.

 

 

>> 난 재귀방식이 편하고 좋은데 DFS방식에서 DP방식을 떠올리는게 살짝 어색하고 어렵다..