유튜브 ALGORITHM JOBS 채널에 게재된 SSAFY대비 CT 예상문제 풀이 영상을 통해 배우고 공부한 내용 정리
https://www.youtube.com/watch?v=PLAm5iAeyF8
해당 문제는 문제를 읽어보면 노골적으로 LCS라는 표현이 나오고 대학교 algorithm 강의 내용 중 Dynamic Programming part에서도 편집거리(Edit Distance)(inspired by LCS algorithm)라는 이름으로 똑같은 문제를 다뤘어서 바로 접근법을 알 수 있었다.
두 문자열이 주어졌을 때 하나를 X, 다른 하나를 Y라고 할 때 X를 Y로 바꾸는데 드는 비용이 최소가 되도록 하는게 목표이고 그 촤소 횟수를 찾는 문제이다.
대학교 강의에서는 직접 코드를 짜서 구현했지만 싸피의 CT문제는 답만 구하면 되므로 풀이 방법이 잘 생각나지 않았다.
알고리즘 잡스에서 설명하는 풀이법은 두 문자열에 대한 LCS 테이블을 완성하고 그 테이블로 부터 LCS를 계산하여 X 문자열이 LCS문자열이 되기 위해 감소하는 문자의 개수와 LCS가 Y문자열이 되기 위해 증가하는 문자의 개수를 더하게 되면 정답이 구해지는데 바로 앞서 설명한 방법을 통해 계산하는 것이다.
다음과 같이 정리할 수 있을 것이다.
알고리즘 잡스 풀이법
- LCS 테이블 그려서 LCS 구하기
- (X 문자열에서 LCS문자열이 되기 위해 감소되는 문자의 개수) + (LCS 문자열에서 Y 문자열이 되기 위해 감소되는 문자의 개수) 계산
해당 풀이법으로 계산한 풀이과정은 다음과 같다.
하지만 해당 문제를 5분안에 풀어야 되는데 테이블만 5개를 그리는 데에도 5분이 훌쩍 넘을 것 같고 문자열의 길이가 길어지면 시간은 더욱 오래걸릴 것이고 이 방법만을 사용한다면 결국 싸피에 떨어지지 않을까 하는 생각이들었다.(속도가 느린 필자의 경우)
정확도는 떨어질지 몰라도 훨씬 더 빨리 풀고자 Y로부터 X에 포함되지않는 문자들을 전부 제거하기 위해 줄을 그어 표시해두고 나머지 필요한 문자열들을 추가한 뒤 이 과정을 부터 발생한 횟수를 count해서 구했다.
