이번 주차에서는 다이나믹 프로그래밍과 그리디를 배웠다. 여전히 어려운 건 마찬가지이지만 계속 알고리즘 문제들을 풀어가다보니 어떻게 해나가야하는지 조금씩 알게 되는 것 같아 좀 뿌듯하다.
dp는 정말 알다가도 모르겠는 문제들이 많다. 그래서 어려웠던 문제나 새로 알게 된 유형의 문제를 정리했다. 금방 까먹으면 안되니까!
백준 9251번 LCS
https://www.acmicpc.net/problem/9251
이전에 풀어왔던 dp 문제들은 dp = [0] * (n+1)의 방식으로 리스트 하나만 만들어서 그 안에 저장을 했었는데 이 문제에서부터 dp 테이블로 풀어야했다. dp 테이블이라는 접근 방식 자체가 내 머릿속에 없었기 때문에 생각이 안나서 그냥 답을 보고 이해한 다음 따로 풀었다.. 그리고 이전 값에서 바로 값을 받아와야겠다는 생각만 했지 왼쪽 위 대각선의 값을 받아와야한다는 사실은 생각도 못했다.
접근법
- 두 수열을 받아줄 a와 b 리스트를 만든다.
- (len(b) + 1) * (len(a) + 1)의 dp 테이블을 만든다. 편의상 n,t에 len(a), len(b)를 담았다. (예제와 같다면 저런 형태의 dp 테이블이 된다 물론 초기값은 다 0이다)
- a[i] == b[j]일 때(a와 b가 같은 문자일 때), dp 왼쪽 위 대각선 값에 +1을 해준다.
- 같은 문자가 아니라면 이전에 받아왔던 값(바로 왼쪽값)이나 현재 위치 기준 위쪽에 있는 값중 가장 큰 값을 받아온다.
- 마지막으로 나온 값이 최종 답이기 때문에 dp([n][t])를 출력한다.
import sys
input = sys.stdin.readline
a = list(input().rstrip())
b = list(input().rstrip())
n, t = len(a), len(b)
dp = [[0] * (t+1) for _ in range(n+1)]
for i in range(1, n+1):
for j in range(1, t+1):
# a와 b가 일치할때, 왼쪽 위 대각선 값에서 +1을 해준다
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
# 그게 아니라면 현재 위치의 위쪽이나 왼쪽에 있는 값중 큰 값을 추가해준다
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
print(dp[n][t])백준 12865번 평범한 배낭
https://www.acmicpc.net/problem/12865
가장 기본적인 배낭 문제라고 한다. 근데 어려웠다.. 뭔가 dp 테이블을 만들어서 풀어야하는 문제같은데 아까 LCD 문제처럼 간단하게 +1해서 되는 문제가 아니고 물건의 가치와 무게를 고려해야하기 때문에 조금 헷갈렸던 것 같다. 알고나니 아까 문제보다 조금 더 응용을 하면 풀 수 있는 문제라고 느껴졌다.
접근법
- backpack이라는 2차원 배열을 만들어서 물건 무게와 가치를 받아서 넣는다.
- 아까 LCD 문제와 같이 dp 테이블을 만든다.
- 무게가 1일 때부터 들어갈 수 있는지를 판별한다. 만약 넣으려는 물품이 더 크다면 이전에 받아왔던 값을 가져온다.
- 가방에 들어갈 수 있는 무게라면, 지금 가방에 들어있는 가치와 새롭게 들어올 수 있는 물건의 가치를 비교해서 더 가치있는 것을 넣는다.
- dp의 마지막값을 출력한다.
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
backpack= [[0,0]]
for _ in range(n):
backpack.append(list(map(int, input().split())))
dp = [[0] * (k+1) for _ in range(n+1)]
# 무게 = 1일때 넣을 수 있는 값을 표에 삽입해줌
# 그래서 k값에 도달했을 때 넣을 수 있는 최적의 값을 찾아주는거임
for i in range(1, n+1):
for j in range(1, k+1):
weight = backpack[i][0]
value = backpack[i][1]
# 넣으려는 물건의 무게가 더 클 때
if j < weight:
# 옆의 값 가져옴
dp[i][j] = dp[i-1][j]
else: # 가방에 넣을 수 있다면
# 아까 값이 더 큰지, 새로운 값이 더 큰지 판별해서 넣어줌
# ex) 6kg = 13의 값이 최적/ dp[i-1][6 - 6]+ 13 = 13 삽입
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight] + value)
print(dp[n][k])백준 11053번 가장 긴 증가하는 부분 수열
https://www.acmicpc.net/problem/11053
이 문제의 챌린지는 어떻게 해야 이전 값과 비교하면서 dp값을 갱신할 수 있는지 모르겠다는 거였다. 그 부분에 초점을 맞춰서 코드를 짰다. 중간에 막혀서 다른 사람들 풀이를 참조하긴 했지만..
접근법
- 수열을 받아줄 seq라는 리스트를 생성한다.
- dp는 [1]로 채워주는데, 그 이유는 처음 숫자를 카운트할 때부터 1이고, 그 처음 숫자 기준으로 증가할 때마다 길이가 +1씩 증가하기 때문이다. dp = [0] * (n+1) 해주고 dp[1] = 1로 설정해도 상관없다. 근데 그렇게 되면 for문 range랑 코드를 조금 바꿔줘야한다.
- 이중 포문을 돌리는데 for j in range(i) << 이 부분이 중요하다! 이 부분이 계속해서 이전 숫자들과 현재 숫자를 비교해준다.
- seq[i]가 더 클 때, 현재 값이나 dp 이전값에서 +1한 값을 비교했을 때 더 큰 값을 넣어준다. 예를 들어 i가 2라면, dp[0] + 1과 dp[1] +1, 그리고 dp[2]의 값 중 가장 큰 값을 넣어주는 것이다.
- dp에서 가장 큰 수를 출력한다.
import sys
input = sys.stdin.readline
n = int(input())
seq = list(map(int, input().split()))
dp = [1] * (n+1)
# 포문을 이렇게 돌리게 되면 i = 2일때, j는 0과 1이다.
# 그래서 계속 이전 숫자들과 현재 숫자를 비교할 수 있다
for i in range(1, n):
for j in range(i):
if seq[j] < seq[i]:
# 현재값과 이전값 +1 중 큰 값을 넣는다
dp[i] = max(dp[i], dp[j] + 1)
# 그 중 가장 큰 수를 출력한다
print(max(dp))
백준 1946번 신입사원
https://www.acmicpc.net/problem/1946
그리디 문제다. 이 문제는 원래 시험성적, 면접성적을 다 일일이 비교하면서 코드를 짜려고 했는데 그러다보니 예제는 출력되지만 틀렸습니다가 계속 나오고 코드도 너무 지저분했다. 그래서 다른 사람 풀이를 참고했는데 그냥 면접성적만 기준으로 하면 되더라.. 조금 억울했다..
접근법
1. 성적을 받아서 이차원 배열 안에 넣어서 sort해준다.
2. 면접 성적을 기준으로 카운트를 할 건데, 무조건 한명은 뽑히므로 cnt는 1에서 시작한다.
3. 만약 지금 lst[j][i]가 지금 비교하는 lst[0][1]보다 작을 때, 즉 면접을 더 잘 봤을 때 test값을 현재값으로 갱신하고 cnt +1 해준다.
4. 반복 후 cnt값 출력
import sys
input = sys.stdin.readline
n = int(input())
for i in range(n):
m = int(input())
lst = [list(map(int, input().split())) for _ in range(m)]
lst.sort()
ans = []
test = lst[0][1]
cnt = 1
for j in range(1, m):
if lst[j][1] < test:
test = lst[j][1]
cnt += 1
print(cnt)
