코딩테스트를 준비하면서 알고리즘 공부의 필요성을 절실히 느끼게 되었습니다.
특히 알고리즘이 자료구조와 밀접하게 연결되어 있다는 점을 알게 되면서,
이번 기회에 알고리즘을 제대로 학습해보아야겠다고 다짐하였습니다.
문제를 풀기에 앞서, 우선 알고리즘에는 어떤 대표적인 유형들이 있는지 정리하고 살펴보고자 합니다.
알고리즘(Algorithm)
알고리즘은 어떤 문제를 해결하기 위해 명확히 정의된 유한한 단계의 절차입니다.
같은 문제라도 어떤 절차를 사용하느냐에 따라 실행 시간과 메모리 사용량이 크게 달라질 수 있습니다.
따라서 알고리즘을 설계할 때는 효율성과 정확성을 동시에 고려하는 것이 중요합니다.
알고리즘의 조건
알고리즘이 성립하기 위해서는 다음과 같은 조건들을 만족해야 합니다.
- 정확성 : 주어진 입력에 대해 올바른 출력을 보장해야 함
- 명확성 : 각 단계가 모호하지 않고 명확하게 정의되어야 함
- 유한성 : 유한한 횟수의 연산 후에 종료되어야 함
- 효율성 : 시간과 메모리 사용량이 합리적이어야 함
알고리즘 성능 평가
알고리즘의 성능은 크게 시간 복잡도와 공간 복잡도로 평가합니다.
그중에서도 시간 복잡도는 입력 크기 N이 커질 때 연산 횟수가 얼마나 증가하는지를 나타내며, 주로 빅오(Big-O) 표기법을 사용합니다. 아래는 대표적인 시간 복잡도와 그 의미를 정리한 표입니다.
 |
