문제를 해결할 좋은 알고리즘을 고를 때 정확성과 효율성은 어떤 순서로 검증하나요?

이렇게 답해 보세요 (핵심 답변)

먼저 입력·출력 계약과 불변식(Invariant)을 바탕으로 모든 유효한 입력에서 올바른 답을 내고 정상 종료하는지 '정확성'부터 확인합니다. 그다음 입력 크기와 분포에 따른 시간·공간 복잡도, 최악의 경우(Worst-case), 그리고 구현 복잡도를 함께 검토합니다. 이론적 Big-O 차수로 규모 증가에 따른 추세를 비교하되, 실제 선택에서는 목표 실행 환경의 데이터로 측정한 결과를 함께 확인해야 합니다.

함께 설명하면 좋은 이유 (꼬리질문 대비)

1. 빈 입력, 단건 입력, 중복값, 최대 크기 같은 경계값과 반례는 평범한 예제 입력에서는 잘 드러나지 않는 논리 오류를 찾아 줍니다.
2. 점근적 복잡도가 같더라도 상수 비용과 CPU 캐시 접근 패턴에 따라 실제 실행 시간은 크게 달라질 수 있습니다.

면접에서 자주 하는 실수

문제 정의와 정확성 계약을 검증하기도 전에 빠르다는 인상이나 Big-O 표기만으로 실제 초 단위 실행 시간을 단정하면 안 됩니다.