알고리즘은 정보처리기사 필기 2과목과 실기 모두에서 나오는 중요한 영역입니다. 특히 정렬 알고리즘의 시간 복잡도와 동작 방식, 이진 탐색 원리는 시험에서 반복해서 묻습니다. 코드를 직접 짜는 것보다는 알고리즘을 보고 결과를 추론하거나 빈칸을 채우는 형태로 출제되는 경우가 많으니 원리를 이해하는 방향으로 공부하세요.
1. 시간 복잡도와 Big-O 표기법
알고리즘의 효율성을 표현할 때 사용하는 표기법입니다. 입력 크기 n이 커질 때 실행 시간이 어떻게 증가하는지를 나타냅니다.
| 복잡도 | 표기 | 설명 | 예시 |
|---|---|---|---|
| 상수 | O(1) | 입력 크기와 무관하게 일정 시간 | 배열 인덱스 접근 |
| 로그 | O(log n) | 입력이 2배 늘어날 때 1번 추가 연산 | 이진 탐색 |
| 선형 | O(n) | 입력 크기에 비례 | 선형 탐색 |
| 선형 로그 | O(n log n) | n × log n에 비례 | 합병 정렬, 퀵 정렬(평균) |
| 이차 | O(n²) | 이중 반복문 | 버블·선택·삽입 정렬 |
| 지수 | O(2ⁿ) | 입력이 1 늘면 실행 시간 2배 | 재귀적 피보나치 |
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
퀵 정렬은 평균 O(n log n)이지만 최악의 경우 O(n²)임을 기억하세요.
2. 정렬 알고리즘
| 정렬 | 평균 복잡도 | 최악 복잡도 | 공간 | 안정성 |
|---|---|---|---|---|
| 버블 정렬 | O(n²) | O(n²) | O(1) | 안정 |
| 선택 정렬 | O(n²) | O(n²) | O(1) | 불안정 |
| 삽입 정렬 | O(n²) | O(n²) | O(1) | 안정 |
| 퀵 정렬 | O(n log n) | O(n²) | O(log n) | 불안정 |
| 합병 정렬 | O(n log n) | O(n log n) | O(n) | 안정 |
| 힙 정렬 | O(n log n) | O(n log n) | O(1) | 불안정 |
| 기수 정렬 | O(dn) | O(dn) | O(n+k) | 안정 |
각 정렬 알고리즘 원리
버블 정렬: 인접한 두 요소를 비교해 큰 값을 오른쪽으로 밀어내는 과정을 반복합니다. 가장 직관적이지만 가장 느린 편입니다. 패스(pass)마다 가장 큰 값이 맨 오른쪽으로 정렬됩니다.
선택 정렬: 전체에서 가장 작은 값을 찾아 맨 앞 원소와 교환합니다. 교환 횟수가 적어 메모리 접근이 많은 환경에서 유리합니다.
삽입 정렬: 현재 요소를 이미 정렬된 부분의 올바른 위치에 삽입합니다. 이미 정렬된 데이터나 거의 정렬된 데이터에서 매우 빠릅니다 (O(n) 가능).
퀵 정렬: 피벗을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할 후 재귀 정렬합니다. 평균적으로 가장 빠른 알고리즘이지만, 이미 정렬된 데이터에서는 O(n²)이 될 수 있습니다.
합병 정렬: 분할 정복 방식. 배열을 반씩 나누고 정렬된 두 부분을 합칩니다. 항상 O(n log n)을 보장하고 안정 정렬이지만, 추가 메모리 O(n)이 필요합니다.
✔ 가장 빠른 평균 복잡도: 퀵/합병/힙 정렬 모두 O(n log n)
✔ 항상 O(n log n) 보장: 합병 정렬, 힙 정렬 (퀵은 최악 O(n²))
✔ 안정 정렬: 버블, 삽입, 합병 / 불안정 정렬: 선택, 퀵, 힙
✔ 추가 메모리 없이 정렬 가능(제자리 정렬): 버블, 선택, 삽입, 퀵, 힙
3. 탐색 알고리즘
선형 탐색 (Sequential Search)
처음부터 끝까지 순서대로 비교합니다. 정렬 여부 상관없이 사용 가능합니다. 시간 복잡도: 평균 O(n/2), 최악 O(n).
이진 탐색 (Binary Search)
정렬된 배열에서 중간값과 비교해 탐색 범위를 절반씩 줄입니다. 반드시 정렬된 배열에서만 사용 가능합니다. 시간 복잡도: O(log n).
해시 탐색
해시 함수를 이용해 키를 인덱스로 변환 후 직접 접근합니다. 평균 O(1). 해시 충돌이 발생하면 성능이 저하됩니다. 충돌 해결 방법: 체이닝(연결 리스트), 개방 주소법(선형 탐사·이차 탐사·이중 해싱).
4. 핵심 자료구조
| 자료구조 | 특징 | 시간 복잡도 (접근/탐색/삽입/삭제) |
|---|---|---|
| 배열(Array) | 연속 메모리. 인덱스로 빠른 접근 | O(1) / O(n) / O(n) / O(n) |
| 연결 리스트(Linked List) | 포인터로 노드 연결. 삽입·삭제 빠름 | O(n) / O(n) / O(1) / O(1) |
| 스택(Stack) | LIFO(후입선출). push/pop | - |
| 큐(Queue) | FIFO(선입선출). enqueue/dequeue | - |
| 덱(Deque) | 양쪽 끝에서 삽입·삭제 가능 | - |
| 해시 테이블 | 키-값 쌍. 평균 O(1) 접근 | O(1) / O(1) / O(1) / O(1) [평균] |
스택 활용 예시
스택은 함수 호출 스택, 괄호 검사, 수식 변환(중위 → 후위)에 사용됩니다.
5. 트리와 그래프
이진 트리 순회
트리 순회는 시험에서 직접 순회 결과를 쓰는 문제로 자주 나옵니다. 세 가지 방식을 확실히 익혀두세요.
| 순회 방식 | 순서 | 특징 |
|---|---|---|
| 전위 순회(Preorder) | 루트 → 왼쪽 → 오른쪽 | 루트를 먼저 방문. 트리 복사에 사용 |
| 중위 순회(Inorder) | 왼쪽 → 루트 → 오른쪽 | 이진 탐색 트리에서 오름차순 정렬된 결과 |
| 후위 순회(Postorder) | 왼쪽 → 오른쪽 → 루트 | 루트를 마지막에 방문. 트리 삭제, 수식 계산에 사용 |
✔ 전위(Pre): Root가 맨 앞(Pre = 먼저)
✔ 중위(In): Root가 중간(In = 가운데)
✔ 후위(Post): Root가 맨 뒤(Post = 나중에)
✔ 이진 탐색 트리(BST) 중위 순회 = 오름차순 정렬 결과
그래프 탐색
| 탐색 | 방식 | 자료구조 | 특징 |
|---|---|---|---|
| DFS (깊이 우선 탐색) | 한 방향으로 갈 수 있는 끝까지 탐색 후 되돌아옴 | 스택 (재귀) | 사이클 탐지, 경로 탐색 |
| BFS (너비 우선 탐색) | 현재 노드와 인접한 노드를 모두 방문 후 다음 레벨로 | 큐 | 최단 경로, 레벨별 탐색 |
• 다익스트라(Dijkstra): 음수 가중치 없는 그래프의 최단 경로. O((V+E) log V)
• 벨만-포드(Bellman-Ford): 음수 가중치 허용. O(VE). 음수 사이클 탐지 가능
• 플로이드-워셜(Floyd-Warshall): 모든 쌍의 최단 경로. O(V³)
시험에서 "음수 가중치를 허용하는 최단 경로 알고리즘" 하면 벨만-포드를 떠올리세요.
마무리
알고리즘 파트에서 가장 중요한 건 정렬 알고리즘의 시간 복잡도와 안정성, 그리고 트리 순회 결과입니다. 이 두 가지만 확실히 잡으면 알고리즘 문제 대부분을 커버할 수 있습니다. 복잡도는 외우는 것도 중요하지만 "이중 루프면 O(n²)"처럼 코드를 보고 바로 복잡도를 추론하는 연습도 병행하세요.