다익스트라(Dijkstra) 알고리즘 그래프의 최단 경로를 구하는 알고리즘으로 하나의 정점에서 출발하여 최단 거리를 구하는 알고리즘이다. 탐욕법(Greedy)과 동적 계획법을 사용하는 알고리즘으로, 음의 가중치(음의 값)가 없어야한다. 음의 가중치가 존재하게 되면, 최소 비용의 음의 무한대값이 생성될 수 있으며 그리디 알고리즘을 적용할 수 없다. 인접 행렬로 표현된 그래프의 경우 O(n^2)의 복잡도를 가지며, 우선순위 큐를 사용하여 시간복잡도를 O(m logn)까지 낮출 수 있다. 매커니즘 (1) 방문하지 않은 노드 중 가장 비용이 적은 노드를 선택한다 (그리디) (2) 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신한다 (DP) 예시 https://mag1c.tistory.com/451 [백준 19..

서론 Upper Bound, Lower Bound는 이진탐색을 활용한 알고리즘이다. [알고리즘] 이진탐색(이분탐색) - Binary Search Binary Search 정렬된 데이터 집합을 이분화 하면서 탐색하는 방법 정렬되어 있어야 한다 보통 세 개의 변수를 지정해 두고 (ex : left, mid, right) 찾고자 하는 값, 즉 mid의 값이 찾아낸 값보다 크면 mid는 mag1c.tistory.com 백준에서 이진탐색을 활용한 문제를 풀다가, 깔끔하게 풀리지 않아서 풀고 난 뒤 다른 분들의 코드나 설명을 참조했더니, 내가 사용했던 조건들이 Upper Bound라는 것을 알게되었고, 정리하고자 포스팅을 진행한다. [백준 1654번 / JAVA] 랜선 자르기 문제 링크 https://www.acm..

서론 올해 초부터 어느정도 적당한 난이도 이상의 코딩테스트들에 응시하고 있는데, 항상 5번문제는 MST관련 문제가 나왔다. 조금만 변형되어도 풀기가 애매해질 정도로 얕은 정도로만 학습을 한 상태였기 때문에, 복기를 위해 관련된 것들을 학습하려고 한다. Union Find Disjoint Set(서로소 집합)을 관리하는 데 사용되는 알고리즘으로, 각 집합의 대표 요소를 통해 집합을 식별한다. 대표 요소를 해당 집합의 부모라고도 부르며, 루트로 표현된다. 일반적으로 작은 번호를 부모로 정하는데, 이는 트리의 높이를 최소화하여 연산의 효율성을 높일 수 있다. 여러 노드가 존재할 때, union과 find 연산을 수행한다. Union : 노드를 연결 Find : 특정 노드의 루트 노드를 찾음 예제 원소 A B ..

Dynamic Programing 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. - 위키백과 Dynamic Programing은 1. 하위 문제로 쪼개지며, 하위 문제의 정답으로 해당 문제의 정답을 구할 수 있을 때(Optimal Substructure) 2. 하위 문제가 겹칠 때 (Overlapping Subproblem) 사용할 수 있다. Top-Bottom방식과 Bottom-Up방식이 있는데 이름에서 알 수 있다시피 위에서아래로, 아래에서 위로 가는 방식인 것 같다. Top-Bottom은 재귀를 통해 메인 문제에서 작은 문제들로 쪼개어가는 과정이고 Bo..

투포인터 1차원 배열이 있고, 이 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터(idx)를 조작해가며 원하는 것을 얻는 형태이다. 부분 배열 중 그 원소의 합이 조건과 일치하는 경우의 수를 구하는 것이다. 모든 경우의 수를 다 테스트한다면 구간의 합을 구간 배열로 O(1)만에 구한다고 해도 경우의 수는 O(N^2)이기 때문에 시간 복잡도를 고려하는 문제라면 풀 수 없다. 배열의 최대 범위가 너무 크기 때문이다. 예시 / 그림 참조 : https://butter-shower.tistory.com/226 X = 5를 구하는 문제에서

깊이 우선 탐색 ( Depth-First Search ) 루트 노드에서 시작해 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 특징 1. 모든 노드를 방문하고자 하는 경우에 사용한다. 2. 단순 검색 속도는 너비 우선 탐색(BFS)에 비해 느리다. 3. 검색이 아닌 순회를 할 경우 많이 사용한다. 공통 상위를 가지는 아래 리프 노드들을 한방에 잘라내는게 가능하기 때문에 백트래킹에 사용된다. 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다. 장점 1. 현 경로상의 노드들만 기억하면 되기 때문에 저장 공간의 수요가 비교적 적다. 2. 목표 노드가 깊은 ..

너비 우선 탐색 ( Breadth-first search ) 트리나 그래프를 방문 또는 탐색하는 방법으로 루트 노드에서 시작해서 인접 노드를 먼저 탐색하는 방법. 탐색 방법 1. 루트노드에서 시작한다. 2. 자식노드들을 저장한다. 3. 저장되어있는 노드를 방문하며 저장되어있는 노드들의 자식들을 저장하며 4. 위의 과정을 모든 노드를 방문할 때 까지 반복하며 완료 시 탐색을 종료한다. 특징 1. 어떤 노드를 방문했는지 반드시 검사 해야 한다. 2. Queue를 사용하는 경우가 일반적이며 재귀적으로 동작하지 않는다. 3. Prim, Dijkstra알고리즘과 유사하다. 장점 1. 노드의 수가 적고 깊이가 얕은 경우 빠르게 동작할 수 있다. 2. 단순 검색 속도가 깊이 우선 탐색(DFS)보다 빠르다. 3. 너비..

[ 플로이드-워셜(Floyd-Warshall) ] 그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘이다 다익스트라는 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘(S.S.S.P - Single Source Shortest Path) 이었다면, 플로이드-워셜 알고리즘은 한 번 실행하여 모든 노드 간 최단 경로를 구할 수 있습니다. 플로이드-워셜 알고리즘은 다익스트라 알고리즘과는 다르게 음의 간선도 사용할 수 있다. 다익스트라(Dijkstra) 알고리즘 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘이다 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다 음의 간선을 포함할 수 없지만 현실 세계에서는 음의 간선이 존재하지 않기 때문에 현실..