개발하는 리프터 꽃게맨입니다.

1. 다익스트라 알고리즘의 한계다익스트라 알고리즘은 최단거리를 찾는 일반적인 알고리즘입니다.그러나 그래프 간선의 가중치의 값이 음수일 경우 항상 최적해를 찾는다는 보장은 없습니다. 물론, 다익스트라 알고리즘이 음수 가중치가 존재한다고 해서 항상 최단거리를 찾지 못하는 것은 아닙니다.   먼저, 우선순위 큐를 사용하지 않는 다익스트라 알고리즘 위 그래프에서 최단거리를 찾아낼 수 없습니다.모든 간선의 가중치가 양수일 경우 방문하지 않은 vertex 중 distance 배열의 값이 최소인 노드는 자명하게 최단거리이기 때문이죠. 그러나 음의 가중치 값이 그래프에 존재할 경우미래에 더 저렴한 경로를 찾을 가능성이 존재합니다.  위와 같은 그래프에서는 우선순위 큐를 사용한 다익스트라 알고리즘으로 최단거리를 찾아낼 ..

이진 탐색 알고리즘은 '정렬된 상태의 배열' 에서 원하는 값을 O(log n) 만에 탐색할 수 있는 알고리즘 입니다. 그 방법은 '업앤다운 숫자맞추기'를 하는 방법과 유사합니다. 1~50 중에서 상대방이 생각한 숫자를 가장 빨리 맞추는 방법은 절반인 25를 말해서 업, 다운을 듣고 업! 이라면 37 다운! 이라면 12 을 말하면서 점차 줄여나가는 방식입니다. 계속 절반 절반 반띵하면서 원하는 수를 찾아가는 것이죠. 샘플코드 입니다. 찾고자 하는 값이 mid 값보다 크냐 작냐에 따라서 찾고자하는 범위를 좁혀나가는 것입니다. 재귀적으로 코드를 구성할 수 있습니다. 이진탐색의 경우 log2 N 의 시간복잡도를 가지며, 임의 접근이 불가한 연결리스트의 경우에는 설사 정렬이 되어 있더라도 이진 탐색을 사용할 수 ..

https://powerclabman.tistory.com/90 [C++/이론] 최소 스패닝 트리 : 프림 알고리듬 (Prim Algorithm) 스패닝 트리 임의의 그래프가 있다고 생각해봅시다. 스패닝 트리란 부분 그래프 중 하나로 다음과 같은 조건을 만족해야 합니다. 1) 그래프 내의 모든 정점을 포함하는 부분 그래프 2) 사이클이 powerclabman.tistory.com 개요 크루스칼 알고리즘은 최소 스패닝 트리를 구하기 위한 또 다른 알고리즘입니다. 앞전에 소개한 프림 알고리즘과 차이점은, 프림 알고리즘의 경우 특정 노드에서 출발해 노드들을 탐색하면서 최소 스패닝 트리를 완성시켜나가는 알고리즘이었다면 크루스칼 알고리즘은 모든 경로를 두고, 최소 경로만 쏙쏙 선택해서 트리를 만들어낸다고 보면 되..

스패닝 트리 임의의 그래프가 있다고 생각해봅시다. 스패닝 트리란 부분 그래프 중 하나로 다음과 같은 조건을 만족해야 합니다. 1) 그래프 내의 모든 정점을 포함하는 부분 그래프 2) 사이클이 없는 그래프 이런 그래프를 신장 트리 (혹은 스패닝 트리)라고 합니다. 스패닝 트리를 찾는 것은 매우 단순합니다. 단순 BFS, DFS를 하면 스패닝 트리를 찾을 수 있죠. 그런데 가중치 그래프의 경우를 생각해봅시다. 모든 노드를 다 방문하는데 비용이 다 다르다면, 아무래도 최소 비용으로 방문하는 것이 가장 좋겠죠? 그래서 중요하게 다뤄지는 알고리즘이 최소 신장 트리 (최소 스패닝 트리) 이며, 이는 모든 노드를 방문하는 최소 비용의 신장트리를 찾는 것을 목적으로 합니다. 더보기 최소 비용 경로 알고리즘과 무엇이 다..

https://www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net 1. 문제 2. 아이디어 기본적으로 그리디 알고리즘이다. 가장 작은 카드를 더해서 카드 뭉치를 업데이트해주면 된다. 그러면 가장 작은 요소로 배열을 정렬해서 하는 방법이 있는데, 이는 조금 문제가 있다. 왜냐면, 업데이트 + 정렬 + 업데이트 + 정렬은 생각보다 비용이 크기 때문이다. 정렬의 경우 아무리 빨라봐야 평균 n log n 시간 복잡도가 소모된다. 시..

