August 04, 2024
복잡도란 복잡도(Complexity)란 알고리즘의 성능을 나타내는 척도이며, 일반적으로 시간 복잡도와 공간 복잡도로 나뉜다. 시간 복잡도 알고리즘의 실행 시간, 즉 연산 수행 횟수를 측정하는 척도이다. 공간 복잡도 알고리즘이 실행되는 동안 필요한 메모리의 양을 측정하는 척도이다. 효율적인 알고리즘을 사용한다고 했을 때, 시간 복잡도와 공간 복잡도는 서로 …
August 11, 2024
그래프 탐색 이전 글에서 시간 복잡도를 설명하며 선형 탐색과 이진 탐색에 대해 다루었다. 두 알고리즘 모두 선형적 구조에서 작동하는 탐색 방식으로, 그래프 탐색은 비선형적 구조를 탐색하는 알고리즘이며 조금 다른 접근 방식이 필요하다. 그래프 이론 그래프는 노드(Node, 또는 Vertex)와 간선(Edge)으로 이루어진 비선형 자료 구조이다. 노드는 객체…
August 12, 2024
정렬 데이터를 특정한 기준에 따라 순서대로 나열하는 것을 정렬(Sort)이라 한다. 프로그램에서는 데이터를 효율적으로 가공하거나 활용하기 위해 먼저 정렬을 수행하는 경우가 많다. 아래는 프로그램에서 사용되는 대표적인 정렬 알고리즘들이다. 선택 정렬: O(N^2). 앞에서부터 차례대로 가장 작은 원소를 찾아 현재 위치에 놓는 방식이다. 삽입 정렬: O(N^…
August 14, 2024
다이나믹 프로그래밍 다이나믹 프로그래밍(DP)은 복잡한 문제를 해결하기 위해 작은 부분 문제로 나누고, 그 결과를 저장하여 동일한 계산을 반복하지 않도록 최적화하는 기법이다. 이 접근법은 주로 점화식(Recurrence Relation)을 기반으로 하며, 대표적인 예로 피보나치 수열, 배낭 문제, 최장 공통 부분 수열(LCS) 등이 있다. 점화식과 메모이…
August 22, 2024
다익스트라 알고리즘 다익스트라 최단 경로 알고리즘은 그래프 이론에서 중요한 알고리즘 중 하나로, 특정 출발점에서 다른 모든 점으로 가는 최단 경로를 찾는 데 사용된다. 이 알고리즘은 단방향 그래프나 가중치가 있는 그래프에서 특히 유용하다. 다익스트라는 그리디 알고리즘에 속하며, 매 단계에서 ‘가장 비용이 적은 노드’를 선택하여 최단 경로를 확정한다. 방…
August 26, 2024
서로소 집합 서로소 집합이란, 공통 원소가 없는 두 집합을 의미한다. 예를 들어, 집합 A와 집합 B가 있을 때, A와 B가 서로소 집합이라면 A와 B는 공통 원소를 갖지 않는다. 서로소 집합 자료구조는 원소들을 서로소 부분 집합들로 나누어 관리하는 자료구조이다. 이 자료구조는 'union-find' 자료구조라고도 불리며, 주요 연산으로는 'union'…
August 28, 2024
스패닝 트리 스패닝 트리 또는 신장 트리(Spanning Tree)는 모든 노드를 포함하며 사이클이 존재하지 않는 부분 그래프를 의미한다. 즉, 모든 노드가 서로 연결되어 있되, 하나의 노드에서 나온 간선이 자기 자신으로 돌아오지 않아야 신장 트리의 조건을 만족한다. 최소 스패닝 트리 간선의 가중치 또는 비용이 주어질 때, 신장 트리를 이루는 모든 간…
February 01, 2025
위상 정렬 위상 정렬(Topological Sort)은 방향성 그래프에서 각 정점을 선후 관계에 맞게 정렬하는 알고리즘이다. 이 알고리즘은 주로 작업이나 이벤트의 순서를 결정할 때 사용된다. 예를 들어, 여러 작업을 수행할 때 어떤 작업이 다른 작업보다 먼저 실행되어야 한다면, 이를 그래프 형태로 표현하고 위상 정렬을 통해 적절한 실행 순서를 도출할 수 …
February 04, 2025
벨만-포드 알고리즘 벨만-포드 알고리즘은 최단 경로를 구하는 알고리즘 중 하나로, 다익스트라 알고리즘과 비슷한 역할을 한다. 하지만 중요한 차이점은 음수 가중치가 있는 그래프에서도 최단 경로를 구할 수 있다는 부분이다. 이 점 때문에 다익스트라와는 다른 방식으로 동작한다. 다익스트라 알고리즘과의 차이 다익스트라 알고리즘은 음수 가중치가 없는 그래프에서 사…