고급 알고리즘 완전정복 - 세그먼트 트리부터 위상정렬까지
November 15, 2025코딩 테스트와 실무에서 자주 사용되는 고급 알고리즘을 완벽 정리. 세그먼트 트리, 펜윅 트리, 유니온 파인드, 최소 공통 조상(LCA), 강한 연결 요소(SCC), 위상 정렬, 최소 신장 트리(MST), 최대 유량 등 실전 문제 해결에 필요한 모든 알고리즘을 JavaScript로 구현합니다.
13 posts tagged with "Algorithm"
퀵 정렬 (Quick Sort)
November 06, 2025퀵 정렬은 분할 정복 알고리즘으로 평균적으로 매우 빠른 정렬 알고리즘이다. 피벗을 선택해 기준으로 삼고, 작은 값과 큰 값을 분할해 재귀적으로 정렬한다.
KMP 알고리즘 (Knuth-Morris-Pratt)
November 01, 2025문자열 검색을 효율적으로 수행하는 알고리즘. 실패 함수(Failure Function)를 이용해 불필요한 비교를 건너뛰며, 시간복잡도는 O(N+M)이다.
벨만-포드 알고리즘 (Bellman-Ford)
November 01, 2025음수 가중치가 있는 그래프에서 최단 경로를 구할 수 있는 알고리즘. 음수 사이클 감지도 가능하며, 시간복잡도는 O(VE)이다.
병합 정렬 (Merge Sort)
November 01, 2025분할 정복(Divide and Conquer) 기법을 사용하는 안정 정렬 알고리즘. 시간복잡도는 O(N log N)이며, 추가 공간이 필요하다.
최장 공통 부분수열 (LCS)
November 01, 2025두 문자열의 공통 부분수열 중 가장 긴 것을 찾는 동적 계획법 문제. 문자열 유사도 측정과 차이점 분석에 활용된다.
트리 순회 (Tree Traversal)
November 01, 2025이진 트리에서 노드를 방문하는 순서를 다르게 하는 세 가지 순회 방법. 전위, 중위, 후위 순회로 나뉘며 재귀 또는 스택으로 구현 가능하다.
너비 우선 탐색 (Breadth-First Search, BFS)
October 30, 2025그래프에서 시작 정점으로부터 가까운 정점부터 차례대로 탐색하는 알고리즘. 최단 간선 수 경로 탐색에 유용하며 큐(Queue)를 사용한다.
다익스트라 알고리즘 (Dijkstra)
October 30, 2025가중치가 모두 비음수인 그래프에서 한 시작 정점으로부터의 최단 경로를 구하는 알고리즘. 우선순위 큐(최소 힙)를 사용하면 효율적이다.
최소 동전 수 (Coin Change, DP)
October 30, 2025동적 계획법(DP)을 사용하여 특정 금액을 만들기 위한 최소 동전 개수를 구한다. 그리디가 항상 최적을 보장하지 않는 경우에도 최적해를 보장하는 방법이다.
이진 탐색 (Binary Search)
October 30, 2025정렬된 배열에서 중간값을 기준으로 탐색 범위를 절반으로 줄여가며 값을 찾는 알고리즘. 시간복잡도는 O(log N)이다.
깊이 우선 탐색 (Depth-First Search, DFS)
October 30, 2025그래프에서 한 경로를 가능한 깊게 따라간 뒤, 더 갈 곳이 없으면 되돌아오는 탐색 방법. 재귀 또는 스택을 사용하며, 연결 요소 탐색과 위상 정렬 등에 활용된다.
그리디 알고리즘 (Greedy Algorithm)
April 04, 2021그리디 알고리즘, 탐욕 알고리즘 이라고도 부른다. 그리드 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각 되는것을 선택해 나가는 방식이다.
All tags