코딩테스트 문제 풀기 팁

코딩테스트에선 문제마다 특정 값 입력의 최대 크기, 혹은 저장해야할 값의 최대 크기가 주어진다. 우리는 이를 통해 짜야할 알고리즘에 대한 힌트를 얻을 수 있다.

입력 값의 최대 크기로 유추

컴퓨터는 일반적으로 1초에 10^8 ~ 10^9의 연산을 할 수 있다. 이 사실과 시간초과가 15초(프로그래머스)로 설정된것을 기반으로 생각해보면 대충 유추가 가능하다.

• ex) O(N^3)이 걸리는 알고리즘의 경우(3중 반복문 등)
  • N의 범위가 1000이라면 필요한 연산의 수는 1000^3이 걸린다. 그렇다면 컴퓨터가 1초에 10^9번 연산한다고 가정하면 (1000^3 / 10^9 = 1초)의 시간이 걸린다. 때문에 안전한 범위는 N의 범위가 1000까지 일때이다.
• ex) O(N^2)이 걸리는 알고리즘의 경우(2중 반복문 등)
  • 위와 같은 내용으로 N의 범위가 100000 이라면 N은 10^5이며 O(N^2)인 알고리즘은 10^10의 연산이 필요하다. 위와 같이 계산하면 (10^10 / 10^9 = 10초)의 걸린다. 그렇기 때문에 N의 범위가 100000이라면 O(N^2) 알고리즘까지 사용할 수 있다.

O(N)이나 O(logN)과 같은 효율적인 알고리즘의 경우에는 N이 매우 큰 경우(예: 10^6 이상)에도 충분히 시간 내에 해결할 수 있다.

또한, 입력값의 최대 크기가 작은 경우(예: N ≤ 20)에는 완전 탐색이나 백트래킹과 같은 시간복잡도가 높은 알고리즘을 사용해도 무방하다.

저장해야 할 값의 크기로 유추

문제에서 주어지는 값의 범위도 중요한 힌트가 된다:

• 정수 범위가 -2^31 ~ 2^31-1로 주어진다면 int 자료형을 사용
• 정수 범위가 -2^63 ~ 2^63-1로 주어진다면 long long 자료형을 사용
• 소수점 계산이 필요한 경우 double이나 float 자료형 고려

이러한 값의 범위는 오버플로우나 언더플로우 같은 에러를 방지하기 위해 적절한 자료형을 선택하는데 도움을 준다.

위 내용을 이용해 필요한 알고리즘과 출제자의 의도를 엿볼 수 있다.