서론
주변에 취업을 하신 지인 분이나 코딩테스트를 몇 번 보신 분들이 필수적으로 코테 알고리즘에서 중요하다고 했던 것들 중에서 바로 동적 프로그래밍을 다룰 것이다.
내 시기는 지금 개발 공부를 더 열심히하고 프로젝트도 많이 해보는 경험을 쌓는 시기라고 많이 느낀다.
그래서 요새는 알고리즘보다는 그냥 개발 공부를 더 한다.
하지만 놓아야 해도 놓을 수가 없는게 나는 나중에 코딩 테스트를 잘 보고 싶은 욕구가 크기 때문에
그냥 닥치는대로 푸는 것이 아닌 알고리즘을 하나 하나 풀어가면서 푸는 방식을 알아가면서
정리만 하고 개발 공부에 집중하려고 한다.
이 DP 블로그는 1주일 간 3시간씩 투자하면서 정리하고 공부했던 일종의 일기? 라고 해야할까
이제 본론으로 들어가기 전에 DP를 공부하며 느낀 것은 규칙을 찾고 점화식을 구하는게 90% / 코딩 10% 라고 생각한다.
( 본론에서 나오는 Bottom-up 방식으로 모든 문제를 풀었음 )
내가 수학을 하는건지 코테를 준비하는건지 가끔 오락가락한다...
본론
DP ( Dynamic programming) 란 무엇일까??
( 진실 : 알고리즘 이름은 그냥 멋있어 보여서 지은 것이랍니다.. )
어떤 복잡하고 큰 문제를 쪼개어서 작은 문제들의 규칙성 혹은 결과들을 사용해서 다시 큰 문제로 돌아가서 해결하는 방법이다.
이 방법이 의미하는 것은 공간 복잡도를 더 늘려서 (작은 문제로 나눈다 )시간 복잡도를 단축시키는 방법( 큰 문제를 효율적으로 푼다 )
이라고 생각하면 된다.
작은 문제들이 풀린 결과들은 규칙성을 띄게 되면 다시 계속 사용하는 방식으로 진행이되는 방식.
즉 , 재귀적인 방향성도 존재하며 점화식으로 반복적으로 푸는 반복문 방식도 사용된다.
DP 의 방식 ? TOP-DOWN VS BOTTOM-UP
Top - down ( 재귀 방식 )
큰 문제를 작은 문제로 나누어서 푸는 방식으로 함수를 사용해서 반복적으로 그 함수를 재귀하여
문제를 푸는 방식이다. 대표적인 예로는 피보나치 함수가 있다.
장점 :
중복을 피하는 방식을 사용하고 필요 없는 값을 사용하지 않는다.
구현이 비교적 쉽게 사용 가능하다.
단점 :
구현된 함수가 메모리를 감당하지 못해서 과부하가 일어날 수 있는 가능성이 크다.
작은 문제들을 제대로 활용하지 못할 경우 최적의 수 또는 경우의 수가 달라지는 경우가 발생한다.
Bottom - up ( 점화식 )
top -down의 방식은 큰 문제를 나누어서 푸는 방식이지만 이 방식은 작은 문제들을 하나 하나 해결해 나가며 푸는 방식이다.
이름을 직역으로 해석해보면 밑에서 부터 올라간다. 라는 형식이기 때문이다.
규칙을 찾고 점화식을 구하여 배열 , 리스트를 통해 결과를 저장하고 풀어가는 방식이다.
장점 :
직관적으로 이해하기 비교적 쉽다.
작은 문제부터 차례대로 풀기 때문에 최적의 해 보장이 된다.
메모리의 과부하가 일어나지 않는다.
단점 :
필요없는 값이나 중복된 값들을 계산한다.
결과를 계속 저장하면서 가기 때문에 메모리 사용이 커지는 ( 공간 복잡도 ) 일이 생긴다.
# 이렇게 방식을 설명했는데 실전에서는 " 이 친구는 DP 문제야 ~ " 라고 알려주진 않는다.
그렇기 때문에 어떤 것이 DP 문제에 충족할까??
이 친구가 DP 문제 일까요?
내가 공부하면서 DP의 조건에는 총 3가지가 있었던거 같다.
1) 규칙성
2) 최적의 해 구하기
3) 중복성
1) 규칙성
dp의 특성은 작은 문제들을 수기로 작성하여 풀 수 있으며 또한 규칙이 발생될 수 있다.이런 규칙을 통해 점화식을 만드는 것이 가능하다.
2) 최적의 해 구하기
dp에서 요구하는 것은 최적의 결과를 내는 것이나 작은 문제들을 주어주면서 경우의 수를 최고의 결과로 요구할 때 주로 사용되는 조건이 있다.
3) 중복성 (중요)
아마 내가 생각한 조건 중에서 이 조건이 중요하지 않을까 싶다.
중복성은 예를 들어 어떤 문제의 N = 3 경우의 수를 구해!! 를 요구하고 N=2 경우의 수를 N=3경우의 수를 구할 때 사용하는 경우가 많다.
대표적인 또 다른 예로는 피보나치가 있다.
중복성을 보면 f(3)은 그 전에 f(2)와 f(1)을 중복적으로 사용한다.
이런 조건 3가지가 나타나면 DP 문제이다.
DP는 많은 문제들을 풀어보고 예시들을 많이 겪어봐야 이해가 가는거 같다.
이제 마지막으로 내가 DP 공부를 하면서 풀었던 한 문제를 보며 설명하겠다.
https://www.acmicpc.net/problem/11727
대충 문제를 설명하면 2*1 ,1*2 와 2*2로 2*N의 사각형을 몇 개를 사용해서 만들 수 있는지를 묻는 문제이다.
나는 여기서 바로 키보드에 손을 대지 않고 바로 메모장을 열어서 몇 개가 나오는지 그리면서 숫자를 세어갔다.
사실 5개까지만 구했다.
그러고 느낀 것은 " 아 규칙성을 띄겠구나.. " 라는 생각이었다.
보통 2*2도 2*1과 1*2로 만들 수 있으니깐 2*2를 사용하는 빈도가 규칙적으로 바뀌겠지? 로 생각이 들어갔다.
그래서 이런 점화식이 나오게 되었다.
이렇게 1) 조건에 해당 되는 규칙성과 동시에 홀수와 짝수를 합친 최적의 해를 구하는 방식도 찾게되며 1) 조건과 2) 조건이
동시에 찾게 된다.
이 문제를 풀 때 찾지 못하였지만 3) 중복성도 포함이 된다.
예를 들면 2*3 에서 2*4를 만들 때 2*3의 경우를 사용이 가능하는 중복적인 조건을 찾을 수 있다.
그 밖에 코테 대비해서 추천 받은 DP 문제들 ..
https://www.acmicpc.net/problem/2293
이 문제는 규칙을 찾기가 너무 힘들었음.. 코딩은 2분 생각은 2시간..
# 2293 동전 1 / DP
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
arr = []
for _ in range(N):
arr.append(int(input()))
coin = [0] * (K+1)
coin [0] = 1
for i in arr:
for j in range(i, K+1):
coin[j] += coin[j-i]
print(coin[K])
https://www.acmicpc.net/problem/15989
#15989 1,2,3 더하기 4 / DP
import sys
input = sys.stdin.readline
arr = [1] * 10001 # 1을 무조건 하나씩을 가지고 있으니깐 1을 설정해줌.
# 또한 N개가 2로 나뉘어지는 시점은 2이므로 2부터
for N in range(2,10001):
arr[N] = 1+(N//2)
# +3이 시작되는 시점은 3부터 이므로 3부터 범위를 지정
for N in range(3,10001):
arr[N] += arr[N-3]
count = int(input())
for i in range(count):
print(arr[int(input())])
https://www.acmicpc.net/problem/1003
https://www.acmicpc.net/problem/9095
마무리
DP 는 진짜 그냥 수학인거 같고 모든 알고리즘이 다 그렇겠지만 문제를 많이 풀어봐야 하는 것 같다...
또 요새 개발 공부를 하고 있지만 정작 정리를 제대로 하지 않는 게으름을 제대로 나에게 표현 중이다...
다시 간이 프로젝트 및 공부를 더 해야겠다...
허나 !! 방학 때라도 하루에 한 개의 알고리즘 문제 풀어야지 ! ( 학원에서 알고리즘 가르쳐야해서 해야댐 )
마무리로 이제 개발 공부 정리도 올려야겠다. 너무 알고리즘만 올려...
'알고리즘' 카테고리의 다른 글
| [백준] 1012번 유기농배추 (JAVA) (0) | 2025.07.13 |
|---|---|
| [백준] 2230 수 고르기 (JAVA) (2) | 2025.07.11 |
| [백준] 7569번 토마토 (PYTHON) (0) | 2024.11.19 |
| [백준] 17609번 회문 / C언어 (0) | 2024.09.20 |
| [백준 / 올림피아드 ] 28325번 호숫가의 개미굴 ( DP , greedy / c언어) (0) | 2024.07.10 |
