May, I Try
2024. 1. 26. 23:19
2024. 1. 26. 23:19
TL;DR
알고리즘이란,
문제를 해결해나가는 절차임.
특히 컴퓨터 과학 분야에서는
데이터를
효율적으로 정렬/탐색하는 방법론이라고 볼 수 있음.
데이터의 특성(수량, 형태 등)과
저장소와 연산 환경의 특성(저장 공간, 컴퓨팅 파워 등)에 따라
주로 활용되는 알고리즘이 다름.
큰 분류로 보면
큰 그림 수준에서의 절차 설계의 방향을 제시하는
<완전탐색>, <분할정복>,
<다이나믹 프로그래밍>, <그리디 알고리즘>으로 나눌 수 있음.
위의 큰 분류 알고리즘의 방향에 따라
구체적 절차를 제시하는 세부 알고리즘이 아주 많음.
<선형탐색>, <조합탐색>, <너비우선탐색>, <깊이우선탐색>, <백트래킹>,
<병합정렬>, <퀵정렬>, <이진 탐색>,
<플로이드 와샬>, <다익스트라>, <크루스칼>, <프림>... 등
우리는
당면한 문제의
핵심 과제가 무엇이고,
다뤄야 할 데이터가 어떤 상태이며,
어떤 환경에서 코드를 돌려야 하는지 잘 판단하여,
효율적으로 작동할 알고리즘을 구현하는 능력을 키워야 함.
알고리즘과 자료구조를 공부한 지 오늘로 2주가 되었다.
꼬리에 꼬리를 물고 떠오르는 수많은 "왜"들을 애써 외면하며, 어찌어찌 전체 겉핥기는 마쳤다.
통달을 하기엔 너무도 짧은 시간이었고, 외면당한 "왜"들이 내내 마음에 걸린다.
그래서 일단 지금은 밑그림을 그려놓고, 앞으로 차근차근 개선 보완하여
선명하고 자세한 개념 지도를 완성해보려고 한다.
아래는 내가 지난 2주 간 공부한 것을 바탕으로
알고리즘 전체를 러프하게 정리한 것이다.
빠진 것, 틀린 것들이 많을 수 있다.
1. 완전 탐색 Exhaustive Search (Brute Force)
- 주요 아이디어: 모든 데이터를 하나하나씩, 혹은 모든 경우의 수에 대해 전부 탐색하는 방법
1-a. 선형 탐색
- 자료구조: 배열, 리스트
- 문제: 배열 또는 리스트 내 특정 값 찾기
- 기법: 모든 요소를 처음부터 끝까지 순차적으로 확인
1-b. 조합/순열 탐색
- 자료구조: 배열, 리스트
- 문제: 주어진 집합에서 가능한 모든 조합/순열 찾기
- 기법: 재귀나 반복문으로 모든 경우의 수를 찾아냄
1-c. 백트래킹
- 자료구조: 그래프, 트리
- 문제: 조합, 순열, 부분 집합 등 문제 해결
- 기법: 가능한 모든 경우의 수를 탐색하되, 불필요 경로는 조기에 차단
1-d. 너비 우선 탐색 BFS
- 자료구조: 비가중 무방향성 그래프
- 문제: A지점에서 B지점까지 최단 거리 경로 찾기
- 기법: 그래프에서 레벨이 같은 노드 단위(가로 방향)로 경로 탐색
1-e. 깊이 우선 탐색 DFS
- 자료구조: 비가중 무방향성 그래프
- 문제: 그래프에서 가능한 모든 경로를 탐색
- 기법: 재귀로 최대한 깊게 그래프를 탐색해 내려간 후 다시 올라오면서 경로 탐색
2. 분할 정복 Divide and Conquer
- 주요 아이디어: 복잡하고 큰 문제를 독립적인 작은 문제로 쪼개어 해결한 후, 결과들을 마지막에 합침
2-a. 병합 정렬 Merge Sort
- 자료구조: 배열, 리스트
- 문제: 데이터 정렬
- 기법: 데이터를 반으로 나눈 뒤 정렬하고 병합
2-b. 퀵 정렬 Quick Sort
- 자료구조: 배열, 리스트
- 문제: 데이터 정렬
- 기법: 피봇을 기준으로 데이터를 분할하고 분할된 각 부분을 재귀적으로 정렬
2-c. 이분 탐색 Binary Search
- 자료구조: 그래프, 트리
- 문제: 정렬된 데이터에서 특정 값 찾기
- 기법: 대소를 비교하여 탐색의 범위를 절반으로 줄여나감
3. 동적 프로그래밍 Dynamic Programming
- 주요 아이디어: 복잡하고 큰 문제를 작은 부분들로 쪼개 해결해나가는데, 작은 부분 해결 시 도출된 결과를 저장해두고, 이후 문제 해결시 저장된 결과를 참조하여, 전체적인 관점에서 최선의 선택을 하여 결과를 도출.
3-a. 플로이드 워셜 Floyd-Warshall
- 자료구조: 가중치가 있는 그래프 (방향성 관계x)
- 문제: 모든 정점에서 모든 정점으로 가는 최소 비용 계산
- 기법: 추후 추가 예정
4. 탐욕 알고리즘 Greedy
- 주요 아이디어: 복잡하고 큰 문제를 작은 부분들로 쪼개 해결해나가는데, 작은 부분을 해결하는 딱 그 시점에 가장 최선의 선택을 하여 결과를 도출
4-a. 크루스칼 Kruskal
- 자료구조: 가중치가 있는 그래프
- 문제: 최소 신장 트리 Minimum Spanning Tree 구하기
- 기법: 가장 가벼운 가중치를 가진 엣지부터 선택하여 그래프를 트리로 재구성하기
4-b. 프림 Prim
- 자료구조: 가중치가 있는 그래프
- 문제: 최소 신장 트리 Minimum Spanning Tree 구하기
- 기법: 임의의 정점 하나에서 시작하여 점진적으로 가장 작은 가중치를 갖는 엣지를 이어서 트리로 재구성
4-c. 다익스트라 Dijkstra
- 자료구조: 가중치가 있는 그래프 (양의 가중치)
- 문제: 정점 하나로부터 다른 모든 정점으로 가려고 할때, 최소 비용으로 연결할 수 있는 경로 계산
- 기법: 현재 정점에서 최소 비용 정점을 선택하고, 그 정점에서 또 다른 최소 비용 정점을 선택해가며 경로를 만들어감
5. 기타 분류
5-a. 위상 정렬 Topological Sort
- 자료구조: 방항성이 있는 비순환 그래프
- 문제: 그래프의 모든 정점을 순서를 보존하여 한 방향으로 정렬하기
- 기법: 특수한 형태의 그래프에서만 활용되는 알고리즘임
5-b. 버블/삽입/선택 정렬
- 자료구조: 배열
- 문제: 배열 내 모든 요소를 오름차순/내림차순으로 정렬
- 기법: 정렬 여부, 데이터 크기 등의 상태에 따라 적절히 선택해야 함. 그러나 데이터가 아주 큰 경우 효율이 떨어져서 정렬 알고리즘 학습용 정도로만 활용 됨.
