https://leetcode.com/problems/longest-common-subsequence/description/

Just a moment...Just a moment...leetcode.com

이 문제를 풀었음.

"abcde" , "ace"가 있을 때 가장 긴 common subseq가 "ace" 라서 길이 3을 찾는 문제.


처음에 좀 헤메다가, dp문제라는 걸 알고 있긴 해서 2차원 dp로 풀었음.


내가 푼 방법은 


이런식으로 행과 열에서 각 알파벳 값이, 해당 값까지만 문자열에서 사용한다고는 표기일 때, 

빨간색 동그라미의 경우, "a"와 "a"를 비교하는데 값에 해당하는 두 알파벳이 같으니까, 값으로 1을 채울 수 있음.

두번째 동그라미인 경우, "c"와 "c"가 같은 상황이기 때문에, 대각선 위의 값 "ab"와 "a"를 비교했을 때 가장 길었던 subseq에서 1을 더한 2가 나옴.

이렇게 하기 위서는 첫번째 동그라미에서도 "a"와 "a"가 같은 상황에서 대각선 위의 " ", " " 를 비교한 0에서 1을 더했다고 볼 수 있음.


마름모의 경우에는 "abc"와 "ace"를 비교하는데, 이 때도 "c"와 "e"가 다르기 때문에, 

"abc"와 "ac"를 비교하는 문제, "ab"와 "ace"를 비교하는 문제의 sub-problem으로 나뉘고 이 중에 더 큰 값을 가져옴.


이걸 반복하다보면 결국엔 마지막 칸을 채울 수 있고 이 값을 가져오면 답은 3을 가져오게 됨.


내가 유튜브에서 본 풀이는 이거였음. 여기서는 행과 열에서의 각 알파벳 값이, 해당 값부터 문자열에서 사용한다는 표기임.

p1에서 출발한다고 가정했을 때, 이 때는 "a"와 "a"가 같으니까 "bcde"와 "ce"를 비교하는 subproblem으로 가기 위해 대각선으로 이동함.

그래서 s2에 도달하면 s2는 "b"와 "c"가 다르기 때문에 2개의 subproblem으로 나눠질 수 있음.

첫번째는 오른쪽으로 이동해서 "cde"와 "ce"를 비교하는 문제, 두번째는 아래로 이동해서 "e"와 "bcde"를 비교하는 문제 중 더 큰 값을 구해서 s2에 채워줌.

이런 식으로 쭉쭉 내려가다보면 결국엔 "e", "e"가 만나는 칸에 도착하게 되는데, 이 때는 답이 1임을 알 수 있음.

이렇게 "e", "e"가 만나는 칸부터 1로 채우고 뒤로 돌아가면서 푸는 방식을 봣음.



분명히 내가 떠올린건데 1번인데, 설명을 들어보면 2번식으로 bottom-up으로 푸는 게 더 직관적이라는 생각이 들었음.
물론 둘 다 그냥 dp 테이블 채우는 반복문으로 풀긴 했음.

혹시 이 둘 중에 어느 방법이 더 낫다거나, 실전에서 더 다양하게 사용할 수 있다는 게 있음? 예를 들면 bottom-up으로 푸는 게 더 실수를 줄일 수 있다거나?
암튼 쉬운 문제지만 공들여서 봐보니까 재밌네ㅇㅇ