코드 작성 전에 올바른 DSA 패턴을 식별하는 방법
Source: Dev.to
Introduction
사람들이 DSA를 어떻게 더 잘할 수 있냐고 물을 때 보통 다음과 같은 조언을 합니다:
“문제를 더 많이 풀어라.”
이는 틀린 말은 아닙니다. 저에게 가장 큰 차이를 만든 것은 코드를 생각하기도 전에 패턴을 빨리 식별하는 방법을 배우는 것이었습니다. 이 부분을 어느 정도 잘하게 되면 나머지 문제는 스스로 풀려 나갑니다.
Signals to Look For
전체 이야기를 머리속에 먼저 떠올리지는 않습니다. 대신 몇 가지 아주 구체적인 신호를 찾습니다:
- 어떤 종류의 입력이 주어졌는가?
- 시간·공간 제약은 무엇인가?
- 출력이 정확히 무엇을 요구하고 있는가?
이 세 가지만으로도 대부분의 선택지를 아주 빠르게 배제할 수 있습니다.
Typical cues and associated patterns
- 정렬된 배열 + 쌍/부분 배열 찾기 + O(n) 기대 → two‑pointers 혹은 sliding window.
- 문제가 구간을 요구하고, 누적값을 언급하며, 부분 배열에 대한 개수·합을 원한다 → prefix sums와 hashing.
- 입력 크기가 크고 답 공간이 단조롭다 → binary search (배열이 아니라 답 자체에 대해 이진 탐색하는 경우가 많음).
Invariants
제가 더 신경 쓰는 것은 입력을 진행하면서 반드시 유지되어야 하는 조건입니다. 이것이 보통 불변식(invariant) 입니다.
불변식을 끌어내기 위한 질문 예시:
- 탐색 공간을 축소하고 있는가?
- 유효한 윈도우를 유지하고 있는가?
- 무언가를 단조롭게 누적하고 있는가?
- 진행하면서 옵션을 제거하고 있는가?
불변식을 한 문장으로 말할 수 있게 되면 패턴이 보통 바로 떠오릅니다.
Workflow
제가 믿게 된 특정한 느낌이 있습니다. 처음 몇 분 안에 불변식을 말할 수 있다면, 아직 모든 엣지 케이스를 몰라도 올바른 방향에 있다는 것을 알 수 있습니다.
- 그 말을 할 수 없으면, 속도를 늦춥니다. 이는 통찰을 얻으려 애쓰다 보니 무리하게 브루트포스로 접근하고 있다는 신호입니다.
From thought to code
예전에는 코드를 바로 작성하곤 했는데, 그 결과는 보통:
- 논리가 엉망이 되고
- 되돌아가야 하며
- 설명이 불명확해졌습니다
이제는 불변식을 영어로 설명할 수 없으면 에디터를 열지 않습니다.
패턴이 명확해지면:
- 루프 구조가 바로 보이고
- 포인터 이동 결정이 이해되며
- 복잡도가 거의 자명해집니다
코드는 구현 세부 사항이 될 뿐, 핵심 작업이 아닙니다.
Conclusion
이러한 사고 방식—제약을 먼저, 불변식을 두 번째, 코드를 마지막—은 제가 점점 더 체계적으로 문서화하려는 방향입니다. 엄격한 규칙이라기보다 DSA를 덜 무작위적이고 더 구조적으로 느끼게 하는 방법이죠.
저는 패턴과 그 패턴을 가리키는 신호들을 한 곳에 정리하고 있습니다(indexedcode.com), 주로 제 자신을 위한 참고용입니다. 여기서 글을 쓰는 것이 그 사고를 다듬는 데 도움이 됩니다.
다음 글에서는 난이도 라벨(쉬움/보통/어려움)이 왜 종종 오해를 불러일으키는지, 그리고 학습할 때 왜 해가 될 수 있는지에 대해 파고들고 싶습니다.
패턴 인식이 지금은 흐릿하게 느껴진다면, 그것은 정상입니다. 그리고 어느 순간 깨달음이 오면, 문제를 푸는 방식이 이전과 다르다는 것을 느낄 겁니다: 처음엔 느리지만, 장기적으로는 훨씬 빠르게 해결하게 됩니다.