알고리즘은 문제를 해결하기 위한 방법이다.
대표적으로 피타고라스의 정리는 빗변의 길이를 구하기 위한 알고리즘이라고 볼 수 있으며 컴퓨터 공학에서 알고리즘은 대부분 기존에 일반적인 방식으로 진행 시 소모되던 시간을 더 줄일 수 있는 새로운 방법이라고 생각한다. 그렇기 때문에 알고리즘은 도출할 수 있는 모든 결과 중에서도 거의 최악에 가까운 경우의 수를 판단하는 지표로 보고 해당 경우의 수 이내에 작업이 수행된다고 판단한다. 그래서 대부분의 알고리즘 Big-O 표기법이라고 하는 점근적 표기법으로 입력에 따른 수행시간을 나타낼 수 있으며 이를 시간 복잡도라고도 한다.
시간 복잡도의 표기는 다음과 같다.
실제로 수학적 식으로 표현하면 약간 다르지만 기본적으로 필자가 적은 방법대로 시간 복잡도를 구하면 쉽게 시간 복잡도를 구할 수 있다. 여기서 코드를 보고 직접 시간 복잡도를 구해보도록 하자.
해당 코드의 경우 n 에 임의로 값을 집어 넣었는데, 실제로는 scan 을 통해 값을 받는 다고 가정하자. 그리고 위의 시간 복잡도 Big-O 표기법으로 바꾸면 n+1 에서 1 을 버리고 O(n) 이 된다. 하지만 다음과 같이 순수 상수만 있는 경우에는 어떻게 될까?
위와 같이 상수만 있는 경우에는 n 이 없으므로 O(0) 이 되지 않을까 싶지만 상수만 남았을 경우 O(1) 로 표기한다.
그럼 마지막으로 자주 나오는 시간 복잡도 목록과 더불어 기본 알고리즘이라고 알려진 몇몇 알고리즘을 알아보자.
보통 O(n2) 을 넘어가면 수행 시간이 급격하게 증가하기에 대부분의 PS 문제에서 요구하는 효율성은 O(nlogn) 이하이며 해당 시간복잡도를 넘은 솔루션을 구현하면 정확성을 다 통과하더라도 절반 이하로 점수를 받게 된다. 따라서 문제를 해결할 수 있는 열쇠가 될 대표적인 알고리즘을 숙지하고 있어야하며 전공 이수과정 및 PS 에서 자주 출현하는 알고리즘들은 다음과 같다.
1. 탐색
- 선형 탐색
- 이분 탐색
2. 정렬
- 버블 정렬
- 선택 정렬
- 삽입 정렬
- 퀵 정렬
- 병합 정렬
3. 그래프 / 트리
- DFS(깊이 우선 탐색)
- BFS(너비 우선 탐색)
- 최단 경로 탐색
- 다익스트라
- 힙 트리
- 스패닝 트리
- 크루스칼
- 프림
4. 기타 프로그래밍 기법
- 동적계획법(DP)
- 분할 정복
- 그리디
- 백트래킹
