코딩테스트 준비 방법
프로그램 개발 순서
코딩 테스트는 개발자의 개발 역량을 파악하기에 좋은 기준입니다.
코딩 테스트를 준비하기 위해서는 핵심적인 부분을 반드시 학습 후 시작할 것을 추천합니다.
준비 방법의 순서는 다음과 같습니다.
- 자료구조와 알고리즘
- 복잡도 계산
- 알고리즘 문제 풀이
- 작성한 코드 분석
프로그램 제작의 설계 단계에서 프로그래머는 어떠한 방법으로 문제를 해결할 것인지 선택해야 합니다.
어떠한 데이터들이 있고 입력과 출력 형식을 파악한 뒤 요구사항에 맞는 자료구조를 선택하고
최대의 효율을 이끌어 낼 수 있는 알고리즘을 선택할 수 있어야 합니다.
그렇기 때문에 먼저 여러가지 자료구조와 알고리즘을 학습해야 합니다.
자료구조와 알고리즘을 선택할 때, 효율적인 효과를 위해 모든 자료구조와 알고리즘을 구현한 뒤 비교하기에는
사용되는 비용이 매우 큽니다. 따라서 효율적인 자료구조와 알고리즘을 판단할 수 있는 기준이 필요합니다.
판단 기준이 바로 시간 복잡도와 공간 복잡도 입니다.
모든 프로그램은 제한된 시간 안에 종료되고 요구사항에 맞는 목적을 달성해야 하므로
이를 위해 시간 복잡도와 공간 복잡도를 미리 계산하여 구현 비용을 절약할 수 있습니다.
시간복잡도와 공간복잡도를 근거로 효율적인 자료구조와 알고리즘을 선택하였다면,
이제 코드를 직접 작성해야 합니다.
코드 작성에는 개발 환경, 목적에 따라 사용하는 언어가 다릅니다.
따라서 목적에 맞는 언어로 코드를 작성합니다.
마지막으로 코드 작성이 끝나면 실행한 뒤 정상적으로 동작하는지 확인합니다.
프로그램은 반드시 유효한 시간에 목적을 달성한 뒤 종료되어야합을 잊지 말아야 합니다.
코딩 테스트 성능 확인
일반적인 코딩 테스트 환경에서는 O(N ^ 3) 을 넘어가면 문제 풀이에서 사용하기 어렵습니다.
왜냐하면 CPU 기반의 개인 컴퓨터나 채점용 컴퓨터에서는 연산 횟수가 10억 을 넘기면
C언어 기준으로 1초 이상의 시간이 소요됩니다.
이떄 N의 크기가 5,000을 넘는다면 족히 10초 이상의 시간이 걸릴 수 있습니다.
각기 다른 시간 복잡도의 연산 횟수가 N의 크기에 따라서 어떻게 분포되는지 확인해야 합니다.
다음은 대략적인 연산 횟수를 비교한 표로, 시간 복잡도가 동일하더라도
실제 연산 횟수에서 차이가 날 수 있습니다.
시간 복잡도가 O(N log(N))인 알고리즘은 매우 다양합니다.
Big-O 표기법으로 표시한 시간 복잡도가 같더라도
알고리즘 내부 로직 및 차수가 낮은 항의 영향에 따라 10,000번, 100,000번 등
실제 수행되는 연산 횟수는 다를 수 있습니다.
[N = 1,000 일때, 연산 횟수]
O(N) = 1,000
O(N log(N)) = 10,000
O(N ^ 2) = 1,000,000
O(N ^ 3) = 1,000,000,000
시간 복잡도 분석은 문제 풀이의 핵심입니다.
알고리즘 문제 풀이에 능숙한 숙련자들은 문제를 해석하기도 전에 조건을 먼저 보기도 합니다.
문제의 조건부터 확인하면 문제를 풀기 위해 얼마나 효율적인 알고리즘을 작성해야 하는지
눈치 챌 수 있기 때문입니다.
예를 들어 데이터의 개수 N이 1,000만 개를 넘어가며 시간 제한이 1초라면,
대략 최악의 경우 O(N)의 시간 복잡도로 동작하는 알고리즘을 작성해야 할 것이라고 예상할 수 있습니다.
혹은 데이터의 크기나 탐색 범위가 100억이나 1,000억을 넘어가는 경우 이진 탐색과 같이
O(log(N))의 시간 복잡도를 갖는 알고리즘을 작성해야 할 것입니다.
그래서 실제로 알고리즘 대회 참가에 익숙한 사람들은 문제의 조건을 확인한 뒤에
사용할 수 있는 알고리즘을 좁혀 나가는 전략을 채택하기도 합니다.
N의 범위가 500인 경우: O(N ^ 3)
N의 범위가 2,000인 경우: O(N ^ 2)
N의 범위가 100,000인 경우: O(N log(N))
N의 범위가 10,000,000인 경우: O(N)
코딩 테스트에서 문제를 풀 때는 가독성을 해치지 않는 선에서
최대한 복잡도가 낮게 프로그램을 작성해야 합니다.