빅오 표기법 | 내용 | 대표 예시 |
| O(1) | 입력 크기와 관계없이 항상 일정한 시간에 실행 | 배열 인덱스 접근(탐색) | |
| O(log N) | 입력 크기가 커져도 연산 횟수가 로그 단위로 증가 | 이진 탐색 (탐색), 균형 이진 트리 탐색 (트리) | |
| O(N) | 입력 크기에 비례하여 실행 시간 증가 | 선형 탐색 (탐색), BFS/DFS (그래프) | |
| O(N log N) | 대부분의 효율적인 정렬 알고리즘의 복잡도 | 병합 정렬, 퀵 정렬 (정렬), 힙 정렬 (트리) | |
| O(N^2) | 이중 반복문이 사용되는 경우 | 버블 정렬, 삽입 정렬 (정렬), 플로이드-워셜 (그래프) | |
| O(N^3) | 삼중 반복문이 필요한 경우 | 그래프의 모든 경로 탐색 일부 (그래프) | |
| O(2^N) | 입력 크기가 하나 늘 때마다 연산 횟수가 2배 증가 | 부분 집합 생성, 백트래킹 탐색 (그래프/트리) | |
| O(N!) | 가능한 모든 경우의 수를 탐색 (순열) | 외판원 순회 문제 완전 탐색 (그래프) |
위 표를 통해 알 수 있듯이, 입력 크기가 커질수록 알고리즘의 실행 시간 차이는 기하급수적으로 커집니다.
따라서 알고리즘을 설계할 때는 항상 입력 크기와 허용 가능한 시간 복잡도를 고려해야 합니다.
실무나 코딩 테스트에서도 문제의 입력 범위를 확인하고,
이에 맞는 시간 복잡도를 가진 알고리즘을 선택하는 것이 매우 중요합니다.
대표 알고리즘 유형
알고리즘의 종류는 매우 다양하지만,
코딩 테스트와 실무에서 특히 자주 사용되는 핵심 유형들을 중심으로 살펴보겠습니다.
이 글에서는 대표 알고리즘(정렬, 탐색, 그래프, 트리, 해싱)과 함께,
문제 해결을 위한 알고리즘 설계 패러다임(재귀, 분할 정복, 동적 계획법, 탐욕법, 백트래킹)에 대해서도 정리하고자 합니다.
구체적인 알고리즘과 설계 기법을 함께 이해하면,
단순히 이론을 아는 데서 그치지 않고 실제 문제 해결에 적용할 수 있는 힘을 기를 수 있습니다.
대표 알고리즘 유형
대표적인 알고리즘에는 정렬, 탐색, 그래프, 트리, 해싱이 있습니다.
이들은 코딩 테스트와 실무에서 가장 자주 다뤄지는 핵심 주제이며, 알고리즘 학습의 기초를 이루는 중요한 영역입니다.
아래에서는 각 알고리즘 유형의 기본 개념과 특징을 살펴보고, 어떤 상황에서 활용되는지 좀 더 자세히 알아보겠습니다.
1) 정렬(Sorting)
주어진 데이터를 일정한 기준(오름차순, 내림차순 등)에 맞게 재배열하는 알고리즘
대표적인 정렬 알고리즘으로는 버블 정렬(Bubble Sort), 삽입 정렬(Insertion Sort), 선택 정렬(Selection Sort), 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort), 힙 정렬(Heap Sort), 카운팅 정렬(Counting Sort) 등이 있습니다.
정렬 알고리즘은 단순히 데이터를 순서대로 나열하는 데 그치지 않고,
이후에 수행되는 탐색, 최적화, 데이터 분석과 같은 연산을 더 빠르고 효율적으로 만들기 위해 사용됩니다.
또한 정렬은 실생활 속 다양한 사례에서 자연스럽게 활용됩니다.
도서관에서 책을 가나다순으로 배열하거나, 쇼핑몰에서 상품을 가격순으로 정렬하는 것,
그리고 시험 성적을 점수 순으로 나열하는 것 모두 정렬 알고리즘의 대표적인 적용 예시입니다.
🔢 활용 자료구조
- 배열(Array) → 가장 기본적인 자료구조로, 대부분의 정렬 알고리즘(버블, 삽입, 선택, 병합, 퀵 등)의 입력으로 사용됨
- 리스트(List) → 연결 리스트 기반 정렬(삽입, 병합)에서 활용되며, 노드 기반 구조라 삽입·삭제에 용이함
- 힙(Heap) → 힙 정렬에 사용되는 대표 자료구조로, 완전 이진 트리 형태를 이용해 최대/최소값을 빠르게 꺼낼 수 있음
2) 탐색(Search)
주어진 데이터 집합에서 원하는 값을 찾아내는 알고리즘
대표적인 탐색 알고리즘으로는 순차 탐색(Linear Search), 이진 탐색(Binary Search) 등이 있습니다.
탐색 알고리즘은 단순히 값을 찾는 것에서 끝나는 것이 아니라,
이후의 데이터 처리, 조건 분기, 최적화 문제에서 기본적인 연산으로 활용됩니다.
실생활에서 탐색은 예를 들어 전화번호부에서 특정 이름을 찾는 과정, 쇼핑몰에서 원하는 상품을 검색하는 기능 등으로 쉽게 접할 수 있습니다.
🔍 활용 자료구조
- 배열(Array) → 순차 탐색, 이진 탐색에 가장 기본적으로 사용됨
- 트리(Tree) → 이진 탐색 트리(BST)를 이용하면 탐색을 더 효율적으로 수행할 수 있음
- 해시 테이블(Hash Table) → 평균적으로 O(1)에 가까운 탐색 성능을 제공함
3) 그래프 (Graph)
정점(Vertex)과 간선(Edge)으로 이루어진 자료구조에서 경로, 연결 여부, 최단 거리 등을 찾는 알고리즘
대표적인 그래프 알고리즘으로는 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS), 다익스트라(Dijkstra), 크루스칼(Kruskal), 프림(Prim) 등이 있습니다.
그래프 알고리즘은 단순히 구조를 탐색하는 데 그치지 않고,
네트워크 경로 탐색, 소셜 네트워크 분석, 최적화 문제 등 다양한 분야에서 활용됩니다.
실생활에서는 지하철 노선에서 최단 경로 찾기, 지도 앱에서 최적 경로 탐색, SNS에서 친구 추천 기능 등이 그래프 알고리즘의 대표적인 사례입니다.
🕸 활용 자료구조
- 인접 리스트(Adjacency List) → 희소 그래프에서 메모리를 효율적으로 표현할 때 사용
- 인접 행렬(Adjacency Matrix) → 밀집 그래프를 표현할 때 유리하며, 특정 두 정점 간 연결 여부를 빠르게 확인 가능- 큐(Queue) & 스택(Stack) → BFS(큐), DFS(스택) 구현 시 필수적으로 사용됨
4) 트리 (Tree)
계층적 구조를 표현하는 비선형 자료구조로, 루트(Root)에서 시작하여 부모-자식 관계를 기반으로 구성
트리는 알고리즘(Algorithm) 자체라기보다는 자료구조(Data Structure)이지만,
다양한 알고리즘의 기반이 되므로 대표 알고리즘 유형에서 함께 다루겠습니다.
대표적인 트리 알고리즘으로는 이진 탐색 트리(Binary Search Tree, BST), 레드-블랙 트리(Red-Black Tree), 허프만 코딩(Huffman Coding) 등이 있습니다.
트리 알고리즘은 데이터의 탐색, 삽입, 삭제를 효율적으로 수행할 수 있도록 도와주며, 계층적 구조를 다루는 데 매우 유용합니다.
실생활에서는 폴더 디렉토리 구조, 가계도, 회사 조직도 등 계층적으로 표현되는 데이터에서 트리 구조가 활용됩니다.
🌳 활용 자료구조
- 이진 탐색 트리(BST) → 탐색과 정렬을 빠르게 수행할 수 있는 기본 트리 구조- 힙(Heap) → 우선순위 큐 구현과 힙 정렬에 사용됨
- 세그먼트 트리(Segment Tree) → 구간 합, 최솟값/최댓값 등 범위 쿼리 연산에 활용됨
5) 해싱(Hashing)
데이터를 해시 함수(Hash Function)를 통해 일정한 크기의 값(해시 값)으로 변환하여, 해시 테이블에 저장하고 검색하는 기법
해싱은 알고리즘(Algorithm) 그 자체라기보다 기법(Technique) 또는 자료구조의 구현 방식에 더 가깝습니다.
해싱 자체는 데이터를 빠르게 저장·탐색하기 위한 기법입니다.
다만 해시 함수 설계, 충돌 해결 방식 등에서 알고리즘적인 요소가 포함되기 때문에 알고리즘 학습에서 함께 다루게 됩니다.
대표적인 해싱 기법으로는 체이닝(Chaining), 개방 주소법(Open Addressing) 등이 있습니다.
해싱은 평균적으로 탐색, 삽입, 삭제 연산을 O(1)에 가깝게 수행할 수 있어 매우 빠른 성능을 제공합니다.
실생활에서는 사전(Dictionary) 자료 검색, 데이터베이스 인덱싱, 비밀번호 암호화 저장 등에서 해싱이 널리 활용됩니다.
🗂️ 활용 자료구조
- 해시 테이블(Hash Table) → 키-값(Key-Value) 쌍 데이터를 빠르게 저장하고 탐색
- 배열(Array) → 해시 테이블의 기본 저장 공간으로 사용됨
- 연결 리스트(Linked List) → 체이닝 방식 충돌 해결 시 활용됨
알고리즘 설계 패러다임
알고리즘을 단순히 나열하거나 암기하는 것만으로는 한계가 있습니다.
문제를 해결하기 위해서는 어떤 전략으로 접근할 것인지, 즉 알고리즘을 설계하는 방법론을 이해하는 것이 중요합니다.
이를 알고리즘 설계 패러다임(Algorithm Design Paradigm)이라고 하며,
이는 다양한 문제 유형에서 반복적으로 등장하는 공통적인 해결 전략을 뜻합니다.
대표적인 설계 패러다임으로는 재귀(Recursion), 분할 정복(Divide & Conquer), 동적 계획법(Dynamic Programming), 탐욕법(Greedy), 백트래킹(Backtracking)이 있습니다.
아래에서는 각 알고리즘 유형의 기본 개념과 특징을 살펴보고, 어떤 상황에서 활용되는지 좀 더 자세히 알아보겠습니다.
1) 재귀 (Recursion)
어떤 함수가 자기 자신을 직접 혹은 간접적으로 호출하여 문제를 해결하는 방식
대표적인 재귀 알고리즘으로는 팩토리얼 계산, 피보나치 수열, 하노이의 탑 문제 등이 있습니다.
재귀는 문제를 작은 부분 문제로 쪼개어 해결하기 때문에 코드가 간결해지고 이해하기 쉬워집니다.
다만, 호출 스택을 사용하기 때문에 깊은 재귀 호출에서는 스택 오버플로우가 발생할 수 있고, 반복문보다 비효율적일 수 있습니다.
실생활 예시로는 디렉토리 탐색(폴더 안에 또 다른 폴더를 확인하는 과정), 가계도 탐색 등이 있습니다.
🔁 활용 자료구조
- 스택(Stack) → 함수 호출 시 호출 스택에 쌓이는 구조
- 트리(Tree) → 트리 순회(전위, 중위, 후위)에 재귀가 자주 사용됨
- 그래프(Graph) → DFS(깊이 우선 탐색) 구현에 활용됨
2) 분할 정복 (Divide & Conquer)
문제를 더 작은 부분 문제로 나눈 뒤(Divide), 각각을 해결하고(Conquer), 그 결과를 합쳐서(Combine) 원래 문제를 해결하는 방식
대표적인 분할 정복 알고리즘으로는 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort), 이진 탐색(Binary Search), 푸리에 변환(FFT) 등이 있습니다.
분할 정복은 문제를 잘게 나누어 처리하기 때문에 큰 문제도 효율적으로 해결할 수 있습니다.
다만, 부분 문제의 수가 많아지고 중복 연산이 많아질 경우 비효율적일 수 있습니다.
실생활 예시로는 전화번호부에서 중간 값을 기준으로 찾는 이진 탐색, 대용량 데이터를 여러 서버에서 나누어 처리하는 분산 처리 시스템 등이 있습니다.
➗ 활용 자료구조
- 배열(Array) → 이진 탐색, 병합 정렬, 퀵 정렬에서 사용됨
- 트리(Tree) → 분할된 문제 구조를 계층적으로 표현할 때 활용
- 재귀 함수 → 분할 정복 알고리즘 구현의 기본적인 도구
3) 동적 계획법 (Dynamic Programming, DP)
큰 문제를 작은 부분 문제로 나누어 해결하고, 그 결과를 저장해두어 중복 계산을 피하는 방식
대표적인 DP 알고리즘으로는 피보나치 수열, 최장 공통 부분 수열(LCS), 배낭 문제(Knapsack Problem), 플로이드-워셜 알고리즘(Floyd-Warshall) 등이 있습니다.
DP는 메모이제이션(Top-down) 또는 테이블 채우기(Bottom-up) 방식을 사용하여 연산 속도를 크게 개선할 수 있습니다.
다만, 테이블 크기에 따라 공간 복잡도가 커질 수 있습니다.
실생활 예시로는 지도 앱에서 여러 경로 중 최단 거리 찾기, 주식 거래에서 최대 이익 계산, 문자열 비교(자동완성, 맞춤법 교정) 등이 있습니다.
📊 활용 자료구조
- 배열(Array) → 메모이제이션, DP 테이블 구현에 기본적으로 사용됨
- 해시 테이블(Hash Table) → 부분 문제 결과를 동적으로 저장할 때 활용됨
- 그래프(Graph) → 최단 경로 문제 등 DP와 결합해 자주 쓰임
4) 탐욕법 (Greedy)
매 단계에서 그 순간 가장 최적이라고 생각되는 선택을 하여 최종적인 해답에 도달하는 방식
대표적인 탐욕 알고리즘으로는 최소 신장 트리(MST) 알고리즘(크루스칼, 프림), 다익스트라 최단 경로 알고리즘, 동전 거스름 문제 등이 있습니다.
탐욕법은 구현이 간단하고 빠른 시간 안에 답을 구할 수 있다는 장점이 있습니다.
그러나 항상 전역 최적해(Global Optimum)를 보장하지는 않고, 특정 조건(탐욕 선택 속성, 최적 부분 구조)이 만족되어야 올바른 답을 얻을 수 있습니다.
실생활 예시로는 잔돈 거슬러주기(가장 큰 동전부터 사용), 회의실 배정 문제(빨리 끝나는 회의부터 선택) 등이 있습니다.
💰 활용 자료구조
- 우선순위 큐(Priority Queue) → 다익스트라, 프림 알고리즘에서 사용됨
- 그래프(Graph) → MST, 최단 경로 탐색에 활용됨
- 배열(Array) → 정렬 후 탐욕적으로 선택하는 문제에서 사용
5) 백트래킹 (Backtracking)
조건을 만족하지 않으면 되돌아가(Backtrack) 다른 경우를 탐색하는 방식
대표적인 백트래킹 알고리즘으로는 N-Queen 문제, 부분 집합 생성, 순열 생성, 미로 찾기 등이 있습니다.
백트래킹은 모든 경우를 탐색하는 완전 탐색(Brute Force)을 개선한 방식으로, 불필요한 탐색을 줄일 수 있습니다.
하지만 경우의 수가 여전히 많을 경우, 시간 복잡도가 급격히 증가할 수 있습니다.
실생활 예시로는 스도쿠 풀이, 지도에서 특정 조건을 만족하는 경로 탐색, 암호학에서 가능한 키 조합 탐색 등이 있습니다.
🔙 활용 자료구조
- 스택(Stack) → 탐색 경로를 저장하고 되돌아갈 때 사용됨
- 트리(Tree) → 가능한 경우의 수를 트리 구조로 표현
- 그래프(Graph) → 경로 탐색 문제에서 백트래킹 기법 활용
되돌아보며
알고리즘은 문제를 단계적으로 해결하는 절차이며, 적절한 자료구조와 함께할 때 가장 큰 효과를 발휘합니다.
같은 문제라도 어떤 자료구조를 선택하느냐에 따라 실행 속도와 효율성이 달라지므로, 두 가지를 함께 학습하는 것이 중요합니다.
특히 코딩 테스트에서는 단순히 알고리즘을 아는 것보다,
문제 조건을 보고 시간 복잡도를 예측하고, 그에 맞는 패러다임을 적용하는 능력이 핵심입니다.
이를 위해서는 다음과 같은 훈련 과정이 필요합니다.
- 문제 조건 분석 → 입력 크기와 제약을 보고 가능한 시간 복잡도를 예측하기
- 패러다임 선택 → 정렬+그리디, BFS/DFS, 다익스트라, DP 등 적절한 알고리즘 패턴 떠올리기
- 구현 및 검증 → 직접 코드를 작성하고 성능을 확인하며 이해를 체화하기
이 과정을 반복하다 보면, 단순히 알고리즘을 외우는 것이 아니라
상황에 맞는 알고리즘을 적절히 선택하고 적용할 수 있는 감각을 기르는 것으로 발전하게 됩니다.
결국 이는 곧 진정한 의미의 문제 해결 능력으로 이어진다고 생각합니다.
저 또한 이 과정을 토대로 꾸준히 훈련하여, 알고리즘 문제를 해결하는 실력을 한 단계씩 쌓아가고 싶습니다.
