TIL # 30 : [Algorithm] 백준 / DP / 이론 / Memoization 연습

셀레스틴 허·2021년 1월 4일

DP TIL algorithm python 백준 코테

ALGORITHM

목록 보기

3/18

새해 알고리즘 스터디(1.1~7)

2일차

백준 문제 :
9095, 1912, 9461, 1699

✨ DP 알고리즘 시작!

DP 공부를 시작하는 마음가짐 🐳

◻️ 내 것이 될 때까지 물어보고 공부하고 정리하자
◻️ 파이써닉한 코드를 많이 보고 연구하자
◻️ 조급해 말고 나만 꽉 채우자

과거를 기억하지 못하는 자는 반복하기 마련이다 -DP

Dynamic Programming의 약자로, Programming은 '테이블 만든다'라는 뜻이다. 큰 문제와 작은 문제로 나눠서 푸는 계획법이며 접근방법은 3가지다:

재귀
보관(memoization)
바텀-업(bottom-up), 탑-다운(top-down)

DP는 분할정복(divide and conquer)과 다르다. 분할정복은 큰 문제 해결하기 어려워서 작은 문제로 나눠서 푸는 방법이다. 분할정복과 달리 DP는 작은 문제에 중복이 없으며 계산한 작은 부분문제들을 이용해 풀어나간다.

모든 작은 문제들은 한번만 풀어야 하며 정답을 구한 작은 문제는 어딘가 보관한다. 보관한 작은 문제보다 더 큰 문제를 풀어나가야 할 때 똑같은 작은 문제가 나타나면 보관한 작은 문제의 결과값을 이용하는 방법이다.

언제 써야할까?

작은 문제와 작은 문제의 결과값을 이용한 풀이기 떄문에 DP는 해당 조건에 쓴다:

작은 문제가 반복/중복 될 때
작은 문제의 결과값이 계속 같을 때

요약 : DP는 작은 문제들이 중복되며, 그의 결과값이 계속 같을 때 사용하는 계획법이다.

DP 1. 보관(memoization)

한번 계산한 작은 문제들의 결과값을 저장해놓고 다시 사용하는 방법이다.

예시 코드 1:

def fib(n, memo):
  if memo[n] != null:
    return memo[n]
  
  if n==1 or n==2:
    result = 1
  
  else:
    result = fib(n-1)+fib(n-2)
  memo[n] = result
  return result

예시 코드 2:

def fib(n):
  memo[0] = 1
  memo[1] = 1

  if  n < 2:
    return memo[n]
  
  for i in range(2, n+1):
    memo[i] = memo[i-2]+memo[i-1]

  return memo[n]

if __name__ == '__main__':
  n = int(sys.stdin.readline())
  memo = [0 for i in range(n+2)]
  print(fib(n))

0,1번째 수열을 항상 1이므로 저장한다. 2번째 수열을 구할 때 배열에 저장된 이 값을 이용하며,2번째 수열의 결과값도 배열에 저장한다. n번째 수열을 구할 때까지 반복한다.

DP 2. 바텀-업(bottom-up), 탑-다운(top-down)

2A) 바텀-업(bottom-up):
작은 문제부터 구해나가는 방법이다. for문, 재귀를 이용해 처음값부터 다음값을 계산해 나간다.

def fib(n):
  if n <= 1:
    return n
  fir = 0
  sec = 0
  for i in range(0,n-1):
    next = fir+sec
    fir = sec
    sec = next
  return next

if __name__ == '__main__':
  n = int(sys.stdin.readline())
  print(fib(n))

2A) 탑-다운(top-down):
재귀함수로 구현하는 경우 대부분 탑-다운이라고 생각하면 된다. 큰 문제를 풀 때 작은 문제가 아직 안 풀렸다면 작은 문제를 해결하는 방법이다. 함수 호출을 줄이기 위해 앞서 말했던 메모이제이션을 사용한다.

def fib(n):
  if memo[n] > 0:
    return memo[n]
  if n <= 1:
    memo[n] = n
    return memo[n]
  else:
    memo[n] = fib(n-1)+fib(n-2)
    return memo[n]

if __name__ == '__main__':
  memo = [0 for i in range(100)]
  n = int(sys.stdin.readline())
  print(fib(n))

DP의 초기화

계산한 부분과 계산하지 않은 부분을 구분해야 한다. 계산하지 않은 값은 초기값 그대로며 계산한 값은 바뀌었기 때문에 그렇게 차이점을 둔다. DP에서 계산한 값의 범위를 대략적으로 알아내서 그 범위에 있지 않은 값으로 초기화를 해준다. 계산된 값이 0일 수 있는 DP의 경우에는 보톤 -1(무한대값, INT_MAX)을 사용하고 계산된 값이 0일 수 없는 경우에는 전역 변수를 선언한다.

