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

입력 읽기

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

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

가능할 때 완전 탐색을 세운다

입력이 모두 주어지고 후보를 나열할 수 있다면, 바로 최적화를 떠올리기보다 가장 단순한 완전 탐색을 기준선으로 세우면 문제의 상태가 보입니다.

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

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

입력: 시작 정점과 인접 리스트
출력: 도달 가능한 정점 수
상태: queue, visited, count
불변 조건: queue에 들어간 정점은 이미 visited
절차: 하나를 꺼내고 아직 방문하지 않은 이웃을 넣는다

이 정도 의사코드가 서면 함수 시그니처와 자료구조가 자연스럽게 정해집니다. 한 단계 처리의 책임이 길어지면 이웃 열거, 조건 검사, 상태 갱신을 작은 함수로 분리하되 문제보다 추상화를 크게 만들지 않습니다.

입력이 스트리밍으로 오거나, 질의와 갱신이 번갈아 오거나, 출력 형식이 증명·구성 자체를 요구한다면 완전 탐색을 먼저 만들 수 없을 수 있습니다. 이 경우에는 먼저 어떤 정보를 지금 알 수 있는지, 답을 언제 내야 하는지, 유지해야 할 불변식이 무엇인지부터 정합니다.

알고리즘 후보

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

엣지케이스

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