알고리즘 선택의 기준이 되는 시간 복잡도

코딩 테스트의 핵심 중 하나는 문제마다 주어진 시간 복답도를 고려해 적절한 알고리즘을 선택하는 것입니다. 처음에 알고리즘을 잘못 선택하면 아무리 코드를 잘 짜려고 노력해도 좋은 결과를 거두기 어렵습니다.

 

시간 복잡도 표기법 알아보기

알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말합니다. 일반적으로 수행 시간은 1억 번의 연산을 1초의 시간으로 간주하여 예측합니다.

 

시간 복잡도 유형

- 빅-오메가, 빅-세타, 빅-오

- 빅-오 : 최악일 때 (worst case)의 연산 횟수를 나타낸 표기법

 

코딩 테스트에서는 빅-오 표기법을 기준으로 수행 시간을 계산하는 것이 좋습니다.  다양한 테스트 케이스를 수행해 모든 케이스를 통과하는 것 처럼 시간 복잡도를 판단할 때는 최악일 때 를 염두어 둬야 합니다.

 

시간 복잡도는 작성한 코드의 비효율적인 로직을 개선하는 바탕으로도 사용할 수 있습니다. 이 부분을 활용하려면 가장 먼저 코드의 시간 복잡도를 도출할 수 있어야 합니다. 시간 복잡도를 도출하려면 다음 2가지 기준을 고려해야 합니다.

1. 상수는 시간 복잡도 게산에서 제외한다.

2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다.

 

시간 복잡도는 가장 많이 중첩된 반복문을 기준으로 도출한다.

 

코드에서 논리 오류를 찾아내지 못해 코딩 테스트를 통과하지 못하는 안타까운 경우를 많이 봅니다. 이러한 상황에서 논리 오류를 찾을 수 있는 가장 최선의 방법은 '디버깅'입니다.

 

프로그램에서 발생하는 문법 오류나 논리 오류를 찾아 바로잡는 과정을 디버깅(debugging)이라고 합니다. 문법 오류는 컴파일러가 자동으로 찾아 주므로 테스트할 때 문제가 되지 않습니다. 논리 오류는 코드가 사용자의 의도와 다르게 동작하느 ㄴ것이며 다양한 형태로 발생합니다.

 

디버깅은 코딩 테스트에 필요한 기술이고, 그냥 알아 두기만 하면 되는 것이 아니라 문제를 풀면서 반드시 해야 하는 과정입니다. 반드시 디버깅을 익힌 후에 코딩 테스트에 응시하기 바랍니다.