백준 5582번 '공통 부분 문자열' 파이썬(Python) / 투 포인터, DP

https://www.acmicpc.net/problem/5582 난이도 : 골드5 문제를 푸는 2가지 방법 5582번 문제는 교육적으로 상당히 좋은 문제라고 생각한다. 나는 이 문제를 2가지 방법으로 풀어보았다. 1) 슬라이딩 윈도우(sliding window) 2) DP 메모리 제한이 256MB로 빡빡하여 2번도 pypy3으로만 통과했지만, 문제 풀이를 잘 익혀두면 좋을 문제라 생각한다!

문제 설명 문제는 간단하다. 두 문자열에서, 가장 긴 일치하는 부분 문자열의 길이를 구하면 된다.

정답=5 문제 풀이 - 투 포인터(Two Pointers) 슬라이딩 윈도우(Sliding Window) 문제 풀이를 보기 전에, 슬라이딩 윈도우의 개념에 대해 먼저 보도록 하자. 슬라이딩 윈도우 알고리즘에서는 고정된 크기의 윈도우가 움직인다.

이전의 윈도우와 이후의 윈도우에서 공유되는 값이 있기 때문에, 이를 활용할 수 있는 문제에서 쓰면 좋다. 이번 문제에서 쓴 투 포인터(Two Pointers)...