📖 What I Learned...
4주차 키워드 :
동적 프로그래밍,그리디 알고리즘
동적 프로그래밍 (Dynamic Programming)
(1) 최적 부분 구조 (Optimal Substructure)
- 부분 문제들의 최적의 답을 이용해 기존 문제의 최적의 답을 구할 수 있음
(2) 중복되는 부분 문제 (Overlapping Subproblems)
- 그런 부분 문제가 여러 번 반복될 때
- 백준 9084 동전
2원, 3원으로 6원을 만든다고 할 때의 경우의 수는 2원으로 6원을 만드는 <경우의 수 + 3원으로 6원을 만드는 경우의 수>다. 그래서 동전의 종류마다 반복문을 돌면서 table의 값을 갱신해주면 된다!
for coin in coins:
for i in range(coin, goal+1):
table[i] += table[i-coin]-
백준 9251 LCS
가장 긴 공통적인 부분 수열(Longest Common Subsequence) 문제! 점화식을 떠올리기가 굉장히 어려웠다..ㅎ
📌 각각 길이가 i, j인 문자열 와 가 있을 때 lcs[i][j] 테이블은 , 의 공통적인 부분 수열의 최대 길이를 뜻함
📎 길이가 0인 문자열과의 lcs는 항상 0이다.
📎 ==라면 lcs[i][j] = lcs[i-1][j-1] + 1
📎 != 라면 lcs[i][j] = max(lcs[i-1][j] + 1, lcs[i][j-1]) -
백준 12865 아주 평범한 배낭
동전이랑 유사한 방식으로 풀면 된다. 코드는 아래에...
import sys
n, k = map(int, sys.stdin.readline().split()) # 물품의 수, 버틸 수 있는 무게
items = [[0]] # 물품 정보
for _ in range(n):
items.append(list(map(int, sys.stdin.readline().split()))) # 물건 무게, 물건 가치 순서로 저장
table = [[0 for _ in range(k+1)] for _ in range(n+1)] # table[i][j] : i는 아이템, j는 배낭 무게
for i in range(1, n+1):
weight, value = items[i]
for j in range(1, k+1):
table[i][j] = table[i-1][j] # 일단 지금 아이템을 선택하지 않았다고 간주
if j >= weight and table[i-1][j-weight] + value > table[i][j]: # 만약 지금 아이템을 선택했을 때가 선택하지 않았을 때보다 가치가 더 크다면 선택
table[i][j] = table[i-1][j-weight] + value
print(table[n][k]) import sys
n = int(sys.stdin.readline()) # 행렬의 개수
matrix = []
table = [[0 for _ in range(n)] for _ in range(n)] # table[i][j] : i~j번째 행렬을 곱하는 연산 횟수 최솟값
for _ in range(n):
matrix.append(list(map(int, sys.stdin.readline().split())))
for gap in range(1, n): # gap (서로 곱하는 행렬 사이에 몇 개의 행렬이 더 있는가)
for i in range(n - gap): # table 2차원 행렬의 행 값
j = i + gap # 2차원 행렬 table의 열 값
if gap == 1:
table[i][j] = matrix[i][0] * matrix[i][1] * matrix[j][1]
continue
table[i][j] = 2 ** 32
for k in range(i, j):
table[i][j] = min(table[i][j], table[i][k] + table[k+1][j] + matrix[i][0] * matrix[k][1] * matrix[j][1])
print(table[0][n-1])그리디 알고리즘
(1) 최적 부분 구조 (Optimal Substructure)
- 부분 문제들의 최적의 답을 이용해 기존 문제의 최적의 답을 구할 수 있음
(2) 탐욕적 선택 속성 (Greedy Choice Property)
- 각 단계에서 탐욕스러운 선택이 최종 답을 구하기 위한 최적의 선택임을 증명해야 함
-
백준 1541 잃어버린 괄호
import re를 처음으로 사용한 문제다. 여러 문자를 기준으로 문자열을 split하고 싶을 때는re.split('[+-]', string)을 사용하면 되고, 결과물로 delimeter까지 포함하고 싶다면re.split('[+|-]', string)을 사용하면 된다. (참고)
풀이 방법은 문자열에서 '-'를 만났을 때 이후의 숫자들은 모두 빼주면 끝이다.
What I Realized...
DP는 아무래도 연습을 더 많이 해야할 것 같다. 점화식만 떠올릴 수 있다면 아주 빠르게 풀 수 있는 문제인 것 같은데, 그걸 떠올리기가 쉽지 않다는 점ㅎ 아주 많이 깨닫고 간다. 이제 알고리즘 위크가 끝나고 C로 넘어가게 될텐데 이게 맞는건지는 잘 모르겠다. 아직 공부해야 할 것들이 남아있는데 그걸 제치고 다른 단계로 넘어간다는 게 익숙하지 않지만, 직면한 것들에 집중해보자. (그렇다고 해서 알고리즘을 놓겠다는 소리는 아님)
