코딩테스트 필수 알고리즘 및 개념 정리

코딩 테스트를 준비하기 위해 반드시 공부해야 하는 주요 알고리즘을 정리한다. 다음은 주요 알고리즘과 그 개념, 그리고 사용되는 상황에 대한 설명이다.

1. 정렬 알고리즘

정렬은 데이터를 특정 순서대로 배열하는 작업이다. 대표적인 정렬 알고리즘으로는 버블 정렬, 삽입 정렬, 선택 정렬, 병합 정렬, 퀵 정렬 등이 있다. 정렬은 배열을 정리하거나 탐색 효율성을 높이기 위해 사용된다.

• 버블 정렬: 인접한 두 요소를 비교하여 정렬한다. 시간 복잡도는 O(n^2)이다.
• 삽입 정렬: 정렬된 부분과 정렬되지 않은 부분으로 나눠 하나씩 삽입하며 정렬한다. 시간 복잡도는 O(n^2)이다.
• 퀵 정렬: 기준점을 잡고 이를 기준으로 작은 값과 큰 값을 분리하여 재귀적으로 정렬한다. 평균 시간 복잡도는 O(n log n)이다.

2. 탐색 알고리즘

탐색은 원하는 데이터를 찾는 작업이다. 대표적인 탐색 알고리즘으로는 이진 탐색, BFS, DFS가 있다.

• 이진 탐색: 정렬된 데이터에서 절반씩 범위를 좁혀가며 탐색한다. 시간 복잡도는 O(log n)이다.
• BFS (너비 우선 탐색): 그래프에서 가까운 노드부터 탐색한다. 큐를 사용한다.
• DFS (깊이 우선 탐색): 그래프에서 깊은 노드부터 탐색한다. 스택이나 재귀를 사용한다.

3. 그래프 알고리즘

그래프는 노드와 간선으로 이루어진 자료 구조다. 그래프 알고리즘은 연결된 데이터를 다룰 때 사용된다.

• 다익스트라 알고리즘: 가중치가 있는 그래프에서 최단 경로를 찾는다. 우선순위 큐를 사용한다.
• 플로이드-워셜 알고리즘: 모든 노드 쌍 간의 최단 경로를 찾는다. 시간 복잡도는 O(V^3)이다.
• 크루스칼 알고리즘: 최소 스패닝 트리를 찾는다. 간선을 정렬한 뒤, 사이클이 생기지 않게 선택한다.
• 프림 알고리즘: 최소 스패닝 트리를 찾는 또 다른 방법이다. 우선순위 큐를 사용한다.

4. 동적 프로그래밍 (DP)

동적 프로그래밍은 큰 문제를 작은 문제로 나누어 푸는 기법이다. 중복되는 계산을 피하기 위해 메모이제이션을 사용한다.

• 피보나치 수열: 재귀적 구현 대신 DP를 사용해 효율적으로 계산한다.
• 배낭 문제: 제한된 무게 내에서 최대 가치를 찾는다.
• 최장 공통 부분 수열 (LCS): 두 문자열 간의 가장 긴 공통 부분 수열을 찾는다.

5. 문자열 알고리즘

문자열 처리와 관련된 알고리즘이다. 패턴 매칭이나 문자열 조작에 사용된다.

• KMP 알고리즘: 문자열에서 특정 패턴을 효율적으로 찾는다. 시간 복잡도는 O(n + m)이다.
• 트라이(Trie): 문자열 집합을 효율적으로 저장하고 탐색한다.
• 라빈-카프 알고리즘: 해싱을 사용하여 특정 패턴을 찾는다.

6. 분할 정복

분할 정복은 문제를 작은 단위로 나누고 각각을 해결한 뒤 합쳐서 최종 결과를 얻는 방법이다. 대표적으로 퀵 정렬, 병합 정렬이 있다.

7. 그리디 알고리즘

그리디 알고리즘은 매 단계에서 가장 좋은 선택을 하여 최적의 결과를 얻는 기법이다. 하지만 항상 최적의 해를 보장하지는 않는다.

• 동전 거슬러주기 문제: 큰 단위의 동전부터 선택한다.
• 활동 선택 문제: 최대한 많은 활동을 선택하기 위해 종료 시간이 가장 빠른 활동부터 선택한다.

8. 백트래킹

백트래킹은 가능한 모든 경우를 탐색하면서 조건에 맞는 해를 찾는다. 재귀를 활용하며, 조건을 만족하지 않으면 되돌아간다.

• N-Queens 문제: 체스판 위에 N개의 퀸을 놓는 방법을 찾는다.
• 부분 집합 문제: 모든 부분 집합을 생성한다.

9. 해시 및 자료 구조

효율적인 데이터 저장 및 탐색을 위해 다양한 자료 구조와 해시 기법이 사용된다.

• 해시 테이블: 키-값 쌍을 저장하고 탐색한다. 평균 시간 복잡도는 O(1)이다.
• 스택과 큐: LIFO와 FIFO 구조를 사용한다.
• 힙(Heap): 우선순위 큐 구현에 사용되며, 최소/최대 값을 빠르게 찾는다.

10. 기타 알고리즘

특정 상황에서 유용한 알고리즘이다.

• 유니온-파인드: 그래프의 연결 요소를 관리한다.
• 에라토스테네스의 체: 소수를 빠르게 찾는다.
• 투 포인터: 배열이나 리스트에서 두 개의 포인터를 사용해 문제를 푼다.

코딩 테스트를 준비하면서 위 알고리즘을 체계적으로 학습하고, 관련 문제를 꾸준히 풀어나가는 것이 중요할 것이다.