원활한 코딩테스트를 위해 공부해볼만한 토픽들 ft.ChatGPT

코딩 테스트를 위한 알고리즘 공부 방향성을 잡아줄 좋은 글을 찾아 해당 토픽들의 간단한 개념 및 용처를 챗지피티를 통해 정리해 보았다.

1. 완전탐색 (Brute Force): 가능한 모든 경우의 수를 직접 검사하여 문제의 해를 찾는 방법. 소규모 데이터셋에서 모든 가능성을 탐색할 때 사용.
2. 그리디 (Greedy): 매 순간 최적이라고 생각되는 선택을 하여 최종적인 해답에 도달하는 방식. 각 단계에서의 최적의 해가 전체에서도 최적의 해를 보장하는 경우에 적합.
3. 분할 정복 (Divide and Conquer): 큰 문제를 작은 문제로 나누어 해결한 뒤, 작은 문제의 해를 결합하여 원래 문제의 해를 찾는 방식. 정렬, 고속 푸리에 변환 등에 사용.
4. BFS (Breadth-First Search): 너비 우선 탐색으로, 가까운 노드부터 차례대로 탐색하는 알고리즘. 최단 경로 찾기나 레벨별 탐색에 유용.
5. DFS (Depth-First Search): 깊이 우선 탐색으로, 가능한 멀리 있는 노드까지 탐색하며 미로 찾기, 사이클 검출에 적합.
6. DP (Dynamic Programming): 복잡한 문제를 간단한 여러 개의 하위 문제로 나누어 푸는 방법, 중복 계산을 피하기 위해 이전에 계산한 값을 저장. 최적화 문제나 카운팅 문제에 사용.
7. 최단경로: 그래프에서 두 노드 사이의 가장 짧은 경로를 찾는 문제, 다익스트라, 벨만-포드, 플로이드-워셜 알고리즘 등이 있음.
   1. 다익스트라(Dijkstra) 알고리즘: 시작 정점으로부터 다른 모든 정점까지의 최단 거리를 구하는 알고리즘으로, 가중치가 음수인 간선이 없을 때 사용 가능.
   2. 벨만-포드(Bellman-Ford) 알고리즘: 시작 정점으로부터 다른 모든 정점까지의 최단 거리를 구하는 알고리즘으로, 가중치가 음수인 간선이 있어도 사용 가능하며 음수 사이클의 존재 여부도 판별. 복잡도는 O(VE)로, 다익스트라 알고리즘보다 느림.
   3. 플로이드-워셜(Floyd-Warshall) 알고리즘: 모든 정점 쌍 사이의 최단 거리를 구하는 알고리즘으로, 가중치가 음수인 간선이 있어도 사용할 수 있고, 모든 정점 사이의 최단 거리를 한 번에 알 수 있는 것이 장점. 복잡도는 O(V^3)으로, 큰 그래프에서는 비효율적.
8. 이분탐색 (Binary Search): 정렬된 리스트에서 특정 값의 위치를 빠르게 찾는 알고리즘. 값이나 조건을 만족하는 범위를 찾을 때 사용.
9. 슬라이딩 윈도우 (Sliding Window): 배열이나 리스트의 일정 범위의 요소를 윈도우처럼 슬라이드하면서 문제를 해결하는 방법. 연속된 데이터의 최댓값, 최솟값, 합계 등을 효율적으로 계산할 때 사용.
10. 투 포인터 (Two Pointers): 시작점과 끝점 두 개의 포인터를 이용해 범위를 조절하며 문제를 해결하는 방식. 정렬된 배열에서 두 수의 합, 연속 부분 수열 찾기 등에 유용.
11. 유니온 파인드 (Union-Find): 집합을 표현하고, 두 원소가 같은 집합에 속하는지를 판단하는 자료구조. 그래프의 연결성, 서로소 집합 문제에 사용.
12. 최소 신장 트리 (Minimum Spanning Tree): 그래프 내의 모든 정점을 최소한의 비용으로 연결하는 트리. 프림, 크루스칼 알고리즘 등이 있음.
13. BBST (Balanced Binary Search Tree): 이진 탐색 트리의 균형을 맞추어 탐
14. 세그먼트 트리 (Segment Tree): 구간 쿼리 문제(예: 구간의 합, 최소값, 최대값 조회 등)를 빠르게 처리하기 위한 이진 트리 기반의 자료구조로, 변경이 잦은 데이터 집합에서도 빠른 연산을 지원함.