유니온 파인드 그래프 노드가 존재할 때, 노드들은 서로 연결되어 집합을 형성한다. 노드가 서로 연결되며 집합을 형성하는 것을 합집합 연산으로 간주할 수 있으며, 특정 노드가 어떤 집합에 속하였는지 궁금할 수 있다. 이때 사용할 수 있는 알고리즘이 유니온 파인드 알고리즘이다. union 연산은 각 노드가 속한 집합을 하나로 합치는 연산이며, find 연산은 특정 노드 a에 관해 노드 a가 속한 집합의 대표 노드를 반환하는 연산이다. 이때 find 연산을 활용해 특정 노드 a, b가 속한 집합의 대표 노드가 동일한지 비교하여 두 노드가 같은 집합에 속하였는지 확인할 수 있다. 유니온(union) 연산 초기 노드가 위와 같이 있다고 가정하자. 유니온 파인드 알고리즘은 일반적으로 1차원 배열을 이용해 해당..

너비 우선 탐색 너비 우선 탐색 BFS 알고리즘 DFS와 유사한 그래프를 완전 탐색하는 알고리즘이다. 시작 노드에서 탐색할 분기를 정해 최대 깊이까지 탐색하는 DFS와는 다르게 시작 노드를 기준으로 가까운 노드부터 방문한다는 차이점이 있다. 너비 우선 탐색 역시 노드 수가 V, 간선 수가 E일 때 O(V + E)의 시간 복잡도 내에서 그래프를 완전 탐색할 수 있으며, 재귀 함수 형태로 구현하지 않기 때문에 DFS에서 고려해야 하는 사항인 스택 오버플로우를 고려하지 않아도 된다. 너비 우선 탐색 - 이론 깊이 우선 탐색에서는 스택 자료구조를 사용하였는데, BFS에서는 스택 대신 큐 자료구조를 사용한다. 후입선출의 특징을 가지는 스택 자료구조와는 다르게 큐는 선입선출 특징을 가지고 있다. DFS와 마찬가지..

깊이 우선 탐색 깊이 우선 탐색 DFS는 그래프 완전 탐색 알고리즘 중 하나로, 시작 노드에서 출발해 탐색할 분기를 정하여 최대 깊이까지 탐색을 수행한 후, 다음 분기로 이동하여 다시 깊이 우선 탐색을 수행하는 알고리즘이다. 노드 수가 V, 간선 수가 E일 때 O(V + E)의 시간 복잡도를 가지는 알고리즘이며, 스택 자료구조를 사용한다. DFS는 보통 스택 자료구조와 재귀 함수 형태를 이용하여 구현을 하는데, 이때 과도한 재귀 함수의 호출로 스택 오버플로우가 발생하지 않도록 주의해야 한다. 깊이 우선 탐색 - 이론 위에서 DFS는 스택 자료구조를 사용하는 알고리즘이라 하였다. DFS를 이용하기 위해 그래프를 연결 리스트 형태로 표현해야 한다는 것도 알아두자. DFS 방식의 핵심은 시작 노드를 스택에 ..

위상 정렬 위상 정렬이란 사이클이 없는 유향 그래프에서 노드 순서를 찾는 알고리즘이다. 여기서 유향 그래프는 방향성이 있는 그래프를 의미한다. 위상 정렬은 사이클이 없는 그래프에서 사용 가능한 알고리즘이며 노드 수가 V, 간선 수가 E일 때 O(V+E)의 시간 복잡도를 가진다. 노드의 순서를 찾는 특성 상 위상 정렬의 결과는 한 가지만 존재하지 않을 수 있다는 점을 참고하고, 위상 정렬에 대해 알아보자. 이 예시 그래프를 이용해 위상 정렬에 대해 알아보겠다. 먼저, 위상 정렬 알고리즘을 적용하기 위해서는 존재하는 노드의 '진입 차수'를 알아야 한다. 진입 차수란 노드 자신을 가리키는 간선의 개수로, 노드로 들어오는 간선의 개수를 뜻한다. 위 그래프에서 노드 1, 2, 5의 진입 차수는 0이며, 노드 3..

동적 계획법 수학적 최적화 방법이자 알고리즘 패러다임입니다. 이 방법은 1950년대 Richard Bellman이 개발하였으며 항공 우주 공학에서 경제학에 이르기까지 수많은 분야에 적용되었습니다.  두 맥락 모두 복잡한 문제를 재귀적으로 더 간단한 하위 문제로 나누어 단순화하는 것을 말합니다. 일부 결정 문제는 이런 식으로 분해할 수 없지만, 여러 시점에 걸친 결정은 종종 재귀적으로 분해됩니다. 마찬가지로 컴퓨터 과학에서 문제를 하위 문제로 나누고 하위 문제에 대한 최적 솔루션을 재귀적으로 찾는 방식으로 문제를 최적으로 해결할 수 있다면 최적 하위 구조가 있다고 합니다. (출처: 위키디피아)  위키디피아에서 동적 프로그래밍, 통칭 동적 계획법(약칭 DP)을 위와 같이 설명하고 있다. 이것을 나만의 설명으..

PS + 알고리즘 공부했던 것 복습도 할 겸 써보는 알고리즘 설명(?)으로 첫 번째는 최단 경로 알고리즘 중 하나인 플로이드 - 워셜 알고리즘이다.  최단 경로 문제는 그래프 상에서 두 정점 (노드) 사이의 최단 경로를 찾는 문제로 여러 알고리즘을 이용하여 해결할 수 있다. 플로이드 - 워셜, 다익스트라, 벨만 - 포드, A * 알고리즘 등으로 최단 경로 문제를 해결할 수 있다. 각 알고리즘의 특징은 다음과 같다.플로이드 - 워셜모든 정점들 사이의 최단 경로를 구할 수 있다. 3중 루프를 사용한다.다익스트라두 노드 사이의 최단 경로를 구할 수 있지만, 두 노드 사이의 가중치에 음수가 존재한다면 사용할 수 없다.벨만 - 포드다익스트라와 같이 두 노드 사이 최단 경로를 구할 수 있으며, 음수 가중치가 존재하..