본문 바로가기

알고리즘

 (13)
[BOJ 1260번/C++] DFS와 BFS 미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요! https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net DFS와 BFS 문제 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는..
[알고리즘] 이진 탐색(Binary Search) 우선 탐색은 여러 정보들 중에서 특정한 값을 찾는 것이다. 사전을 예로 들어, 사전에서 특정한 단어를 찾는 방법은 대표적으로 2가지가 있다. Orange라는 단어를 찾는다고 해보자. 첫 번째 방법은 처음부터 Orange가 나올 때까지 찾아보는 것이다. 이 방법도 생각할 수 있다. 사전의 중간(Kiwi)을 펼쳐놓고 Orange의 위치는 이보다 뒤이므로 나머지 뒷부분에서 중간을 펼치고... 를 반복해 Orange를 찾는 방법이다. 첫번째 방법이 선형 탐색(순차 검색), 두번째 방법이 이진 탐색(이분 탐색)이라고 볼 수 있다. 선형 탐색(Linear Search) 처음부터 찾고자 하는 값이 나올 때까지 탐색하는 기법이다. 배열 [1, 2, 3, 4, 5, 6, 7, 8, 9] 이 있고 8을 찾는다고 하면, 선..
[알고리즘] 그리디 알고리즘 (Greedy Algorithm) 그리디 알고리즘 (Greedy Algorithm) 눈앞의 이익만 좇는 선택을 반복하는 알고리즘이다. 그리디 알고리즘은 당장의 경우에는 최적의 경우일지라도, 결과는 대부분 최적이 아니다. 그렇지만 드물게 최적의 답을 보장해주는 경우가 있다. 해가 만들어 질 때 까지 가장 좋아 보이는 선택을 하는 것을 반복한다. 그리디 알고리즘은 이미 앞에서 사용되었다. 바로, 최소 신장 트리를 구할 때 사용한 프림 알고리즘과 크루스칼 알고리즘이다. 또한, 프림 알고리즘과 크루스칼 알고리즘은 최적해가 보장되는 예들 중 하나이기도 하다. 그러나 이 둘이 특별한 경우이고 대부분의 경우에는 최적의 해를 보장하지 못한다. 아래와 같은 예시를 보자. 1. 이진 트리의 그리디 탐색 이진 트리에서 리프 노드를 만날 때 까지 방문한 노드..
[알고리즘] 다익스트라 알고리즘 (Dijkstra Algorithm) 다익스트라 알고리즘 다음과 같은 도시들과 그 도시들끼리 이어주는 도로망이 있다고 해보자. A 도시에서 F 도시를 방문한다고 하자. 최단 거리를 찾아서 방문한다면 시간이 절약될 것이다. 그러므로, C 도시를 거쳐서 F 도시로 가는 것이 가장 짧은 경로이다. 이때의 거리는 도로의 길이의 합이 가장 짧은 60km가 된다. 가중치 그래프에서도 마찬가지이다. 한 정점 v에서 각 정점들까지의 최단 경로를 구하고자하는 경우가 있다. v에서 각 정점까지의 가중치들을 더하고, 그 가중치가 가장 작으면 최단 거리가 된다. 이렇게 한 시작 정점 v에서 모든 다른 정점들 까지의 최단 경로를 구하는 알고리즘이 다익스트라 알고리즘(Dijkstra Algorithm)이다. 단, 모든 가중치가 음수가 아닐 경우에 사용이 가능하다. ..
[알고리즘] NP-완비(NP-Complete) 세상의 문제 모든 문제들은 "해결할 수 있는 문제인가?" 와 "해결할 수 없는 문제인가?"라는 두 가지의 집합으로 나눌 수 있다. 해결할 수 없는 문제의 대표적인 경우가 앨런 튜닝이 증명한 정지 문제가 되겠다. 해결할 수 없는 문제는 다시 "현실적인 시간 안에 풀 수 있는 문제" 와 "현실적인 시간 안에 풀 수 없는 문제"로 나눌 수 있다. 지금까지 공부한 알고리즘들은 모두 다항식 시간이 걸리는 문제들이었다. 예를 들어, \(O(n^2)\)의 시간이 필요한 선택 정렬, \(O(nlogn)\)의 시간이 필요한 병합 정렬, \(O(n^3)\)의 플로이드-워셜 알고리즘, ... 등이 있었다. \(O(nlogn)\)은 다항식은 아니지만, \(O(n^2)\)에 속하기 때문에 다항식 시간에 속한다고 볼 수 있다. ..
[알고리즘] 동적 계획법(Dynamic Programming) 동적 계획법(Dynamic Programming) 큰 문제의 해답에 그보다 작은 문제의 해답이 포함되어 있으면 최적 부분 구조(Optimal Substructure)라고 한다. 이 최적 부분 구조가 지켜진 상태에서 문제에 대한 해답을 찾는 과정이 바로 동적 계획법이다. 동적 계획법은 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법이다. 예시로 피보나치 수를 보자. 피보나치 수는 다음과 같다. 1, 1, 2, 3, 5, 8, 13, 21, 34, ... 이를 점화식으로 나타내면 다음과 같다. $$\begin{align} f(1) & = f(2) = 1 \\ f(n) & = f(n-1) + f(n-2) \end{align}$$ \(n\)의 피보나치 수는 더 작은 크기인 \(n-1\)의 피보나치 수와..
[알고리즘] 최소 신장 트리(Minimum Spanning Tree) 최소 신장 트리(Minimum Spanning Tree) 신장 트리(Spanning Tree)란 그래프의 모든 정점을 포함하는 트리를 말한다. n개의 정점이 있다면 n-1개의 간선이 존재해야 한다. 이는 트리의 일종이기에 모든 정점들은 최소 하나의 간선에는 연결되어 있어야 하고, 사이클이 없어야 하기 때문이다. DFS와 BFS를 통해 얻어낸 트리도 신장 트리의 한 예가 된다. 최소 신장 트리(Minimum Spanning Tree)는 가중치 그래프에서 가중치의 합이 가장 작은 트리를 뜻한다. 이러한 최소 신장 트리를 찾는 알고리즘의 종류에는 프림 알고리즘(Prim Algorithm), 크루스칼 알고리즘(Kruskal Algorithm)이 있다. 프림 알고리즘(Prim Algorithm) 프림 알고리즘은 ..
[알고리즘] 너비 우선 탐색(BFS) / 깊이 우선 탐색(DFS) 그래프에서 탐색은 하나의 정점에서 시작해 모든 정점들을 한 번씩 방문하는 작업이다. 이에 대한 방법들이 바로 너비 우선 탐색과 깊이 우선 탐색이다. 자료구조에 대한 그래프는 여기로 [자료구조] 그래프 [자료구조] 그래프 그래프 그래프는 요소들이 서로 연결되어 있는 관계를 표현한 자료구조이다. 그래프는 정점(vertex)와 그들을 연결하는 간선(edge)의 집합으로 구성된다. 수학적으로는 다음과 같이 표시한다. (\G = ggjjdiary.tistory.com 너비 우선 탐색(Breadth First Search) 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 방법이다. 너비 우선 탐색은 큐를 이용한다. 정점들이 방문될 때마다 큐에 인접 정점을 삽입하고, 더 이상 ..

티스토리툴바