참고: https://powerclabman.tistory.com/26 [C++] 경로 역추적: BFS을 이용한 '미로찾기 알고리즘' 개요 위 그림과 같은 임의의 미로가 있고 플레이어와 도착지의 위치가 정해져 있을 때, 플레이어는 도착지를 어떻게 찾을 수 있을까요? 그리고 어떻게 해야 최단 경로로 도착지에 도달할 수 있 powerclabman.tistory.com 참고: https://powerclabman.tistory.com/27 [C++/이론] 다익스트라 알고리즘 (Dijkstra Algorithm) 참고: https://powerclabman.tistory.com/24 참고: https://powerclabman.tistory.com/25 가중치 그래프 이전 포스팅에서 사용했던 그래프는 모두 가중..

참고: https://powerclabman.tistory.com/24 참고: https://powerclabman.tistory.com/25가중치 그래프이전 포스팅에서 사용했던 그래프는 모두 가중치가 없는 그래프였습니다. 즉, 노드와 노드를 이동하는데 비용이 동일하다는 것이죠. 근데, 실제로 상황에서 A->B로 가는 것과 A->C로 가는 것의 비용이 다를 수도 있겠죠? 서울 -> 강원도 서울 -> 부산 두 조건 다 도시와 도시 사이를 이동하는 것이지만, 소모하는 기름, 거리, 톨게이트 비용 등.. 많은 것이 다를 것입니다. 이런 비용을 '가중치' 라고 하고, 가중치를 표현한 그래프를 '가중치 그래프'라고 부릅니다. int adjacent[5][5] = { 0,1,1,0,0, 0,0,1,0,1, 0,0,..

개요 위 그림과 같은 임의의 미로가 있고 플레이어와 도착지의 위치가 정해져 있을 때, 플레이어는 도착지를 어떻게 찾을 수 있을까요? 그리고 어떻게 해야 최단 경로로 도착지에 도달할 수 있을까요? 그에 대한 알고리즘을 소개해보겠습니다. 미로 찾기 베이스 미로 찾기 알고리즘을 개발하기 위한 베이스입니다. 이 파트는 넘어가셔도 상관없다만, 몇 가지만 확인해 주시면 해당 포스트를 이해하는데 도움이 될 것입니다. (포스팅을 위해 하나의 파일로 만들었습니다.) 1. 2차원 좌표값은 Pos 클래스를 사용합니다. Pos(y, x)로 나타내며 y는 y축 값, x는 x축 값을 나타냅니다. 연산자 오버로딩을 해주었기에, 자유롭게 연산이 가능합니다. 2. 미로는 NxM 사이즈의 bool 형 2차원 배열입니다. 0(false)..

(참고: 기본적인 구현인 '인접 행렬'을 사용해서 구현했습니다.) 서론 탐색은 우리가 관리하는 자료구조의 전체를 순회하거나 원하는 자료를 찾고자 하는 것을 뜻합니다. 자료구조를 다루는 시점에서 '탐색'은 필수적이죠. 그런데, 그래프 구조는 복잡하기에 단순하게 순회하는 것조차 힘듭니다. 일반적으로 탐색의 방법은 '깊이 우선 탐색 DFS' '너비 우선 탐색 BFS' 2가지가 존재합니다. 깊이 우선 탐색 1. 개요 깊이 우선 탐색은 말 그대로 출발점에서 가장 멀리 있는 노드(가장 깊이 있는 노드)를 도달하고자 하는 탐색방법입니다. A에서 가장 멀리 있는 노드는 F죠 그래서 A -> D -> F를 먼저 탐색하고 나머지 노드를 탐색합니다. 이런 식으로 탐색하는 이유는 '스택'의 특성 때문에 그렇습니다. 알고리즘의..

개요 그래프(Graph)는 '정점(vertex, node)'과 '간선(edge, adjacent, link)'의 집합으로 이루어진 자료구조입니다. 어떻게 보면, 하나의 노드를 가리키는 '연결리스트' 다수의 노드를 한 방향으로 가리키는 '트리'의 확장된 버전으로 이해할 수 있습니다. (문서를 찾다보면 정점 = Node = Vertex 등 용어가 혼용되고, 간선 = edge = adjacent = link 용어가 혼용됩니다. 다 알아두시길 바랍니다.) 이런 식으로 노드와 노드는 간선으로 연결됩니다. 트리, 연결리스트에 비해 현실 상황을 잘 재현하는 자료구조라고 여겨집니다. 어떻게 보면 지하철 노선도와 같은 형태를 띠고 있으며 이렇게 정보를 가지고 있는 '노드'를 간선으로 직관적으로 연결하고 '복잡한 관계'에..