알고리즘 문제 풀다 보면 해설에서 "이건 투 포인터로 풀면 된다" "슬라이딩 윈도우 패턴이다" 이런 말이 자주 나오는데, 정작 제가 새 문제를 만나면 이게 그 패턴인지 감지가 안 돼요. 그냥 이중 for문으로 다 돌려보다가 시간 초과 나고 나서야 아 이거였구나 하는 식이라서요.
제가 이해하기론 이런 느낌인데 맞나요?
투 포인터 : 정렬된 배열에서 양쪽 끝(또는 좌우)에서 좁혀가는 느낌
슬라이딩 윈도우 : 연속된 구간의 합이나 길이를 다룰 때 창을 밀면서
근데 막상 문제 보면 둘이 겹치는 것 같기도 하고 헷갈려요. 예를 들어 "합이 특정 값 이상인 가장 짧은 연속 부분 배열" 같은 건 슬라이딩 윈도우인 것 같은데, 두 포인터가 창의 양 끝이라고 볼 수도 있잖아요? 그럼 이건 투 포인터인가요 슬라이딩 윈도우인가요? 사실상 같은 거 아닌가 싶기도 하고요.
문제 지문에서 "아 이건 투 포인터겠구나" "이건 슬라이딩 윈도우겠구나" 하고 딱 알아채는 키워드나 신호 같은 게 있을까요? 매번 O(n^2)로 짜다가 갈아엎는 게 너무 비효율적이라 패턴 잡는 법을 익히고 싶어요.