Krafton_jungle 5기 21일차 TIL - DP, 알고리즘

알고리즘

 

Dynamic Programming

DP란?	점화식을 사용해 하나의 큰 문제를 여러개의 작은 문제로 나누어서 그 결과를 큰 문제에 대입해서 푸는 방법 계산값을 재탕한다는 의미로 받아들였다. 알게모르게 알고리즘 문제를 풀이하며 여러번 사용했던 방법.
DP를 사용하는 이유	난 이 이유를 백준의 피보나치를 풀이하며 찾았는데, 기존 피보나치의 경우 일반적인 재귀로 풀면 O(n²)이지만 dp로 값을 재탕하면 시간 복잡도를 O(n)으로 줄일 수 있다. 자세한 내용은 2748 피보나치수 2 문제를 풀어보면 바로 감이 잡힌다.
구현법	젓번째로는 Bottom-Up 방식으로 DP 테이블을 만들어 해당 테이블을 만족하는 점화식을 생성하고, 그 식을 바탕으로 반복문을 사용해 접근하는 방식이다. 해당 방식의 장점은 재귀를 사용하지 않기 때문에 추가 메모리를 사용하지 않는다. 하지만 점화식을 알아내는 과정이 순탄치는 않은 편 두번째로는 Top-Down 방식이다. 해당 방법은 재귀를 반복하며, 해당 값이 이미 Memorization 되어있다면 저장되어 있던 내역을 꺼내서 활용하는 방식이다. 해당 방식은 아무래도 점화식을 구하지 않고도 구현이 가능하다보니 Bottom-Up 방식보다는 구현 난이도가 쉬운 편

 

DP를 적극 응용해 다음 문제를 풀었다.

 

2748 피보나치 수 2

import sys
input = sys.stdin.readline


def top_down(n):
    # 만약 입력값이 0이나 1이면
    if (n < 2):
        fib_memo[n] = n
        return n
    # 만약 메모에 계산된 값이 있으면 바로 반환
    # 약간 BFS, DFS의 방문처리 하는거 생각난다.
    if fib_memo[n] > 0:
        return fib_memo[n]

    fib_memo[n] = top_down(n - 1) + top_down(n - 2)

    return fib_memo[n]

# 기존 풀이와 똑같음
def bottom_up(n):
    fib_table[0], fib_table[1] = 0, 1
    for i in range(2, n+1):
        fib_table[i] = fib_table[i - 1] + fib_table[i - 2]
    return fib_table[n]


n = int(input())
fib_memo = [0] * (n+1)
fib_table = [0] * (n+1)
print(bottom_up(n))

top_down 방식과 botton_up 방식 두가지로 풀이해봤다.

 

1904 01타일

import sys
input = sys.stdin.readline

div = 15746

def bottom_up(n):
    # 만약 n의 값이 1이면
    if n < 2:
        return n
    fib[1]= 1
    for i in range(2, n+1):
        fib[i] = (fib[i-1] + fib[i-2]) % div
    return fib[n]


# 상수를 인덱스로 변경
# 1이 입력값으로 들어오면 index는 2를 가르켜야함
n = int(input()) +1
# 피보나치의 값을 저장할 배열 선언
fib = [0] * (n + 1)
# 1 = 1 1
# 2 = 2 00 11
# 3 = 3 001 100 111
# 4 = 5 1111 0000 0011 1001 1100
# 5 = 8 11111 00001 00100 10000 00111 11100 10011 11001
# 그냥 피보나치인듯 함

print(bottom_up(n))

 

증가하는 수열이 피보나치와 일치한다는 사실을 깨닫고, 피보나치의 점화식을 그대로 가져다가 썼다.