데이터 엔지니어링

안녕하세요. 오늘 다뤄볼 주제는 다이나믹 프로그래밍입니다.

위키에 따르면 동적 프로그래밍은 "복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법" 이라고 설명하고 있습니다.

나무위키에 조금 더 와닿는 설명이 있는데, 답을 재활용하는 것입니다. 앞에서 구했던 답을 뒤에서 이용하고, 옆에서도 이용해서 더 빠르게 답을 구하는 문제 해결 패러다임이라고 볼 수 있습니다.

가장 많이 사용하는 예제는 피보나치 수열입니다.

아래 피보나치를 재귀를 이용해 동적프로그래밍으로 구현한 코드입니다.

import time





def fibonacci(n):

    if n<=1:

        return n

    

    return fibonacci(n-1) + fibonacci(n-2)







def fibonacci_with_cache(n,cache={}):

    if n in cache:

        return cache[n]



    if n <=1:

        return n

    

    cache[n] = fibonacci_with_cache(n-1) + fibonacci_with_cache(n-2)



    return cache[n]





def benchmark():

    start_time = time.time()

    print(fibonacci_with_cache(40))

    end_time = time.time()

    execution_time = end_time - start_time

    print(f"Execution time: {execution_time:.6f} seconds")



# 102334155

# (fibonacci - Execution time: 21.109457 seconds



#102334155

# Execution time: 0.000057 seconds



benchmark()

위 예제에서 피보나치 함수를 2 가지 버전으로 만들었는데요. 하나는 일반 피보나치 함수이고, 다른 하나는 캐시라는 이름이 붙어있습니다.

fibonacci_with_cache 함수는 dictionary 타입(k,v) 의 변수를 캐시라고 가정해서 피보나치의 결과를 캐시에 저장했습니다.

이렇게 답을 구한 결과를 메모리에 저장하는 방법을 메모이제이션(memoization) 이라고 합니다..

응답속도의 결과를 비교해보면 차이가 꽤 납니다.

끝.

1.문제 소개

• DP 문제에 해당한다.

2.코드

import math
# 이친수 여부
def is_ichin(source):
    result = True
    offset = 1
    while(offset<len(source)):
        if source[offset] == '1' and source[offset-1] == '1':
            result=False
            break
        offset +=1
        
    return result

# 문자열 탐색 방식
def solution():
    N = int(input())
    S = int(math.pow(2,N))
    cnt = 0 
    for num in range(0,S):
        s = bin(num)[2:]
        if len(s) == N and is_ichin(s):
            cnt+=1
        #print(f"num : {num}\t binary : {s} ichin : {is_ichin(s)}")
    
    print(cnt)
          
                  
ichin_array = [0,1,1,2]

def get_ichin(n):
    if n < len(ichin_array):
        return ichin_array[n]
    else:
        ichin = get_ichin(n-1)+get_ichin(n-2)
        ichin_array.append(ichin)
        return ichin
    

    
    
# DP 방식 
def solution():
    N = int(input())
    print(get_ichin(N))
    
solution()

3.코멘트

• 이진수를 만들어 문자열 탐색으로 이친수를 여부를 구하는 함수를 만들어 규칙을 찾아봤다.
• 이친수는 피보나치 수열과 동일한 규칙을 갖고 있었다.
• 중복 호출을 줄이는 방식으로 DP 를 이용해 정답을 출력했다.