(요약) DP 기반 알고리즘 동작 장식

구하고자 하는 큰 문제를 작은 부분문제로 나눈다.
가장 작은 부분부터 푼 뒤 값을 저장한다([0], [1]일 때의 값) ➡ 메모이제이션
메모이제이션 결과값을 이용해서 더 큰 (상위)문제의 답을 차례로 구한다.
(3)과정을 반복해서 구하고자 하는 큰 문제에 도달할 때까지 반복한다

DP 문제 해결법

몇차원(=변수 개수) DP를 할 것 인가?
변수 개수(=차원)가 정해졌으면 각각의 변수가 무슨 의미인가?
DP값이 어떤 의미인가?
어떤 DP값과 다른 DP값의 관계가 있는가? 있다면 어떤 관계인가?
➡ (4)를 알아내기 위해서 DP 테이블을 직접 채워보면 확실하게 알 수 있다
(4)의 점화식을 이용해 재귀 또는 for문으로 DP로 계산한다

A) 9095번

1차 시도(실패):

시간 제한 지나서야 패턴을 발견했다.

arr[i] = arr[i-1] + arr[i-2] + arr[i-3]

소스 코드:

testcase=int(input())
 
dp=[ 0 for i in range(12)]
 
dp[1]=1
dp[2]=2
dp[3]=4
 
for i in range(4,12):
    dp[i]=dp[i-1]+dp[i-2]+dp[i-3]
 
for i in range(testcase):
    a=int(input())
    print(dp[a])

출처 - pro-jy

풀이:

테스트케이스의 개수를 위한 변수 선언한다
제로 리스트를 만들어준다(n은 양수이며 11보다 작다)
dp[n]으로 dp 리스트에 값을 넣는다
dp[0]~[3]까지 값이 넣어져 있으니 dp[4]부터 값을 넣기 위해 range를 4~12로 설정한다
dp[i]=dp[i-1]+dp[i-2]+dp[i-3] 패턴으로 dp[i]값을 넣는다
선언한 testcase를 range로 설정해 testcase의 개수만큼 a 변수를 입력하고, print(dp[a])작업을 반복한다

배운점:
1. 제로 리스트로 dp 테이블을 먼저 만들기
2. testcase를 range로 설정해서 입력 변수 제한 두기!

문제풀이 체크리스트

◼️ 시간 제한 지났음에도 문제 터치 못함
◻️ 시간 제한 후 코드 완성
◻️ 코드 미완성
◻️ 코드 완성 - 에러
◻️ 코드 완성 - 정답

B) 1912번

소스 코드:

import sys

input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
d = [[] for _ in range(n)]
d[0] = a[0]
for i in range(1, n):
    d[i] = max(a[i], d[i-1] + a[i])

print(max(d))

출처 - chldkato

풀이:
1. n 변수를 선언해 정수 개수 입력한다
2. a 변수에 n개의 정수로 이루어진 수열 입력한다
3. n개의 리스트를 만든다
4. d[0] = a[0]로 만들어서 똑같이 만든다
5. d[0]은 이미 값이 들어있기 때문에 range(1, n)으로 설정하고 max() 함수를 이용해 a[i]와 d[i-1] + a[i] 중 더 큰 숫자를 d[i]에 대입한다
6. 그리고 리스트 안에 있는 가장 큰 숫자를 출력한다

배운점:
1. for _ in range(n) 보면 i 대신 _ 을 써서 iterator 변수 없이 for문을 선언한다.
2. a[i] = d[i-1] + a[i] max() : max(iterable, *iterables, key, default)

문제풀이 체크리스트

◼️ 시간 제한 지났음에도 문제 터치 못함
◻️ 시간 제한 후 코드 완성
◻️ 코드 미완성
◻️ 코드 완성 - 에러
◻️ 코드 완성 - 정답

C) 9461번

1차 시도(실패):

tc = int(input())

dp = [0 for _ in range(n)]

dp[0] = 0 
dp[1] = 1
dp[2] = 1
dp[3] = 1
dp[4] = 2
dp[5] = 3

for i in range(6, n):
  dp.append(dp[i-1] + dp[i-5])

for _ in range(tc):
  n = int(input())
  print(dp[n])

런타임 에러가 떴다. 확인해보니 NameError: name 'n' is not defined가 떴다. 역시 함수를 만들었어야 했나...

나는 아마 이런 코드를 구현하고 싶었던 것 같다✨ :

T = int(input())
Ns =[0,1, 1, 1, 2, 2, 3, 4, 5, 7, 9]
for _ in range(T):
    N = int(input())
    if N < len(Ns):
        print(Ns[N])
    else:
        for i in range(len(Ns), N+1):
            Ns.append(Ns[i-1]+Ns[i-5])
        print(Ns[N])

