알고리즘/Do it! 알고리즘 코딩 테스트 (25) 썸네일형 리스트형 플로이드-워셜 플로이드-워셜 (floyd-warshall)그래프에서 최단 거리를 구하는 알고리즘. 주요 특징은 다음과 같다. 기능특징시간 복잡도 (노드 수: V)모든 노드 간에 최단 경로 탐색- 음수 가중치 에지가 있어도 수행할 수 있음.- 동적 계획법의 원리를 이용해 알고리즘에 접근O(V^3) 플로이드-워셜의 핵심 이론플로이드-워셜 알고리즘을 도출하는 가장 핵심적인 원리는 A 노드에서 B 노드까지 최단 경로를 구했다고 가정했을 때 최단 경로 위에 K 노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로라는 것이다. 색칠된 에지 경로가 1 -> 5 최단 경로라면 1 -> 4 최단 경로와 4 -> 5 최단 경로 역시 색칠된 에지로 이뤄질 수밖에 없다. 즉, 전체 경로의 최단 경로는 부분 경로의 최단 경로의 조합으.. 벨만-포드 벨만-포드(bellman-ford-moore)그래프에서 최단 거리를 구하는 알고리즘은 다익스트라, 벨만-포드, 플로이드 워셜이 있다. 특정 시작점에서 다른 모든 노드로의 최단 거리를 구하는 알고리즘은 다익스트라, 벨만-포드이고, 그 중 음수 간선을 다루는 유일한 알고리즘이 바로 벨만-포드이다. 그래서 코딩 테스트에서 벨만-포드가 나온다면 최단 거리보단 음수 사이클이 있는지 판단하는 문제가 더 많이 나오게 된다. 벨만-포드의 주요 특징은 다음과 같다. 기능특징시간 복잡도(노드 수:V, 에지 수:E)특정 출발 노드에서 다른 모든 노드까지의 최단 경로 탐색- 음수 가중치 에지가 있어도 수행할 수 있음- 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있음O(VE) 벨만-포드의 핵심 이론1. 에지 리스트.. 다익스트라 다익스트라 (Dijkstra)다익스트라 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘으로, 주요 특징은 다음과 같다. 기능특징시간 복잡도 (노드 수 : V, 에지 수: E)출발 노드와 모든 노드 간의 최단 거리 탐색에지는 모든 양수O(ElogV) 특정 노드에서 다른 노드들의 최단 거리를 구하는 문제가 주어졌을 때 다익스트라 알고리즘을 사용하면 문제를 해결할 수 있다. 다익스트라 알고리즘의 핵심 이론1. 인접 리스트로 그래프 구현하기 인접 행렬로 구현해도 좋지만 시간 복잡도 측면, N의 크기가 클 것을 대비해 인접 리스트를 선택하여 구현하는 것이 좋다. 인접 리스트에 연결한 배열의 자료형은 (노드, 가중치)와 같은 형태로 선언하여 연결했다. 2. 최단 거리 배열 초기화하기최단 거리 배열을 만들고,.. 위상 정렬 위상 정렬 (topology sort)위상 정렬은 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다. 기능특징시간 복잡도(노드 수 :V, 에지 수 :E)노드 간의 순서를 결정사이클이 없어야 함O(V+E) (참고 : https://m.blog.naver.com/ndb796/221236874984) 위상 정렬에서는 항상 유일한 값으로 정렬되지 않는다. 또한 사이클이 존재하면 노드 간의 순서를 명확하게 정의할 수 없으므로 위상 정렬을 적용할 수 없다. 위상 정렬의 핵심 이론위상 정렬은 다음과 같은 단계로 설명할 수 있다. 다음 예를 보자. 위상 정렬의 원리 이해하기1. 진입 차수(in-degree)는 자기 자신을 가리키는 에지의 개수이다. 다음을 보면 ArrayList로 그래프를 표현했다. 그래프.. 유니온 파인드 유니온 파인드 (union-find)유니온 파인드는 그래프 알고리즘으로 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘이다.일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성되어 있는 알고리즘이다. https://ip99202.github.io/posts/%EC%9C%A0%EB%8B%88%EC%98%A8-%ED%8C%8C%EC%9D%B8%EB%93%9C(Union-Find)/ 유니온 파인드(Union-Find)유니온 파인드란? 유니온 파인드는 그래프 알고리즘으로 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘이다. 서로소 집합, 상호 베타적 집합(Disjoint-Set)으로도 불린다.. 그래프의 표현 그래프그래프는 노드와 에지로 구성된 집합이다. 노드는 데이터를 표현하는 단위이고 에지는 노드를 연결한다. 여기서는 그래프를 구현하는 3가지 방법을 알아본다. 에지 리스트 (edge list)에지 리스트는 에지를 중심으로 그래프를 표현한다. 에지 리스트는 배열에 출발 노드, 도착 노드를 저장하여 에지를 표현한다. 또는 출발 노드, 도착 노드, 가중치를 저장하여 가중치가 있는 에지를 표현한다. 에지 리스트로 가중치 없는 그래프 표현하기가중치가 없는 그래프는 출발 노드와 도착 노드만 표현하므로 배열의 행은 2개면 충분하다. 노드는 여러 자료형을 사용할 수 있으며 다음의 경우 노드는 Integer 형이다.1에서 2로 뻗어나가는 에지는 [1, 2]로 표현한다. 4에서 5로 뻗어나가는 에지는 [4, 5]로 표현한.. 정수론 - 확장 유클리드 호제법 유클리드 호제법의 목적이 두 수의 최대 공약수를 구하는 것이라면 확장 유클리드 호제법의 목적은 방정식의 해를 구하는 것이다. 확장 유클리드 호제법을 제대로 이해하려면 수학 증명 과정까지 공부해야 하지만 여기서는 확장 유클리드 호제법 관련 문제를 풀기 위한 알고리즘만 설명한다. 확장 유클리드 호제법의 핵심 이론확장 유클리드 호제법에서 해를 구하고자 하는 방정식은 다음과 같다. 해를 구하고자 하는 방정식ax + by = c (a, b, c, x, y는 정수) 이때 위 방정식은 c % gcd(a, b) = 0인 경우에만 정수해를 가진다. 다시 말해 c가 a와 b의 최대 공약수의 배수인 경우에만 정수해를 가진다. 이는 ax + by = c가 정수해를 갖게 하는 c의 최솟값이 gcd(a, b)라는 것을 의미한다.. 정수론 - 유클리드 호제법 유클리드 호제법 (euclidean-algorithm)유클리드 호제법은 두 수의 최대 공약수를 구하는 알고리즘이다. 일반적으로 최대 공약수를 구하는 방법은 소인수분해를 이용한 공통된 소수들의 곱으로 표현할 수 있지만 유클리드 호제법은 좀 더 간단한 방법을 제시한다. 유클리드 호제법의 핵심 이론유클리드 호제법을 수행하려면 먼저 MOD 연산을 이해하고 있어야 한다. MOD 연산이 최대 공약수를 구하는 데 사용하는 핵심 연산이기 때문이다. 연산기능예제MOD두 값을 나눈 나머지를 구하는 연산10 MOD 4 = 2 // 10 % 4 = 2 MOD 연산을 이해하면 다음과 같은 3단계로 유클리드 호제법을 구현할 수 있다. 큰 수를 작은 수로 나누는 MOD 연산을 수행한다.앞 단계에서의 작은 수와 MOD 연산 결괏.. 이전 1 2 3 4 다음
