필요한 선형 패턴을 찾기 위해 물어볼 질문들

Source: Dev.to

Pattern‑selection cheat sheet

아래는 패턴 선택 치트 시트입니다.
각 패턴마다 문제를 읽으면서 아래 질문들을 스스로에게 물어보세요.
답이 YES이면 해당 패턴이 정답일 가능성이 높습니다.

1. Sliding Window (Fixed Size)

Ask these questions:

• 문제에서 정확히 길이 k인 부분 배열/부분 문자열을 다루고 있나요?
• 크기 k인 모든 윈도우에 대해 (합, 최대값, 개수 등) 어떤 값을 계산해야 하나요?
• 완전 탐색이면 O(n·k) 가 되는데, O(n) 으로 개선해야 하나요?

Trigger words: “window of size k”, “consecutive k elements”, “substring length k”

2. Sliding Window (Variable Size)

Ask these questions:

• 윈도우 크기가 고정되지 않고 어떤 조건에 의해 제한되나요?
• 조건을 만족하는 가장 작은 / 가장 큰 부분 배열을 찾고 있나요?
• 오른쪽을 확장하고 왼쪽을 축소할 수 있나요?

Trigger words: “at most k”, “at least k”, “minimum window”, “longest substring”

3. Two Pointers (Same Direction)

Ask these questions:

• 두 개의 인덱스로 왼쪽 → 오른쪽으로 배열을 순회하고 있나요?
• 한 포인터가 다른 포인터를 추격하고 있나요?
• 배열 안에서 구간(range) 을 유지하고 있나요?

Trigger words: “subarray”, “range”, “continuous segment”

4. Two Pointers (Opposite Ends)

Ask these questions:

• 배열이 정렬되어 있나요?
• 조건을 만족하는 쌍(pair) 을 찾고 있나요?
• 비교 결과에 따라 left++ 또는 right— 로 이동할 수 있나요?

Trigger words: “pair sum”, “target”, “sorted array”

5. Fast & Slow Pointers (Cycle Detection)

Ask these questions:

• 링크드 리스트 혹은 포인터 구조가 등장하나요?
• 사이클 / 루프 가 존재할 가능성이 있나요?
• 한 포인터가 다른 포인터보다 2배 빠르게 움직일 수 있나요?

Trigger words: “cycle”, “loop”, “circular”, “duplicate via index jump”

6. Prefix Sum

Ask these questions:

• 구간 합을 반복해서 구해야 하나요?
• 문제에 부분 배열 합이 k와 같은 경우가 등장하나요?
• 누적 합을 이용하면 도움이 될까요?

Trigger words: “range sum”, “subarray sum”, “sum between i and j”

7. Difference Array

Ask these questions:

• 다중 구간 업데이트가 있나요?
• 구간에 대해 증가/감소 연산을 적용해야 하나요?
• 최종 값만 중요하고 중간 값은 필요 없나요?

Trigger words: “range update”, “apply operations”, “add x from l to r”

8. Hash Map Frequency Counting

Ask these questions:

• 원소/문자의 빈도를 세고 있나요?
• 상수 시간 조회가 필요하나요?
• 순서보다는 개수가 더 중요하나요?

Trigger words: “frequency”, “count occurrences”, “anagram”

9. In‑place Modification

Ask these questions:

• 추가 공간을 사용하지 말라는 제약이 있나요?
• 배열을 수정해도 괜찮나요?
• 결과를 같은 배열 안에 저장해야 하나요?

Trigger words: “in‑place”, “O(1) space”, “modify input”

10. Sorting‑based Pattern

Ask these questions:

• 정렬을 하면 로직이 크게 단순화되나요?
• 쌍이나 구간을 매칭해야 하나요?
• 순서를 바꿔도 정답에 영향을 주지 않나요?

Trigger words: “after sorting”, “arrange”, “reorder”

11. Cyclic Sort

Ask these questions:

• 숫자들이 1…n 범위에 있나요?
• 각 숫자가 특정 인덱스에 있어야 하나요?
• 누락 / 중복된 원소를 찾고 있나요?

Trigger words: “missing number”, “duplicate”, “1 to n”

12. Kadane’s Algorithm (Max Subarray)

Ask these questions:

• 최대 합 부분 배열을 구해야 하나요?
• 음수 합이 문제를 일으키나요?
• 합이 음수가 될 때마다 초기화할 수 있나요?
• 다수 요소가 존재한다는 가정을 할 수 있나요?
• O(1) 공간으로 해결해야 하나요?

Trigger words: “majority element”, “more than half”

20. Reservoir Sampling

Ask these questions:

• 데이터가 스트리밍 / 무한 형태인가요?
• 미리 n을 알 수 없나요?
• 균등한 무작위 샘플이 필요하나요?

Trigger words: “stream”, “random sample”, “unknown size”