알고리즘 썸네일형 리스트형 Dynamic Programming 5: DP 배열 설정의 중요성 (백준 14238, 17404, 12969번) 백준 14238번: 출근 기록 문제 설정은 간단하다. 각 알파벳 A, B, C에 대해서 아래 조건을 금방 파악할 수 있다. 그렇지만 문제 조건을 잘 파악했다 하더라도 다음이 문제다. 기존 문제처럼 dp 배열이 1차원 또는 2차원이라고 가정하고 접근해보자. DP 배열이 1차원이라면? dp[n] = V : 길이가 n인 문자열 중 올바른 출근 기록인 경우의 수(또는 문자열들의 배열?) 점화식을 세울 때 dp[n]과 dp[n-1] 사이 관계를 어떻게 정의할 수 있는가? 길이가 n-1인 문자열 오른쪽 끝에 A를 추가했을 때, B를 추가했을 때 그리고 C를 추가했을 때 매번 기존 문자열의 끝에 어떤 문자가 오느냐에 따라 추가할 수 있는지 없는지가 달라진다. 또는 dp[n]에 길이가 n인 가능한 모든 문자열들을 배열.. 2023. 4. 3. 14:21 ㆍ 알고리즘과 자료구조/Dynamic Programming Dynamic Programming 5: DP 배열 설정의 중요성 (백준 14238, 17404, 12969번 파이썬) 백준 14238번: 출근 기록 문제 설정은 간단하다. 각 알파벳 A, B, C에 대해서 아래 조건을 금방 파악할 수 있다. 그렇지만 문제 조건을 잘 파악했다 하더라도 다음이 문제다. 기존 문제처럼 dp 배열이 1차원 또는 2차원이라고 가정하고 접근해보자. DP 배열이 1차원이라면? dp[n] = V : 길이가 n인 문자열 중 올바른 출근 기록인 경우의 수(또는 문자열들의 배열?) 점화식을 세울 때 dp[n]과 dp[n-1] 사이 관계를 어떻게 정의할 수 있는가? 길이가 n-1인 문자열 오른쪽 끝에 A를 추가했을 때, B를 추가했을 때 그리고 C를 추가했을 때 매번 기존 문자열의 끝에 어떤 문자가 오느냐에 따라 추가할 수 있는지 없는지가 달라진다. 또는 dp[n]에 길이가 n인 가능한 모든 문자열들을 배열.. 2023. 3. 29. 17:29 ㆍ 알고리즘과 자료구조/Dynamic Programming 이전 1 다음
