Complexity check

빠른 연산 뒤에 숨어 있는 반복과 메모리를 같이 센다

복잡도 오판은 보통 “탐색은 빠르다”에서 멈출 때 생긴다. 한 줄의 코드도 반복 횟수, 연산 단가, 보조 공간, 최악 입력을 함께 적어야 상한이 맞는다.

1. 몇 번 반복하나

루프, 재귀, 호출 횟수를 입력 크기 기준으로 먼저 고정한다.

2. 한 번에 무엇을 쓰나

삽입, 복사, 해시 버킷, 재귀 스택처럼 숨은 비용을 더한다.

3. 평균과 최악을 나누나

해시 충돌, 깊은 재귀, 역정렬 입력은 평균식을 깨뜨린다.

4. 입력 제한에 맞나

최종 식을 제한 크기와 메모리 한도에 연결해 판단한다.

코드 신호 숨은 비용 상한을 바꾸는 질문 판정
중간 삽입
list.insert(pos, x) 		뒤 원소 이동 때문에 삽입 한 번이 O(N)이다. 이진 탐색으로 위치를 빨리 찾아도 이동 비용은 남는가? 전체 루프와 합치면 O(N²) 가능성이 크다.
복사
arr[:mid] 		길이 K만큼 시간과 새 버퍼 O(K)가 생긴다. 재귀 호출마다 새 배열을 만들고 있지는 않은가? 점화식과 순간 메모리 피크를 함께 계산한다.
재귀
dfs(node) 		시간은 O(V+E), 스택은 깊이에 비례한다. 그래프가 깊게 이어지면 호출 한계를 넘지 않는가? 시간 통과와 별개로 공간 실패를 점검한다.
해시
set.add / in 		평균은 빠르지만 키 저장공간은 O(N)이다. 입력 분포와 충돌 가능성을 문제 조건이 보장하는가? 평균 O(1)과 최악 케이스를 분리해 적는다.

핵심: 복잡도는 코드 줄 수가 아니라 반복 횟수 × 연산 단가 + 보조 공간의 피크로 판정한다.