<aside> ✅ 금주의 키워드
동적 프로그래밍
그리디 알고리즘 </aside>
11053번 가장 긴 증가하는 부분 수열
이 문제는 동적 프로그래밍에서 가장 유명한 유형인것 같다. 한 수열 내에서 증가하는 부분 수열을 구하는 것이다. 완전 탐색 방법으로 문제를 풀 수 있지만 엄청난 시간과 메모리를 할당해야 하므로 적절하지 않다. 이전 수열의 최적값을 DP테이블에 저장하고 그 최적값을 이용하여 단시간에 최적해를 구할 수 있다. 이러한 개념은 점화식과 같다. 다른 문제들도 마찬가지 이지만 동적 프로그래밍에서 가장 어려운 부분은 점화식을 구하는 것이다. 이전 최적해와 구하려는 최적해의 관계를 살펴보는 것이 가장 중요한 것 같다.
n = int(input())
a = list(map(int,input().split()))
dp = [1] * n
for i in range(1,n):
for j in range(0,i): #구하려는 최적해 이전의 수열들에 대해 탐색
if a[i] > a[j]: #이전 수열이 현재 수열보다 작을때 -> 증가하는 수열일때
dp[i] = max(dp[i],dp[j]+1) #이전 수열의 최적해 +1과 자기자신중에 큰값으로 갱신
print(max(dp))
가장 긴 부분수열을 활용하는 문제로 아래 두 문제가 있다.
위 두문제의 코드는 깃허브에서 확인 할 수 있다.
2253번 점프
이 문제도 크게 보면 위의 가장 긴 증가하는 부분수열과 같다고 볼 수 있다고 생각한다. '현재 위치의 돌은 어느 위치에서 어느 속도를 가지고 점프를 했었을까?'를 고민해 보면 점화식을 쉽게? 떠올릴 수 있었다. 만약 현재 돌이 위치 5, 속도 3 이라면 현재 돌은 위치 2에서 3만큼 점프해서 왔을 것이다. 그렇다면 위치 2에서 3만큼 점프할수 있는 경우는 (위치2, 속도2),(위치2, 속도3),(위치2, 속도4) 밖에 없다. 이 문제는 변수가 위치와 속도 2가지 이므로 DP테이블이 2차원이다.
import sys
input = sys.stdin.readline
from math import sqrt
inf = int(1e9)
n , m = map(int,input().split())
dp = [[inf]*(int(sqrt(2*n))+2) for _ in range(n+1)]
dp[1][0] = 0
stones = set()
for _ in range(m):
stones.add(int(input()))
for i in range(2,n+1):
if i in stones:
continue
for v in range(1,int(sqrt(2*i))+1):
dp[i][v] = min(dp[i-v][v-1],dp[i-v][v],dp[i-v][v+1]) + 1
result = min(dp[n])
if result == inf:
print(-1)
else:
print(result)
여기서 많이 헷갈렸던것이 sqrt(2n)이다. 이것은 위치 n까지 점프해서 도착 할때 가능한 가장 큰 속도 값이다. 위치 1에서 시작해서 n까지 점프하려면 속도 1 부터 2,3,,,k까지 뛰었을 것이다. 그렇다면 속도 k까지 합이 n과 같아야 한다. 이를 근사적으로 구한 식이 sqrt(2n)이다. 등차수열의 합 공식을 떠올려 보면 된다.
위 내용은 아래 블로그를 참고하였습니다.
12865번 아주 평범한 배낭
이 문제는 위 2문제와 약간 다른점이 있다. 위 2문제는 해당위치로 꼭 점프를 한다던가 해당 수를 포함하는 증가하는 부분수열의 최대값을 갱신하는 방식으로 풀이하였다. 하지만 이 문제는 현재 물건을 넣을 수도 있고 넣지 않을 수도 있다. 그래서 현재 물건을 담는 경우의 가치와 현재 물건을 담지 않는 경우의 최적해의 최대값을 DP테이블에 입력해 주면된다.
import sys
input = sys.stdin.readline
n , k = map(int,input().split())
weight_list = [0]
dp = [[0] * (k+1) for _ in range(n+1) ]
for _ in range(n):
w , v = map(int,input().split())
weight_list.append([w,v])
for i in range(1,n+1): #i번째 물건을 넣으려 한다
for j in range(k+1): #무게가 j일때 가치의 최대값을 테이블에 입력하려 한다
if j < weight_list[i][0]: #현재 물건의 무게보다 작을때
dp[i][j] = dp[i-1][j] #물건을 넣을수 없으므로 이전(i-1번째 까지의 최대값)의 값을 그대로 가져옴
else:
dp[i][j] = max(dp[i-1][j], #현재 물건을 선택하지 않는 경우와
dp[i-1][j-weight_list[i][0]]+weight_list[i][1]) #현재 물건을 선택하는 경우의 최대값을 입력
print(dp[n][k])
dp[i-1][j-weight_list[i][0]]인 이유는 현재 물건을 더해서 j가 되려면 i-1 번째에서의 무게는 j에서 현재 물건의 무게를 뺀값이었기 때문이다. 이와 비슷한 느낌의 문제로 포도주 시식이 있다.
import sys
input = sys.stdin.readline
n = int(input())
wine = []
for _ in range(n):
wine.append(int(input()))
if n == 1:
print(wine[0])
exit(0)
elif n == 2:
print(wine[0] + wine[1])
exit(0)
elif n == 3:
print(max(wine[0]+ wine[2],wine[1]+ wine[2],wine[0]+wine[1]))
exit(0)
dp = [0] * n
dp[0] = wine[0]
dp[1] = wine[0] + wine[1]
dp[2] = max(wine[0]+ wine[2],wine[1]+ wine[2],wine[0]+wine[1])
for i in range(3,n):
dp[i] = max(dp[i-3]+wine[i-1]+ wine[i],dp[i-2]+ wine[i],dp[i-1])
print(dp[n-1])
위 내용은 아래 동영상을 참고하였습니다.
1520번 내리막 길
위의 3문제는 모두 바텀업 방식으로 풀이하였다. 하지만 이 문제는 경로를 끝까지 순회한 후 테이블을 채워야 한다는 점에서 탑다운 방식이 코드 짜기가 수월하다. 그리고 재귀함수의 단점을 메모기법을 통해 문제를 해결할 수 있다. 시험 때 바텀업만 생각하다가 풀어내지 못했다. 다이내믹 프로그래밍 하면 그냥 무조건 바텀업만 생각했던 나를 반성하였다. 그리고 아직 재귀함수에 대해 익숙하지 않다는 것도 알았다. 더 많은 문제를 풀어봐야 할것 같다.
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
def dfs(y,x):
if y == m-1 and x == n-1: # 끝에 도달하면
return 1 # 1을 반환 -> 최적해 누적 시작
if dp[y][x] == -1: # 상하좌우에 내리막길이 없는경우
return 0 # 누적하지 않는다
if dp[y][x]: # 메모가 되어있다면
return dp[y][x] # 메모 값을 반환
cnt = 0
# 상하좌우에 대해서 내리막 길인 경우 dfs를 진행
if 0<=y+1<m and 0<=x<n and graph[y][x] > graph[y+1][x]:
cnt += dfs(y+1,x)
if 0<=y<m and 0<=x+1<n and graph[y][x] > graph[y][x+1]:
cnt += dfs(y,x+1)
if 0<=y-1<m and 0<=x<n and graph[y][x] > graph[y-1][x]:
cnt += dfs(y-1,x)
if 0<=y<m and 0<=x-1<n and graph[y][x] > graph[y][x-1]:
cnt += dfs(y,x-1)
if cnt == 0: # 상하좌우가 마지막인 내리막길 경로가 없다면
dp[y][x] = -1 # 메모에 기록
return 0 # 누적하지 않는다
dp[y][x] = cnt # 내리막길 경로의 수(최적해)를 메모
return dp[y][x] # 계산한 값을 누적하기 위해 반환
if __name__ == "__main__":
m , n = map(int,input().split())
graph = [list(map(int,input().split())) for _ in range(m)]
dp = [[0]*n for _ in range(m)]
ans = dfs(0,0)
print(ans)
1202번 보석도둑
이 문제는 그리디 방법으로 풀이할 수 있다. 하지만 최대값과 최소값을 탐색 할 때 max함수나 반복을 사용하면 시간복잡도로 인해 시간초과를 맛볼 수 있다. 여기서 최대,최소를 다룰때 시간복잡도 면에서 유리한 우선순위 큐를 사용하게 된다. 사실 그리디에서 가장 많이 생각하는 것이 최대와 최소인데 우선순위 큐를 사용할 생각을 못했다.
import sys
input = sys.stdin.readline
from heapq import heappop,heappush
a,b = map(int,input().split())
gems = []
bags = []
for _ in range(a):
w , v = map(int,input().split())
heappush(gems,[w,v]) # 가벼운 보석부터 꺼내게끔 힙푸시
for __ in range(b):
heappush(bags,int(input())) # 가벼운 가방부터 꺼내게끔 힙푸시
result = 0
tmp = [] # 이곳에 가방에 담을 수 있는 보석들의 가치를 저장
for ___ in range(b): # 가방의 수만큼 반복
capacity = heappop(bags) # 가방의 용량을 기록
while gems and gems[0][0] <= capacity: # 가방의 용량보다 작은 보석들을
weight , value = heappop(gems)
heappush(tmp,-value) # tmp에 최대힙으로 푸시(가장 큰 가치를 찾아야하기때문)
if tmp:
result += -heappop(tmp) # 담을 수 있는 보석 중 가장 가치있는 것을 담음
elif not gems: # 넣을 보석이 없다면
break # 종료
print(result)
위 코드는 아래 블로그를 참고하여 작성하였습니다.
2138번 전구와 스위치
이 문제는 그리디로 분류되어 있다. 처음 해설을 볼 때 이게 왜 그리디인지 의아했다. 첫 스위치의 상태를 분류해서 푼거 아닌가 라는 생각을 했다. 하지만 다시 생각해 보니 첫 스위치를 켤지 끌지 결정하여 나머지 모든 스위치의 on/off를 결정 하는 것이 오직 자신의 왼쪽에 있는 전구의 상태이게끔 제한하였다. 문제를 보면 스위치를 켬으로 자신과 좌우의 상태가 바뀌어 좌우의 상태를 모두 봐야할 것 같지만 이것을 제한한 것이다.
import sys
input = sys.stdin.readline
inf = int(1e9)
def rev_bulb(arr , i): #스위치를 켜서 좌,우,본인의 상태를 변경
if i == n-1:
arr[i-1] = 1 - arr[i-1]
arr[i] = 1 - arr[i]
else:
arr[i] = 1 - arr[i]
arr[i+1] = 1 - arr[i+1]
arr[i-1] = 1 - arr[i-1]
return arr
def chk_bulb(arr,c): # target과 동일한지 확인
for a in range(n):
if arr[a] != target[a]:
return inf # target과 다를 경우 inf를 반환
return c
if __name__ == "__main__":
n = int(input())
given1 = list(map(int,input().strip()))
target = list(map(int,input().strip()))
given2 = [ a for a in given1]
given2[0] = 1 - given2[0] # given2는 첫번째 스위치를 켜는 경우
given2[1] = 1 - given2[1]
count1 = 0
for i in range(1,n):
if given1[i-1] != target[i-1]:
given1 = rev_bulb(given1,i)
count1 += 1
count2 = 1 # 첫번째 스위치를 켰으므로 1부터 카운트 시작
for j in range(1,n):
if given2[j-1] != target[j-1]:
given2 = rev_bulb(given2,j)
count2 += 1
count1 = chk_bulb(given1,count1)
count2 = chk_bulb(given2,count2)
if count2 == count1 == inf: # 두 경우 모두 다를 경우(target이 될 수 없는 경우)
print(-1)
else:
print(min(count1,count2)) # 두 경우 중 최소 회수를 출력
위 코드는 아래 블로그를 참고하여 작성했습니다.
느낀점 및 더 보아야 할 것