Dp

백준 9251번 바로가기 나의 풀이 # 입력 import sys read = sys.stdin.readline A, B = read().strip(), read().strip() n, m = len(A), len(B) LCS = [[0] * (m + 1) for _ in range(n + 1)] # 처리 - LCS 알고리즘 이용 for i in range(1, n + 1): for j in range(1, m + 1): if A[i - 1] == B[j - 1]: LCS[i][j] = LCS[i - 1][j - 1] + 1 else: LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1]) print(LCS[n][m]) CODE REVIEW 백준 17218번 문제에서 배운 LCS 알고리즘을 이용한 문제. 17218번은 이 문제의 문자열 ver. 변형이라고 볼 수 있다. (n*m) matrix에 경로찾기처럼 숫자를 더해나가며 채워가면 최장 공통 부분 수열의 최대 길이는 마지막 요소에 저장된다. REFERENCES 그림으로 이해하는 LCS 알고리즘

백준 번 바로가기 첫 번째 풀이 # 입력 import sys read = sys.stdin.readline A, B = read().strip(), read().strip() n, m = len(A), len(B) LCS = [[0] * (m + 1) for _ in range(n + 1)] LCS2 = [[''] * (m + 1) for _ in range(n + 1)] # 처리 - LCS 알고리즘 이용 for i in range(1, n + 1): for j in range(1, m + 1): if A[i - 1] == B[j - 1]: LCS[i][j] = LCS[i - 1][j - 1] + 1 LCS2[i][j] = LCS2[i - 1][j - 1] + A[i-1] else: LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1]) if LCS[i-1][j] > LCS[i][j-1]: LCS2[i][j] = LCS2[i-1][j] else: LCS2[i][j] = LCS2[i][j-1] print(LCS[n][m]) print(LCS2[n][m]) 두 번째 풀이 # 입력 import sys read = sys.stdin.readline A, B = read().strip(), read().strip() n, m = len(A), len(B) LCS = [[0] * (m + 1) for _ in range(n + 1)] # 처리 - LCS 알고리즘 이용 for i in range(1, n + 1): for j in range(1, m + 1): if A[i - 1] == B[j - 1]: LCS[i][j] = LCS[i - 1][j - 1] + 1 else: LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1]) print(LCS[n][m]) ans = '' x, y = n, m while x > 0 and y > 0: if LCS[x][y] == LCS[x - 1][y]: x -= 1 elif LCS[x][y] == LCS[x][y - 1]: y -= 1 else: ans += A[x-1] x -= 1 y -= 1 print(ans[::-1]) CODE REVIEW 백준 9251번 - LCS의 연장선 격인 문제. 첫 번째 풀이의 경우 시간초과 에러가 발생했는데, string을 저장하는 과정 자체가 시간이 오래 소요되는 것으로 판단된다. 두 번째 풀이에서는 LCS2 matrix을 사용하지 않고, LCS을 그대로 사용하면서 역추적 해나가는 방식을 택했다. 역추적 해가면서 대각선으로 움직이는 시점의 문자를 더해가며 문자열을 찾아낼 수 있다.

백준 9461번 바로가기 나의 풀이 # 입력 import sys read = sys.stdin.readline arr = [1,1,1,2,2] + [0]*100 # 처리 for i in range(99): arr[i+5] = arr[i+4] + arr[i] for _ in range(int(read().strip())): print(arr[int(read().strip())-1]) CODE REVIEW 규칙이 잘 안보이길래 n이 1부터 12일 때까지 P(N)값을 구해놓고 규칙을 찾아보았다. 점화식으로 $a_{n+5} = a_{n+4} + a_{n}$ 과 같다. 여러 번 불러와야 하므로 105개 정도의 요소를 가진 arr을 미리 구해놓는게 빠르다.

백준 2491번 바로가기 나의 풀이 # 입력 n = int(input()) arr = list(map(int,input().split())) sml2big = [1]*n big2sml = [1]*n # 처리 def find_max(data, dp): for i in range(n-1): if data[i] <= data[i+1]: dp[i+1] = dp[i] + 1 return max(dp) print(max(find_max(arr,sml2big),find_max(arr[::-1], big2sml))) CODE REVIEW dp를 이용한 문제. data[i]와 data[i+1]을 비교해서 크거나 같으면 count를 추가해주면 된다. 주어진 array를 뒤집으면 작거나 같다가 크거나 같다가 되기 때문에 함수 하나를 만들어놓고 arr과 arr[::-1]을 각각 입력했다. arr을 2차원, 3차원으로 확장하면 재밌는 문제를 만들어낼 수 있을 것 같다.

백준 1463번 바로가기 나의 풀이 n = int(input()) dp = [0]*1000001 for i in range(1,n+1): dp[i] = dp[i-1] + 1 if i%2==0: dp[i] = min(dp[i],dp[i//2]+1) if i%3==0: dp[i] = min(dp[i],dp[i//3]+1) print(dp[n]-1) CODE REVIEW 문제 자체는 간단하지만 발상이 어려웠던 문제. 한번에 해결하지는 못하고, n에서 1로 내려오는 대신 1에서 n으로 접근하는 방식을 활용해보라는 힌트를 가지고 문제를 해결했다. 직접 1부터 나아가는 그래프를 그려봤는데(위의 사진 참고!) 처음에는 nums라는 dict을 만들어서 if nums in dict: pass else: nums[n]=count라는 식으로 나아갈려고 했는데, 이게 생각보다 고려할게 많아져서 포기했다. 아예 새로 코드를 짜서 문제를 해결했다. for문 안의 순서가 (+1, *2, *3) 순서인데, 3배하는 것이 최소일 확률이 높아서 그렇게 했다. index와 num을 서로 동일하게 맞추기 위해 dp = [0]*1000001으로 맞춘건 이젠 익숙하다.