출처 - kils-log-of-develop

흥미로운 소스 코드:

import sys
n = int(sys.stdin.readline())
memo = {1:1,2:1,3:1,4:2,5:2}
def find_result(number : int) -> int:
    if number in memo:
        return memo[number]
    memo[number] = find_result(number-1) + find_result(number-5)
    return memo[number]

for _ in range(n):
    num = int(sys.stdin.readline())
    print(find_result(num))

출처 - inspirit941

이 코드의 흥미로운 점은 리스트가 아닌 딕셔너리로 메모이제이션을 했다.

문제풀이 체크리스트

◻️ 시간 제한 지났음에도 문제 터치 못함
◻️ 시간 제한 후 코드 완성
◻️ 코드 미완성
◼️ 코드 완성 - 에러
◻️ 코드 완성 - 정답

D) 1699번

소스 코드:

n = int(input())
dp = [0 for i in range(n + 1)]
square = [i * i for i in range(1, 317)]
for i in range(1, n + 1):
    s = []
    for j in square:
        if j > i:
            break
        s.append(dp[i - j])
    dp[i] = min(s) + 1
print(dp[n])

출처 - pacific-ocean

풀이:

n변수를 선언한다
n+1개의 0로 이루어진 제로 리스트를 만든다
square 변수는 1-317(317^2=100489)로 제곱 숫자를 만든다
for문 안에는 s라는 빈 리스트를 선언하고, square 변수 안에 각 제곱 숫자를 순회하며 square 제곱 숫자 요소가 i보다 더 클 경우 break한다. 만약 square 제곱 숫자 요소가 i보다 작으면 s에 dp[i - j]를 추가한다
dp[i]는 s에서 가장 적은 수와 1을 더한다.

** 왜 1을 더하는지 이해가 안된다 ㅠㅠ

while문을 사용한 소스 코드:

import sys
input = sys.stdin.readline
n = int(input())

dp = [100000 for i in range(100001)]
dp[0] = 0
dp[1] = 1
dp[2] = 2
dp[3] = 3

i = 1
while(i**2 < n+1):
  dp[i**2] = 1
  i+=1
for i in range(2,n+1):
  j = 2
  while(j*j <= i):
    dp[i] = min(dp[i],dp[i-j*j]+1)
    j+=1
print(dp[n])

출처 - dev-wd

문제풀이 체크리스트

◼️ 시간 제한 지났음에도 문제 터치 못함
◻️ 시간 제한 후 코드 완성
◻️ 코드 미완성
◻️ 코드 완성 - 에러
◻️ 코드 완성 - 정답

Reference
https://www.acmicpc.net/
https://www.youtube.com/watch?v=vYquumk4nWw&t=571s
https://www.hackerearth.com/practice/algorithms/dynamic-programming/introduction-to-dynamic-programming-1/tutorial/
https://www.quora.com/What-does-_-in-Python-mean-in-a-for-loop
https://www.programiz.com/python-programming/methods/built-in/max
https://coding-all.tistory.com/2
https://galid1.tistory.com/507
https://pro-jy.tistory.com/6
https://chldkato.tistory.com/122
https://kils-log-of-develop.tistory.com/411
https://inspirit941.tistory.com/entry/Python-%EB%B0%B1%EC%A4%80-9461-%ED%8C%8C%EB%8F%84%EB%B0%98-%EC%88%98%EC%97%B4
https://dev-wd.github.io/algorithm/backjooon1669/
https://pacific-ocean.tistory.com/205?category=810810

셀레스틴 허

Software Developer / 고통은 필연, 괴로움은 선택

이전 포스트

TIL # 29 : [Algorithm] 백준 / 기초 / 별찍기

다음 포스트

TIL # 30 : [Algorithm] 백준 / DP / 이론 / Memoization 연습

ALGORITHM

새해 알고리즘 스터디(1.1~7)

2일차

✨ DP 알고리즘 시작!

DP 공부를 시작하는 마음가짐 🐳

과거를 기억하지 못하는 자는 반복하기 마련이다 -DP

언제 써야할까?

DP 1. 보관(memoization)

DP 2. 바텀-업(bottom-up), 탑-다운(top-down)

DP의 초기화

(요약) DP 기반 알고리즘 동작 장식

DP 문제 해결법

A) 9095번

1차 시도(실패):

소스 코드:

문제풀이 체크리스트

B) 1912번

소스 코드:

문제풀이 체크리스트

C) 9461번

1차 시도(실패):

흥미로운 소스 코드:

문제풀이 체크리스트

D) 1699번

소스 코드:

풀이:

while문을 사용한 소스 코드:

문제풀이 체크리스트

TIL # 29 : [Algorithm] 백준 / 기초 / 별찍기

TIL # 31 : [Algorithm] 백준 / DP / Tiling

0개의 댓글