1. 문제 2. 접근 방법 다이나믹 프로그래밍 문제이다. 이틀에 걸쳐 다양한 접근 방법을 생각해보았으나, 결국 내 능력의 한계로 풀지 못해서 답을 봐야만 했다. 나에게 좌절감을 안겨준 문제이자, 동시에 자극을 준 문제이기도 하다. (더 열심히 해야겠다!) 어쨌든... 접근 방법은 다음과 같다. 위와 같이, 비교 대상인 두 문자를 각각 행과 열로 가지는 배열을 생성한다. 여기에서는 각 시작 문자 앞에 '0' 을 추가하여 0번 행과 열은 모두 0의 값을 가지게 한다. (계산을 위함) 그 후, Z의 순서로 계산을 해나가면 되는데, i행 j열의 계산 방법은 다음과 같다. (1) 행과 열의 문자가 일치할 경우 = 좌 대각선 위의 값 + 1 → 문자가 일치하므로, 이전까지의 LCS에 1을 더하기 위함이다. 즉, 이..

1. 문제 2. 문제 풀이 다이나믹 프로그래밍 (DP) 문제이다. 현재의 상태를 저장시켜서 이를 지속적으로 활용하는 다이나믹 프로그래밍의 특성에 맞춰, 다음과 같은 문제 풀이 접근 방법을 활용하였다. '각각의 계단에 대해서, 이전 계단을 선택하는 경우와, 이전의 이전 계단을 선택하는 경우를 계산해나간다.' 즉, 각 계단에 대해서 다음의 알고리즘을 반복하는 것이다. (1) 이전 계단을 선택하는 경우, 이전 계단의 상태 중에서 '이전 계단을 선택하지 않았던 상태'를 선택할 수 있다. -> 이전 계단 중에서, '이전 계단을 선택했던 경우'를 선택하면 연속해서 세 계단을 오른 경우이므로 선택 불가 (2) 이전의 이전 계단을 선택하는 경우, 이전의 이전 상태 중 더 큰 값을 선택한다. -> 이전의 이전 계단의 경..