한켤레

Dynamic Programming(다이나믹 프로그래밍) 복잡한 문제를 효율적으로 해결하기 위한 알고리즘 설계 기법이다. 다이나믹 프로그래밍은 주어진 문제를 여러 하위 문제로 나누어 해결한 다음에 이를 결합하여 전체 문제의 최적해를 구하는 방식으로 작동한다. 중복되는 하위 문제들을 반복적으로 해결함으로써 중복 계산을 피하고 효율적인 결과를 얻을 수 있다. 다이나믹 프로그래밍의 핵심 아이디어는 "작은 문제의 최적해는 큰 문제의 최적해를 포함한다"라는 것이다. 다시 말해서, 문제를 작은 부분 문제로 나누고, 각 부분 문제의 최적해를 계산하여 이를 저장하고 재사용하여 전체 문제의 최적해를 구하는 방식이다. 다이나믹 프로그래밍의 요소 1. Optimal sub-structure : 큰 문제를 작은 문제로 쪼갠다..

Bellman-Ford Algorithm(벨만-포드 알고리즘) 벨만-포드 알고리즘은 단일 출발점 최단 경로 문제를 해결하는 알고리즘이다. 주어진 weight가 있는 방향 그래프에서, 하나의 출발점에서 다른 모든 정점까지의 최단 경로를 찾는다. 또한, negative weight를 가진 간선이 존재하는 그래프에서 동작한다. 다만 negative cycle이 생성될 때, 최단 경로는 정의되지 못한다. 아래는 예시다. 장점과 단점 장점 - negative edge weight를 다룰 수 있음 - weight가 변경되어있을 때, 어느 정도의 유연성은 제공 단점 - 다익스트라 알고리즘보다 느린 시간 복잡도를 지님 동작 과정 1. 모든 vertex의 최단 거리 값을 무한대로 초기화한다. 출발 정점의 최단 거리 값은..

weighted graph에서 가중치가 음인 경우와 음이아닌 경우에 따른 방법이 다르다. - All nonnegative weights : Dijkstra - If there are negative weights : Bellman-Ford Dijkstra's Algorithm(다익스트라 알고리즘) 다익스트라 알고리즘은 하나의 출발점으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이다. 이 알고리즘은 가중치가 있는 그래프에서 최단 경로 문제를 효율적으로 해결하기 위해 사용된다. 다익스트라 알고리즘은 그리디 알고리즘의 한 종류로, 매 단계에서 가장 가까운 정점을 선택하여 최단 경로를 찾아간다. 동작 과정 1. 그래프에서 출발 정점을 선택하고, 출발 정점을 기준으로 최단 거리를 저장하는 배열을 초기화한..

Kosaraju's algorithm(코사라주 알고리즘) 코사라주 알고리즘은 strongly connected component를 찾는 데 사용되는 그래프 알고리즘이다. 이 알고리즘은 그래프의 구조를 기반으로 각 vertex를 그룹화하고, strongly connected component를 식별하는 데에 사용된다. 동작 과정 1. DFS를 수행해서 DFS forest - 시작 정점은 임의로 선택함 - finish time 추적 2. 그래프의 모든 edge 반전 3. DFS를 다시 실행하여 다른 DFS forest를 만듬 - 이번에는 첫 번째 DFS 실행부터 finish time의 역순으로 vertex를 시작 4. SCCs는 두 번째 DFS forest의 다른 tree임 특징 * SCC 그래프는 Dire..

Strongly Connected Components(SCCs) SCCs는 서로에게 도달할 수 있는 모든 vertex를 그룹으로 묶는 개념이다. 강하게 연결된 컴포넌트는 그래프 내에서 강한 의존 관계를 가지는 vertex들의 집합을 나타낸다. 특징은 다음과 같다. - SCCs 내의 어떤 vertex에서도 다른 모든 정점으로의 경로가 존재 - SCCs 내의 vertex들은 서로에게 강한 의존성이 있어서 한 Component에 속한 vertex 중 하나를 제거하면 다른 vertex들과의 연결이 끊어짐 SCCs를 찾는 방법 1. 가능한 모든 것을 찾아보고 체크 2. 각각의 (u, v)에 대하여 DFS를 실행해서 u에서 v, v에서 u에 대한 경로가 있는지 파악한다. 그렇게 해서 SCCs를 찾기 위한 정보를 모..

BFS(Breadth-First Search) 루트 vertex(또는 다른 임의의 vertex)에서 시작해서 인접한 vertex를 먼저 탐색하는 방법이다. 시작 vertex로부터 가까운 vertex를 먼저 방문하고 멀리 떨어져 있는 vertex를 나중에 방문하는 방법이다. 즉, 깊게 탐색하기 전에 넓게 탐색하는 것이다. 동작 방식 1. 시작 vertex를 큐에 넣고 방문 표시를 한다. 2. 큐에서 vertex를 하나씩 꺼내서 해당 vertex와 인접한 모든 vertex를 방문한다. 3. 방문하지 않은 인접 vertex를 큐에 넣고 방문 표시를 한다. 4. 큐가 빌 때까지 2~3단계를 반복한다. 의사 코드(pesudo code) BFS(graph, start_vertex): visited = set() #..

Topological Ordering(위상 정렬) 위상 정렬 알고리즘은 Directed Graph(유향 그래프)에서 vertex들을 정렬하는 알고리즘이다. 이 때, 그래프의 edge(간선)은 방향성을 가지며 한 정점에서 다른 정점으로 향한다. 위상 정렬 알고리즘은 DAG일 경우에만 적용할 수 있다. DFS를 적용하여 구한다. ※ DAG(Directed Acyclic Graph)란? 방향을 가진 간선을 따라가다보면, 방문했던 vertex를 다시 방문하게 되고 그것이 반복하게 되는 Graph가 있다. 그것을 우리는 순환 그래프라고 한다. DAG는 그것의 반대인, 순환하는 Cycle이 생기지 않고 일방향성만 가진다는 것을 말한다. 알고리즘 동작 방식 1. 진입 차수(in-degree)가 0인 vertex를 선..

DFS DFS, '깊이 우선 탐색' 알고리즘은 그래프에서 모든 정점을 방문하는 알고리즘 중 하나이다. DFS는 스택 또는 재귀 함수를 이용해서 구현할 수 있다. 의사코드 먼저 의사 코드를 작성하면 다음과 같다. DFS(w, currentTime): w.startTime = currentTime// vertex의 시작시간 표시 currentTime += 1 Mark w as in progress// 진행 중인 vertex 표시 for v in w.neighbors: if v is unvisited:// 방문하지 않은 vertex라면.. currentTime = DFS(v, currentTime) currentTime += 1 w.finishTime = currentTime// 이웃 vertex 중에 방문하..

알고리즘을 이용해 코드를 작성했을 때, 성능을 평가할 때, 확인해야 할 요소가 두 가지이다. Proving correctness / Proving complexity correctness는 코드의 결과가 정확한지에 대한 요소이고, complexity에 관련된 것은 또 두 가지가 있다. 시간과 공간이다. 얼마나 빠르게 코드가 진행되는지, 얼마나 효율적으로 메모리 공간을 사용하여 진행되는지에 대한 것이다. Insertion Sort는 삽입 소팅이라고 한다. 한 인덱스의 숫자를 다른 인덱스의 숫자와 비교했을 때, 크거나 or 작으면 그 다음의 행동을 진행하는 알고리즘이다. 코드를 한 번 살펴보자. 아무렇게나 정렬되어있는 숫자 배열을 오름차순으로 정렬하는 알고리즘이다. # INSERTION - SORT(A) f..