2748. 피보나치 수 2
https://www.acmicpc.net/problem/2748
동적 프로그래밍의 기초가 되는 문제로 하향식과 상향식 동적 프로그래밍을 이용한 풀이 방법이 존재한다. 메모이제이션을 사용하기 위한 DP 테이블을 생성하여 계산 결과를 저장하였다.
하향식 동적 프로그래밍을 이용한 풀이
import sys
sys.stdin = open("2748_피보나치 수 2.txt", "r")
input = sys.stdin.readline
N = int(input())
# 메모이제이션을 위해 DP 테이블 초기화
dp = [0] * 100
# 하향식 동적 프로그래밍
def fibonacci(num):
if num == 0 or num == 1:
return num
# 계산 결과가 저장 되있는 경우 저장된 결과 출력
if dp[num] != 0:
return dp[num]
# 계산 결과가 저장되지 않았다면 점화식에 따라서 결과 반환
dp[num] = fibonacci(num - 2) + fibonacci(num - 1)
return dp[num]
print(fibonacci(N))상향식 동적 프로그래밍을 이용한 풀이
import sys
sys.stdin = open("2748_피보나치 수 2.txt", "r")
input = sys.stdin.readline
N = int(input())
# DP 테이블 초기화
dp = [0] * 100
dp[1] = 1
dp[2] = 1
for i in range(3, N + 1):
dp[i] = dp[i - 2] + dp[i - 1]
print(dp[N])1904. 01타일
https://www.acmicpc.net/problem/1904
N이 증가함에 따라 00과 1의 타일로 표현 가능한 2진수의 경우의 수는 피보나치 수열이다. 2748. 피보나치 수 2와 비슷하지만 주어진 N의 범위가 크기 때문에 제출하면서 시간 초과와 메모리 초과가 발생하였다. 15746으로 나눈 나머지 값을 DP 테이블에 저장함으로써 메모리 초과를 해결할 수 있었다.
import sys
sys.stdin = open("1904_01타일.txt", "r")
input = sys.stdin.readline
N = int(input())
dp = [0] * 1000001
dp[1] = 1
dp[2] = 2
for i in range(3, N + 1):
dp[i] = (dp[i - 2] + dp[i - 1]) % 15746
print(dp[N])9251. LCS
https://www.acmicpc.net/problem/9251
주어진 두 수열의 가장 긴 공통 부분 수열(Longest Common Subsequence)의 길이를 구하는 문제이다.
import sys
sys.stdin = open("9251_LCS.txt", "r")
input = sys.stdin.readline
seq1 = input().rstrip()
seq2 = input().rstrip()
dp = [[0] * (len(seq2) + 1) for _ in range(len(seq1) + 1)]
for i in range(1, len(seq1) + 1):
for j in range(1, len(seq2) + 1):
if seq1[i - 1] == seq2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
print(dp[-1][-1])아직 이해가 부족한 것 같다. 다시 천천히 보며 이해할 예정.
9252. LCS 2
https://www.acmicpc.net/problem/9252
9251번 LCS와 유사한 문제이지만 요구하는 출력값의 형태가 다르다. 출력하는 코드만 고치면 되지 않을까 생각했지만 반복문을 구성하는 과정에서 다소 차이가 있었다.
import sys
sys.stdin = open("9252_LCS 2.txt", "r")
input = sys.stdin.readline
seq1 = input().rstrip()
seq2 = input().rstrip()
dp = [[""] * (len(seq2) + 1) for _ in range(len(seq1) + 1)]
for i in range(1, len(seq1) + 1):
for j in range(1, len(seq2) + 1):
if seq1[i - 1] == seq2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + seq1[i - 1]
else:
if len(dp[i][j - 1]) > len(dp[i - 1][j]):
dp[i][j] = dp[i][j - 1]
else:
dp[i][j] = dp[i - 1][j]
result = dp[len(seq1)][len(seq2)]
print(len(result))
print(result)11053. 가장 긴 증가하는 부분 수열
https://www.acmicpc.net/problem/11053
import sys
sys.stdin = open("11053_가장 긴 증가하는 부분 수열.txt", "r")
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
dp = [1 for _ in range(N)]
for i in range(N):
for j in range(i):
if A[i] > A[j]:
dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))12865. 평범한 배낭
https://www.acmicpc.net/problem/12865
import sys
sys.stdin = open("12865_평범한 배낭.txt", "r")
input = sys.stdin.readline
N, K = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
arr.insert(0, [0, 0])
# DP 테이블 초기화
dp = [[0] * (K + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
for j in range(1, K + 1):
if j >= arr[i][0]:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - arr[i][0]] + arr[i][1])
else:
dp[i][j] = dp[i - 1][j]
print(dp[N][K])제목과 다르게 전혀 평범하지 않다. 아직 이해하기 어려운 문제.
11049. 행렬 곱셈 순서
https://www.acmicpc.net/problem/11049
import sys
sys.stdin = open("11049_행렬 곱셈 순서.txt", "r")
input = sys.stdin.readline
N = int(input())
matrix = [list(map(int, input().split())) for _ in range(N)]
dp = [[0 for _ in range(N)] for _ in range(N)]
# 행렬의 행과 열의 거리가 x인 칸까지
for x in range(1, N):
# 행과 열의 번호가 i부터
for i in range(N - x):
j = i + x
# 문제에서 주어진 최대값 입력
dp[i][j] = 2 ** 31
# 두 행렬의 곱에서 나오는 추가 비용을 계산하여 더하기
for k in range(i, j):
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + matrix[i][0] * matrix[k][1] * matrix[j][1])
print(dp[0][N - 1])보류
