[코딩테스트 합격자 되기 C++편] 문제 풀이 일지를 작성하기로 했다.

코딩 테스트 합격자 되기 C++편을 보며 코딩테스트 공부를 시작하기로 했다.

앞의 부분은 건너뛰고 3장. 알고리즘의 효율 분석 부터 정리해보려고 한다.

알고리즘의 효율 분석이란 알고리즘의 시간 복잡도를 계산하는 것을 말한다.

시간 복잡도란 입력값에 따른 알고리즘의 연산 횟수를 의미한다.

입력값은 얼마든지 커질 수 있기 때문에, 실제 숫자로 정확한 수치를 계산하는 것이 아니라 입력값 N으로 점근적 표기를 하게 된다.

그러한 표기법을 빅오 표기법이라고 한다.

O(x²)

이와 같이 가장 증가폭이 큰 항의 계수를 지우고 작성한다.

지수함수>다항함수>로그함수와 같은 우선순위로 작성하게 된다.

지금까지 문제를 풀 때에는 시간 복잡도는 고려하지 않은 채로 문제 풀이 방법에 집중했었는데,

오히려 시간 복잡도를 고려하면 문제를 풀 단서를 쉽게 얻을 수도 있겠다는 생각이 든다.

시간 복잡도를 고려한다는 것은, 문제에 따라 정확한 알고리즘을 선택하는 방법을 고민하는 것과 비슷한 맥락이라고 생각한다.

결국 문제를 풀 때에는 출제자의 의도를 간파해서 그에 맞게 풀어주는 게 가장 쉬운 방법인 것 같다.

문제를 낸 사람도 응시자들이 영원히 고통받기를 바라면서 문제를 만들었을 리도 없고…

문제의 풀이법을 눈치채주길 바라며 단서를 흘렸을 거라고 생각하니까 추리게임 같다는 생각도 들고…?

사실 난 추리게임을 별로 좋아하진 않는다.

아무튼 다음엔 본격적으로 문제 풀이를 해보겠다.