빠른 흐름

1. 입력 크기와 시간 제한을 본다
2. 값 범위와 자료형을 정한다
3. 정렬 여부, 중복 여부, 그래프 조건을 표시한다
4. 가능한 복잡도 후보를 좁힌다
5. 엣지케이스를 먼저 적고 구현한다
6. 예제보다 작은 직접 케이스로 검산한다

입력 읽기

문제 풀이의 첫 단계는 아이디어를 떠올리는 것이 아니라 제약 조건을 숫자로 읽는 것입니다.

예를 들어 n = 100,000인데 모든 쌍을 비교하는 방식은 거의 항상 위험합니다. 반대로 n = 20이면 비트마스크로 모든 부분집합을 보는 방식이 후보가 될 수 있습니다.

먼저 완전 탐색을 세운다

바로 최적화를 떠올리기보다 가장 단순한 완전 탐색을 먼저 세우면 문제의 상태가 보입니다.

모든 후보를 만든다
각 후보가 조건을 만족하는지 검사한다
가장 좋은 값을 갱신한다

그 다음 병목을 찾습니다. 후보 생성이 너무 많은지, 검사 비용이 큰지, 같은 계산을 반복하는지를 보면 정렬, 해시, DP, 그래프 탐색 같은 도구가 왜 필요한지 드러납니다.

알고리즘 후보

중요한 것은 이름을 외우는 것이 아니라 문제 조건과 후보 알고리즘의 전제가 맞는지 확인하는 것입니다. 이진 탐색은 정렬 또는 단조성이 있어야 하고, BFS 최단 경로는 간선 비용이 같을 때 자연스럽습니다.

엣지케이스

구현 전에 아래 케이스를 짧게 적어두면 디버깅 시간을 줄일 수 있습니다.