개발일지

벨만-포드 알고리즘개요　이전 게시물들에서는 그래프 내의 두 정점 사이의 최단 경로를 찾는 방법들에 대해 다루었다. 특히 가중치가 부여된 그래프에서 최단 경로를 찾는 대표적인 방법인 다익스트라 알고리즘은 그리디 알고리즘의 원리를 활용해 각 단계에서 최단 경로를 계산한다. 이 방법은 효율성 면에서 뛰어나지만, 한 가지 큰 제약 사항이 존재하는데, 바로 음의 가중치를 가진 에지를 처리할 수 없다는 점이다. 다익스트라 알고리즘이 음의 가중치를 처리하지 못하는 이유는 그 알고리즘의 핵심 원리에 있다. 이 알고리즘은 '현재까지 발견된 최단 경로'를 기반으로 작동한다. 그리고 이 경로는 더 이상 개선될 수 없다고 가정한다. 즉, 한 번 '최단'으로 판단된 경로는 그 이후에 변경되지 않는다. 　하지만 음의 가중치가 그..

다익스트라 알고리즘개요　그래프에서 단일 시작 최단 경로 문제는 시작 정점과 목적 정점이 주어졌을 때, 시작 정점에서 목적 정점까지 이어지는 최소 비용 경로를 찾는 문제다. 이 문제를 해결하는 여러 알고리즘 중 하나가 다익스트라 알고리즘(Dijkstra's algorithm)이다. 　다익스트라 알고리즘은 음수 가중치를 갖지 않는 그래프에서 사용되는 최단 경로 탐색 알고리즘이다. 이 알고리즘은 프림의 최소 신장 트리(MST) 알고리즘을 변형한 것으로, 다음과 같은 절차를 따른다. 시작 노드를 설정시작 노드의 거리 값은 0으로, 이를 제외한 모든 노드의 거리 값은 무한대로 초기화모든 거리 값을 최소 힙에 추가최소 힙으로부터 꺼낸 정점 U와 인접한 모든 정점 V에 대해, 만약 V의 거리 값이 (U의 거리 값 +..

프림의 최소 신장 트리 알고리즘프림 알고리즘　프림 알고리즘(Prim's Algorithm)은 최소 신장 트리 문제를 해결하는 그리디 알고리즘 중 하나다. 그래프의 임의의 정점에서 시작하여, 그래프의 모든 정점을 포함하고 모든 간선의 가중치 합이 최소인 트리를 찾는 알고리즘으로서, BFS의 동작 방식과 유사하다. 동작 과정은 다음과 같다. 시작 노드를 선택하고, 선택한 정점을 트리에 추가선택한 노드에 인접하고 트리에 연결되지 않은 노드로 연결된 간선들 중, 가장 작은 가중치를 가진 간선을 추가그래프의 모든 노드가 트리에 추가될 때까지 반복예시 　다음과 같은 그래프가 있다고 가정하고, 이러한 그래프에 프림 알고리즘을 적용하여 최소 신장 트리를 구하는 과정을 살펴보자.   　먼저 시작 정점을 제외하고, 모든 ..

그래프 탐색개요　그래프 탐색(graph traversal problem), 또는 그래프 순회 문제(graph search problem)는 그래프의 일련의 정점을 체계적으로 방문하는 문제를 의미한다. 주어진 그래프 G = 에서 특정 정점 s를 시작점으로 하여, 모든 정점 v ∈ V를 한 번씩 방문하는 것이 이 문제의 목표다. 이 과정에서 방문된 정점의 순서는 탐색 알고리즘에 따라 달라진다. 탐색은 주로 그래프의 구조를 이해하거나, 특정 경로를 찾는 등의 목적으로 사용된다. 이를 통해 네트워크 연결 상태, 최단 경로, 사이클 등 그래프의 다양한 특성을 분석할 수 있다. 　그래프 탐색은 다양한 응용 분야에서 중요한 역할을 수행한다. 예를 들어, 네트워크 라우팅, SNS에서 친구 추천, 웹 크롤러 등에서 그래..

그래프 컬러링개요　그래프 컬러링(graph coloring) 문제는 주어진 그래프에서 서로 인접한 정점끼리 같은 색을 갖지 않도록 모든 정점에 색상을 지정하는 것이다. 이때 에지의 가중치는 사용하지 않는다. 컬러링의 주요 종류는 다음과 같다. 정점 컬러링: 가장 기본적인 형태의 그래프 컬러링. 인접한 정점들은 다른 색깔을 가져야 한다는 규칙을 따름.에지 컬러링: 각 에지를 색칠하는 데 중점을 두며, 어떤 두 에지도 같은 색깔을 가질 수 없음. 이 규칙은 에지가 공유하는 정점에도 적용됨.착색수(chromatic number): 그래프를 적절히 색칠하는 데 필요한 최소 색깔 수 (NP-완전 문제) 　그래프 컬러링은 택시 예약 스케줄 작성, 스도쿠 퍼즐 풀기, 시험 시간표 작성 등을 그래프로 모델링한 후 컬러..

시간 복잡도　지난 포스팅에서 디스조인트-셋 자료구조를 사용하면 시간 복잡도가 O(Ea(V))로 줄어들며, 정점이 많은 그래프에서 큰 성능 차이가 발생한다고 하였다. 이는 디스조인트-셋 데이터 구조에 특정 휴리스틱을 적용했다는 것을 의미하는데, 여기서 휴리스틱(heuristics)이란 체계적이고 합리적인 판단을 할 필요가 없는 상황에서 신속하게 사용하는 어림짐작의 기술, 즉 항상 최적의 해를 보장하진 않지만 신속하게 답을 구할 수 있는 접근 방식이다. 이 휴리스틱은 Union by rank와 Path compression이다. 　Union by rank는 두 트리를 합칠 때 더 작은 랭크(rank)의 트리를 더 큰 랭크의 트리 아래에 두는 방법이고, Path compression은 find 연산을 수행할 ..

최소 신장 트리 문제그리디 알고리즘 요구 조건　앞 절에서 모든 문제에 그리디 방식을 적용할 수 있는 것은 아니라고 했다. 즉, 최적 부분 구조(optimal substructure)와 그리디 선택(greedy choice)이라는 두 가지 속성을 모두 갖는 문제만 그리디 접근 방식으로 최적의 솔루션을 구할 수 있다.  　최적 부분 구조는 큰 문제의 최적해가 부분 문제의 최적의 해답들로 구성될 수 있는 구조를 의미한다. 그리디 선택 속성은 현재의 선택이 미래의 선택에 영향을 미치지 않고, 각 단계에서 최적의 선택을 하면 전체적으로 최적의 해답을 얻을 수 있는 것을 의미한다. 　이러한 특성에 대해 이해하기 위해 크루스칼 최소 신장 트리 알고리즘에 대해 알아보도록 하자.개요　최소 신장 트리(Minimum Spa..

배낭 문제개요　배낭 문제(knapsack problem)는 조합 최적화의 한 부분으로, 최적화 이론 및 적용을 이해하는데 근본적인 문제다. 즉, 이 문제는 제한된 무게(또는 부피)의 배낭에 가장 가치 있는 물품들을 적절히 담는 방법을 찾는 것이다. 여기서 물건들은 각각 특정한 무게와 가치를 갖는다.본문 　배낭 문제는 주로 0-1 배낭 문제와 분할 가능 배낭 문제 두 가지 유형으로 분류된다. 일반 배낭 문제라고도 불리는 0-1 배낭 문제는 각각의 아이템이 배낭에 포함되거나 포함되지 않는 두 가지 상태만을 갖는다. 따라서, 아이템을 쪼개서 담는 것이 불가능하다. 이 문제는 NP-완전 문제로 분류되어, 이를 다항 시간 내에 결정적으로 풀 수 있는 알고리즘이 알려져 있지 않다.   　반면, 분할 가능 배낭 문제..

그리디 알고리즘개요　그리디(greedy) 알고리즘은 매 시점에서 가장 이상적인 선택을 지향하는 알고리즘이다. 이 방법론은 지역(local)적으로 최적화된 해답들을 도출하면서, 그 해답들로부터 전역(global)적인 최적해를 구축하는 전략을 채택한다. 그리디 알고리즘은 각 선택의 순간마다 최적의 결정을 내리지만, 이 일련의 결정들이 꼭 최적의 결과를 보장하는 것은 아니다. 그러나 특정 문제에 대해서는 이 알고리즘이 실제로 최적의 결과를 보장하기도 하고, 복잡하고 시간 소모적인 문제를 효과적으로 근사해결하는 데에 종종 활용되기 때문에 그 가치는 높다고 할 수 있다. 　이러한 그리디 알고리즘의 단순하고 직관적인 접근법은 그것의 한계를 동시에 내포하고 있다. 즉, 그리디 특성을 지닌 문제에 대해서만 그리디 알고..

맵리듀스개요　지금까지 우리가 다룬 분할 정복은 주로 알고리즘 설계 패러다임으로 간주했다. 이번엔 이 방식을 일반 컴퓨팅 환경을 초월한 고성능 컴퓨터에 적용하는 방법에 대해 논의하려고 한다. 이러한 확장의 핵심에는 컴퓨터 클러스터(Cluster)라는 개념이 있다. 컴퓨팅 클러스터, 즉 복수의 컴퓨터를 네트워크로 연결하여 단일 시스템처럼 작동하게 하는 방식으로, 이를 통해 더 복잡하고 규모가 큰 문제를 효과적으로 해결할 수 있다. 　하지만, 단순히 컴퓨팅 리소스를 확장하는 것만으로 대규모 데이터 처리에 필요한 세밀함과 효율성을 보장하긴 어렵다. 이러한 관점에서 맵리듀스(MapReduce)는 대용량 데이터를 효과적으로 처리할 수 있는 프로그래밍 모델이다. 맵리듀스는 컴퓨팅 클러스터를 활용해 거대한 양의 데이터..