루프 구조를 식으로 편다
중첩, 결합, 조기 종료 조건을 나눠 실제 반복 횟수가 어떤 입력에서 커지는지 확인합니다.
복잡도 결론은 입력 제한과 병목 연산으로 닫는다
반복 횟수만 세면 개선처럼 보이는 풀이를 놓치기 쉽습니다. 연산 단가, 보조 공간, 입력 상한을 함께 묶어야 결론이 흔들리지 않습니다.
한 번의 작업 비용 분리
이진탐색 뒤 리스트 삽입처럼 겉보기 개선 뒤에 남은 선형 비용을 별도로 계산합니다.
입력과 보조 공간 구분
정렬 버퍼, 해시 테이블, 재귀 스택을 포함해 실제 메모리 여유와 맞는지 확인합니다.
성능 결론을 검증하는 순서
코드 전입력 제한으로 허용 가능한 상한을 먼저 정하고 후보 풀이를
걸러냅니다.
개선 후병목 연산이 정말 줄었는지 반복 횟수와 연산 단가를 다시
씁니다.
제출 전최악 입력과 평균 입력을 나눠 시간과 공간 결론을 동시에
확인합니다.