개인적으로 내가 가장 어려워하는 유형의 문제다.
학생 시절때부터 수열/점화식에 약해서..... 그래서 복습을 빡세게 해야겠다.
유형 1. 단위 숫자로 경우의 수 구하기
DP의 대표적인 유형 문제라 볼 수 있다. 아마 DP 풀면 제일 먼저 풀게 될 유형이기도 하고...
연산에 사용될 수 있는 숫자가 화폐 단위처럼 특정 단위로 나눠져있는 경우이다.
- 거스름돈
https://school.programmers.co.kr/learn/courses/30/lessons/12907
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
고정된 단위 숫자로 목표 숫자를 만들어낼 수 있는 경우의 수를 구하는 문제.
# n원을 만들기 위한 경우의 수를 구하는 DP(dynamic programming) 문제입니다.
# 예를 들어, 동전 [1, 2, 5]가 있을 때 n = 5라면,
# 1+1+1+1+1, 1+1+1+2, 1+2+2, 5 등 다양한 조합이 가능합니다.
def solution(n, money):
# dp[i]는 i원을 만드는 경우의 수를 저장하는 배열
# dp[0] = 1인 이유는, 0원을 만드는 방법은 '아무 동전도 사용하지 않는 것' 1가지이기 때문
dp = [1] + [0] * (n+1)
# 동전 단위를 오름차순으로 정렬
money.sort()
# 각 동전에 대해 경우의 수를 누적 계산
for coin in money:
# 현재 동전 coin으로 만들 수 있는 금액부터 n까지 순회
for p in range(coin, n+1):
# 이전에 coin을 사용해서 만들 수 있었던 경우의 수를 현재 dp[p]에 더함
dp[p] += dp[p - coin]
# 경우의 수가 매우 클 수 있으므로 1,000,000,007로 나눈 나머지를 반환
return dp[n] % 1000000007
유형 2. 연산으로 특정 숫자 만들기
주어진 연산 중 가장 효율적인 것을 선택해서, 연산 횟수를 최소화하는 유형이 자주 나온다.
- 1로 만들기
https://www.acmicpc.net/problem/1463
<사용 가능 연산>
1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.# 최대한 1번 연산을 많이 사용하게끔
def solution(N):
dp = [0] * (N+1)
# 반복문 전체에 걸쳐, min 값을 갱신해준다
for i in range(2, N+1):
# 현재 수에서 1을 빼는 경우
dp[i] = dp[i-1] + 1
# 현재 수가 2로 나눠 떨어지는 경우
if i % 2 == 0:
dp[i] = min(dp[i], dp[i//2] + 1)
# 현재 수가 3으로 나눠 떨어지는 경우
if i % 3 == 0:
dp[i] = min(dp[i], dp[i//3] + 1)
return dp[N]
N = int(input())
print(solution(N))
- 1로 만들기 2
https://www.acmicpc.net/problem/12852
연산 과정까지 포함해서 출력해야 하므로, 직전 숫자를 함께 저장해야 한다는 차이가 있다.
n = int(input())
# dp list
# (연산 횟수, 직전 숫자)
dp = {}
dp[1] = [0, [1]]
if n == 1:
print(dp[n][0])
print(*dp[n][1])
else:
# dp[i] = i를 만들기 위해 필요한 최소 연산횟수
for i in range(2, n+1):
# 1을 빼기
dp[i] = [dp[i-1][0] + 1, [i] + dp[i-1][1]]
# 2로 나눠진 것 전에서 더하기 1
if i % 2 == 0 and dp[i][0] > dp[i//2][0] + 1:
dp[i] = [min(dp[i][0], dp[i//2][0]+1), [i]+dp[i//2][1]]
# 3으로 나눠지면 3으로 나눠진 전 것에서 더하기 1
# 현재 거랑 더 작은거 비교하기
if i % 3 == 0 and dp[i][0] > dp[i//3][0] + 1:
dp[i] = [min(dp[i][0], dp[i//3][0]+1), [i]+dp[i//3][1]]
print(dp[n][0])
print(*dp[n][1])
- N으로 표현
https://school.programmers.co.kr/learn/courses/30/lessons/42895
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
모든 사칙연산 수행이 가능한 경우다. 따라서 모든 연산 경우의 수를 dp에 기록하고, 찾던 목표값이 존재하면 정답을 반환해주는 방식으로 풀면 된다.
def solution(N, number):
# dp[i]는 숫자 N을 i번 사용해서 만들 수 있는 수들의 집합을 저장
# dp[1] ~ dp[8]까지 사용 (최대 8번까지 N을 사용할 수 있음)
dp = [set() for i in range(9)]
for idx in range(1, 9):
dp_list = dp[idx]
# N을 idx번 이어붙여 만든 숫자 (ex: N=5, idx=3이면 555)
dp_list.add(int(str(N) * idx))
# i = j + (idx - j) 형태로 나누어
# 이전에 만든 값들로 사칙연산 조합을 만들어 현재 dp[idx]에 추가
for j in range(1, idx):
for k in dp[j]:
for l in dp[idx - j]:
dp_list.add(k + l) # 덧셈
dp_list.add(k - l) # 뺄셈
dp_list.add(k * l) # 곱셈
# 나눗셈은 0으로 나누는 것을 방지
if l != 0:
dp_list.add(k // l)
# 현재 만든 집합(dp[idx]) 안에 목표 숫자가 있으면 정답 반환
if number in dp_list:
return idx
# 8번 사용해도 만들 수 없다면 -1 반환
return -1
- 설탕 만들기
정해진 단위수 (5kg) 를 이용하여 목표 숫자를 맞춰야 하는 문제이다.
https://www.acmicpc.net/problem/2839
# 봉지 개수를 최대한 적게 해야댐
# 그러면 5킬로 봉지를 최대한 많게
# 1로만들기 문제와 유사한듯
# a_i min (a_5, a_3, a_i-1)
def solution(N):
cnt = 0
# 5킬로 봉지의 개수를 기준으로 dp list 생성
dp = [1002] * (N//5+1)
for i in range(N//5+1):
dp[i] = i # 5킬로 봉지 개수
# 남은 무게
weight = N - 5 * dp[i]
cnt = 0
# Weight이 0이 될 때까지 3으로 빼주기
while weight > 0:
weight -= 3
cnt += 1
# 만약 불가능할 경우
if weight != 0:
dp[i] = 1002 # 1002로 갱신
else:
dp[i] += cnt
# print(dp)
if min(dp) == 1002:
return -1
else:
return min(dp)
N = int(input())
print(solution(N))
유형 4. 구간합
구간을 나누는 모든 경우를 고려해서 최대값 / 최소값을 찾는 문제
- 사칙 연산
https://school.programmers.co.kr/learn/courses/30/lessons/1843
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
각 구간 arr[i:j+1]에서 만들 수 있는 최댓값과 최솟값을 동시에 구한다.
이 때 연산 기호 중 "-" (뺄셈) 이 포함되는데,
연산에서는 최댓값 - 최솟값이 가장 작고, 반대로 최솟값 - 최댓값이 가장 크기 때문에 max_dp, min_dp list를 따로 지정하여 연산을 진행한다.
def solution(arr):
# 수식 길이
n = len(arr)
INF = 99999999 # 큰 수를 이용한 초기화
# 숫자 리스트와 연산자 리스트로 분리
nums = [int(x) for x in arr[::2]] # 홀수 인덱스: 숫자
ops = [x for x in arr[1::2]] # 짝수 인덱스: 연산자
# 최댓값과 최솟값을 저장할 DP 테이블 초기화
max_dp = [[-INF for _ in range(n)] for _ in range(n)]
min_dp = [[INF for _ in range(n)] for _ in range(n)]
# 자기 자신 구간의 값은 자기 자신이 최댓값이자 최솟값
for i in range(len(nums)):
max_dp[i][i] = nums[i]
min_dp[i][i] = nums[i]
# 구간의 길이를 1부터 n까지 점점 넓혀가며 확인
for interval in range(1, len(nums)): # 구간 길이
for i in range(len(nums)): # 구간 시작점
j = i + interval # 구간 끝점
if j >= len(nums):
continue
max_c = [] # 가능한 최대값 후보들
min_c = [] # 가능한 최소값 후보들
# (i ~ j) 범위에서 가능한 모든 분할 위치 k를 순회
for k in range(i+1, j+1):
op = ops[k-1] # 현재 분할에 해당하는 연산자
if op == '+':
# 덧셈: 최댓값 + 최댓값, 최솟값 + 최솟값
max_c.append(max_dp[i][k-1] + max_dp[k][j])
min_c.append(min_dp[i][k-1] + min_dp[k][j])
elif op == '-':
# 뺄셈: 최댓값 - 최솟값, 최솟값 - 최댓값
max_c.append(max_dp[i][k-1] - min_dp[k][j])
min_c.append(min_dp[i][k-1] - max_dp[k][j])
# 현재 구간의 최대/최소값 저장
max_dp[i][j] = max(max_c)
min_dp[i][j] = min(min_c)
# 전체 구간(0 ~ n-1)의 최댓값 반환
return max_dp[0][len(nums)-1]
유형 5. LCS / LIS
LCS
최장 공통 부분 수열 / 문자열 구하는 문제
-> 문자 사이를 건너뛰어 공통되면서 가장 긴 부분의 문자열을 찾으면 된다.
부분 수열이란 원래 문자열에서 문자의 순서를 유지한 채 일부 문자를 골라낸 문자열이며, 연속일 필요는 없다.
- LCS
https://www.acmicpc.net/problem/9251
import sys
def solution(a, b):
# DP 테이블 초기화: dp[i][j]는 a[0~i]와 b[0~j]까지의 LCS 길이
dp = [[0] * len(b) for _ in range(len(a))]
for i in range(1, len(a)):
for j in range(1, len(b)):
if a[i] == b[j]:
# 문자가 같으면, 이전까지의 LCS에 1을 더함
dp[i][j] = dp[i-1][j-1] + 1
else:
# 다르면, 이전까지 중 더 큰 값 선택
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[-1][-1] # 최종 LCS 길이 반환
문자열에도 똑같이 적용할 수 있다.
- LCS2
a = input()
b = input()
"""
dp로 어떻게 구할까?
2차원 배열 만들어서 겹치는 값 구하면 될듯
"""
dp = [[""] * (len(b) + 1) for _ in range((len(a) + 1))]
for i in range(1, len(a)+1):
for j in range(1, len(b) + 1):
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1] + a[i-1] # 복수 정답이라 어느쪽거 가져와도 상관 x
else:
dp[i][j] = dp[i-1][j] if len(dp[i-1][j]) > len(dp[i][j-1]) else dp[i][j-1]
print(len(dp[-1][-1]))
if len(dp[-1][-1]) != 0:
print(dp[-1][-1])
LIS
LIS(Longest increasing Subsequence)는 여기에 하나의 제약조건이 더 붙어서, 가장 긴 증가하는 부분 수열이다.
예를 들어 다음 수열이 주어지면,
3 5 7 9 2 1 4 8
전체가 오름차순인 수열이어야 하므로 3 5 7 9 / 1 4 8 이 증가하는 부분수열이고, 그 중 가장 긴 3 5 7 9가 LIS이다.
용어만 알면 풀이는 간단한데, 초기에 정렬을 해주면 된다.
- 병사 배치하기
내림차순임에 주의할 것!
https://www.acmicpc.net/problem/18353
def solution(N):
# 오름차순으로 정렬
numbers = list(map(int, input().split()))
numbers.reverse()
dp = [1] * N
# dp 리스트
for i in range(1, N):
for j in range(0, i):
if numbers[j] < numbers[i]:
dp[i] = max(dp[i], dp[j] + 1)
return N - max(dp)
N = int(input())
print(solution(N))
근데 이건 열외할 병사 (=LIS가 아닌) 병사의 수만 구하는 문제라서 이렇게 간단하게 풀린듯
- 가장 긴 증가하는 부분수열
실 골 플 다있다
- 실버 / 골드 문제
https://www.acmicpc.net/problem/11053
https://www.acmicpc.net/problem/12015
위에서 봤던 병사 구하기랑 똑같이 부분수열 길이만 구하면 된다.
- 플래티넘 문제
https://www.acmicpc.net/problem/14003
이 문제에서는 실제 부분 수열까지 구해야 한다.
이 때 주의할 점은, 골드 / 플래티넘 문제에서는 (1 ≤ N ≤ 1,000,000) 이기 때문에 위에서 썼던 O(n^2) 로는 시간 초과가 뜬다는 것이다.
이진 탐색을 활용하면 O(n log n) 으로 풀 수 있다.
- LIS의 길이만 구할 때: bisect_left를 활용해서 해결 가능 (O(n log n))
- LIS 수열까지 구하려면:
- dp 배열로 LIS 길이를 유지
- 원래 수열과의 인덱스 추적을 통해 실제 수열 재구성
import sys
import bisect
input = sys.stdin.readline
def solve():
n = int(input())
A = list(map(int, input().split()))
dp = [] # LIS를 저장하는 리스트
pos = [0] * n # A[i]가 LIS의 몇 번째 위치에 있는지를 저장
for i in range(n):
if not dp or A[i] > dp[-1]:
dp.append(A[i])
pos[i] = len(dp) - 1 # 현재 위치 저장
else:
idx = bisect.bisect_left(dp, A[i])
dp[idx] = A[i]
pos[i] = idx # 대체된 위치 저장
# LIS 수열 복원
lis_len = len(dp)
lis = []
cur = lis_len - 1
# pos 배열을 역순으로 순회하며 수열 추적
for i in range(n-1, -1, -1):
if pos[i] == cur:
lis.append(A[i])
cur -= 1
if cur < 0:
break
lis.reverse()
print(lis_len)
print(' '.join(map(str, lis)))
solve()
유형 6. knapsack 문제
정해진 무게(K) 안에서 최대의 가치를 얻는 조합을 찾는 문제.
knapsack 문제는 넣고 빼고 (0 / 1) 로만 나뉘어진다는 특징이 있다.
- 평범한 배낭
https://www.acmicpc.net/problem/12865
n, k = [int(x) for x in input().split()] # 물건 수 n, 최대 무게 k
table = [0] * (k+1) # DP 테이블 (무게별 최대 가치)
for _ in range(n):
w, v = [int(x) for x in input().split()] # 각 물건의 무게 w, 가치 v
if w > k:
continue # 배낭에 넣을 수 없는 무게는 건너뜀
# 뒤에서부터 업데이트하는 이유: 같은 아이템을 중복으로 사용하지 않기 위해!
for j in range(k, 0, -1):
if j + w <= k and table[j] != 0:
table[j + w] = max(table[j + w], table[j] + v)
# 물건 하나만 넣었을 경우도 고려해야 함 (초기화)
table[w] = max(table[w], v)
print(max(table)) # 가장 큰 가치 출력
2차원 배열이 조금 더 직관적인 것 같다.
N, K = [int(x) for x in input().split()]
dp = [[0] * (K+1) for _ in range(N+1)]
for i in range(1, N+1):
w, v = [int(x) for x in input().split()]
for j in range(1, K+1):
if j < w:
dp[i][j] = dp[i-1][j] # 못 넣는 경우
else:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)
print(dp[-1][-1])
유형 7. 최대값 / 최소값 산출
연속 등의 특정 조건 제약을 걸고, 이 제약 안에서 어떻게 하면 최대값 / 최소값을 산출할 수 있는가? 에 대한 문제이다.
굉장히 자주 보이는 유형 중 하나.
- 도둑질
https://school.programmers.co.kr/learn/courses/30/lessons/42897
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
<제약조건>
- 인접한 두 집을 털면 경보가 울린다
- 원형 배열로 구성되어 있다이 문제에서는 원형 배열이므로, 첫 번째(시작점) 스타트인지 두 번째 스타트인지가 구분되어야 한다.
def solution(money):
# 첫 번째 집부터 털 때
dp = [0] * len(money)
dp[0] = dp[1] = money[0]
for i in range(2, len(money) - 1):
# 현재 것 vs 저번 것 (인접 X이기 때문)
dp[i] = max(dp[i-1], money[i] + dp[i-2])
# 두 번째 집부터 털 때
dp2 = [0] * len(money)
dp2[1] = money[1]
for i in range(2, len(money)):
# 현재 것 vs 저번 것 (인접 X이기 때문)
dp2[i] = max(dp2[i-1], money[i] + dp2[i-2])
return max(max(dp), max(dp2))
- 퇴사
https://www.acmicpc.net/problem/14501
<제약조건>
- 상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다.
- 상담 일정표의 금액, 소요일수를 보고 상담을 적절히해서 최대수익 구하기N = int(input())
# 인덱스 1부터 시작하기 위해
dp_list = [0] * (N+1)
t_list = []; p_list = []
for _ in range(N):
t, p = map(int, input().split())
t_list.append(t)
p_list.append(p)
for i in range(N-1, -1, -1):
# 상담 불가할 경우 : 전날 거 그대로
if i + t_list[i] > N:
dp_list[i] = dp_list[i+1]
# 상담 가능할 경우
# 전날까지의 최대값 VS 현재 상담 일자의 이윤 + 현재 상담을 마친 일자부터의 최대 이윤
else:
dp_list[i] = max(dp_list[i+1], p_list[i] + dp_list[i + t_list[i]])
print(dp_list[0])
- RGB 거리
https://www.acmicpc.net/problem/1149
<제약조건>
- 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
- N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
- i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.# 시간 개빡빡하네 반복문 주의할 것
# 1번부터 N번 집
# 규칙을 만족하며 모든 집을 칠하는 비용의 최소값
# 1번 집은 2번집과 같지 않음
# N번 집은 N-1번집과 같지 않음
# i번 집은 양옆집과 같지 않음
def solution(N):
cost = []
for _ in range(N):
cost.append(list(map(int, input().split())))
for i in range(1, N):
# 다음 입력값이 R, G, B일 때 세가지로 나누어 계산
# R일 때
cost[i][0] = min(cost[i-1][1], cost[i-1][2]) + cost[i][0]
# G일 때
cost[i][1] = min(cost[i-1][0], cost[i-1][2]) + cost[i][1]
# B일 때
cost[i][2] = min(cost[i-1][0], cost[i-1][1]) + cost[i][2]
return min(cost[N-1][0], cost[N-1][1], cost[N-1][2])
N = int(input())
print(solution(N))
- 포도주
https://www.acmicpc.net/problem/2156
<제약조건>
- 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
- 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.n = int(input())
wines = [0]
dp = [0] * (n+1)
for _ in range(n):
wines.append(int(input()))
dp[1] = wines[1]
if n >= 2:
dp[2] = wines[1] + wines[2]
for i in range(3, n+1):
dp[i] = max(dp[i-1], dp[i-2] + wines[i], dp[i-3] + wines[i-1] + wines[i])
print(dp[-1])
유형 7-1. 도형에서의 최대값
2차원 평면에서의 탐색을 통해서 최대값을 산출한다.
- 정수 삼각형
https://www.acmicpc.net/problem/1932
현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는것 중 에만 선택 가능하다는 제약 조건이 있다.
# 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램
# a[i+1] = a[i-1] + max(a[i](대각선), a[i](바로 아래))
def solution(n):
# n줄만큼 배열 입력받기
# 2차원 배열 생성
arr = []
for _ in range(n):
tri = list(map(int, input().split()))
arr.append(tri)
# dp 또한 2차원 배열로 만들어줄 것
dp = [[0 for _ in range(n)] for _ in range(n)]
# 각 층의 최대값 구하기
dp[0][0] = arr[0][0]
# dp[1][0] = dp[0][0] + dp[1][0]
# dp[2][0] = dp[1][0] or dp[1][1]
#
# 바로 아래랑 대각선 확인
for i in range(1, n):
for j in range(i+1):
# 이번층과 전층 비교
# 왼쪽 대각선 없을 경우 (j == 0일 때)
if j == 0:
dp[i][j] = arr[i][j] + dp[i-1][j]
# 바로 위 없을 경우 j==n-1일 때
elif j == i:
dp[i][j] = arr[i][j] + dp[i-1][j-1]
# 다른 경우
else:
dp[i][j] = arr[i][j] + max(dp[i-1][j], dp[i-1][j-1])
# 마지막 층에서 최대값 반환
return max(dp[n-1])
print(solution(5))
https://school.programmers.co.kr/learn/courses/30/lessons/43105
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
프로그래머스 문제도 거의 동일하다.
- 구간 합 구하기
https://www.acmicpc.net/problem/11660
2차원 배열을 주고, 특정 영역 내의 합을 구하는 문제이다.
dp 역시 2차원으로 할당해야 계산이 편하다.
# x1부터 x2까지
# 2차원 dp 리스트
def solution(N, M):
graph = []
dp = [[0 for _ in range(N+1)] for _ in range(N+1)]
# dp를 하나 더 할당해서 처리
for i in range(N):
graph.append(list(map(int, input().split())))
# 구간별 합 구해놓기
for i in range(N):
for j in range(N):
# 왼쪽 and 위 - 중복 빼기 + 현재 값
dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j] - dp[i][j] + graph[i][j]
# print(dp)
for _ in range(M):
x1, y1, x2, y2 = map(int, input().split())
print(dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1])
N,M = map(int, input().split())
solution(N, M)
유형 8. 최단 경로 개수 문제
학생 때 하던 경우의 수 구하기 문제랑 다를바가 없다.
- 등굣길
https://school.programmers.co.kr/learn/courses/30/lessons/42898
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
확통 할때 경로 경우의 수 구하던 그거 그대로 하면 된다.
def solution(m, n, puddles):
dp = [[0] * m for _ in range(n)]
dp[0][0] = 1
for y in range(n):
for x in range(m):
if ([x+1, y+1] in puddles) or ((y, x) == (0,0)):
continue
dp[y][x] = (dp[y-1][x] + dp[y][x-1]) % 1000000007 # 문제 제약 조건에 있음
return dp[-1][-1]
'알고리즘 > 자료구조_알고리즘' 카테고리의 다른 글
| [코테 직전 유형 정리] - 그리디 (2) | 2025.03.22 |
|---|---|
| [코테 직전 유형별 정리] - 이분탐색 (0) | 2025.03.21 |
| [코테 직전 유형별 정리] - DFS / BFS (0) | 2025.03.21 |
| [알고리즘] 01. DFS & BFS (0) | 2023.09.11 |
| [알고리즘] 00. 자료구조 리마인드 (0) | 2023.09.11 |
