[tip] 코테 시간 제한 통과하는 방법

boj처럼 코딩테스트 대비를 위한 알고리즘 사이트에서 문제를 풀다보면 아래와 같은 조건이 나오는 것을 볼 수 있다.

 

출처: boj online judge

시간 제한과 메모리 제한이라는 제약 조건이 있는 것을 볼 수 있는데 처음에 풀다 보면, 막연하게 1초, 128mb이러니까 잘 와닿지 않고 저런 조건들은 어떻게 돌아가는 것인가 궁금할 수 있다.

 

나도 정확하게 저 정도가 어느 정도일까 하고 봤는데, 저 내용을 정확하게 이해하려면 몇 가지 개념을 이해해야 한다.

 

1. 시간복잡도 확인하기(제일 핵심)

시간복잡도는 알고리즘(연산)이 실행되는 동안에 사용된 기본적인 연산 횟수를 입력 크기의 함수로 나타낸다. 아래와 같이 시간복잡도는 알고리즘에서 가장 기초적인 부분이고, 지수와 로그에 대한 연산만 할 수 있다면 

2. 로직을 정확하게 작성하자

처음 문제풀이를 하다보면, 언어가 문제인가,, 코드가 별로인가,, 로 생각해 버리는 경우가 참 많다. 그러나 사실 로직이 제대로 잡혀있지 않은 경우가 많다. 펜과 종이로 먼저 이산적 구조를 그려보기를 시도해 보자.

 

3. 다른 사람의 코드 참고하기

확실히 다른 언어보다 c++로 그 문제를 구글링해보면, 이미 풀려져 있는 풀이가 매우 많이 있다. 그걸 참고하되, 주의할 점은 이미 짜놓은 나만의 로직과 코드가 있어야 한다는 점이다. 그래야 비교분석이 가능해지고, 무엇보다 알고리즘에서 제일 중요한 것은 trial-and-error 과정이 선행되어야 하기에 반드시 시간이 걸리고 오래 걸려도 나만의 그 과정이 있어야 한다.

 

남이 풀어서 내놓은 코드는 이미 그 사람이 수도없이 풀어서 수정을 반복한 결과 가운데의 코드이다. 그저 내가 풀어보지 않고, 남의 완성돤 코드만 가져와서 풀면 내 생각하는 능력은 절대 발전하지 않는다.