코딩테스트 문제를 푸는 순서. 실력이 아니라 순서 때문에 시간을 버리는 경우가 많아서 따로 정리해둘 값어치가 있다. 요구사항을 이해하고, 설계하고 검증한 다음, 구현하고, 결과를 확인한다.
결과가 틀리면 구현으로 바로 돌아가지 말고 설계와 검증 단계로 돌아간다. 접근 자체가 틀렸는데 코드만 고치면 끝없이 반복된다.
문제를 읽는 순서
읽는 순서가 있다. 시간 제한과 메모리 제한을 먼저 봐야 어떤 알고리즘이 허용되는지 정해진다. N 범위로 알고리즘 고르기가 그 계산이다. 그 다음 문제 전체를 꼼꼼히 읽는다. 조건 하나를 놓치면 설계 전체가 무너진다. 주어진 정보를 추려 변수가 무엇이고 예제 데이터가 왜 그 답이 나오는지 이해한 뒤, 마지막으로 최대와 최소에 해당하는 입력을 직접 만들어 경계값에서 무슨 일이 일어나는지 확인한다.
구현 전 복잡도 계산
구현에 들어가기 전에 시간복잡도와 공간복잡도를 계산한다. N이 10만인데 이중 for문을 떠올렸다면 100억 번이라 안 된다는 걸 코드 한 줄 쓰기 전에 알 수 있다. O(N log N)이면 180만 번이니 가능하다. 이 계산을 건너뛰고 30분 짠 뒤에 시간 초과를 보는 것이 가장 아까운 경우다.
함수로 쪼개두기
함수로 쪼개 놓는 것도 시간을 아낀다. 다익스트라를 세 번 쓰는 문제에서 20줄짜리를 세 번 쓰면 60줄이지만 함수로 빼두면 호출 세 줄이다. 자주 쓰는 알고리즘은 함수 형태로 손에 익혀두는 것이 실전에서 유리하다.
부분 점수
만점 풀이가 안 떠오르면 완전 탐색으로라도 제출한다. 작은 입력에 대해서는 맞으니 점수가 붙는다. 0점과 부분 점수는 다르다.