본문 바로가기

분류 전체보기

 (229)
크루스칼 알고리즘 (Kruskal's Algorithm) 크루스칼 알고리즘을 공부하기 전에, 스패닝 트리에 대해서 먼저 알아야 한다.span 은 '완전히 덮다' 라는 느낌의 뜻을 가지고 있는 단어이고, 트리는 사이클이 없는 그래프이다.그래서 스패닝 트리는 그래프의 모든 노드를 포함하는 트리이다. 위의 경우에도 스패닝 트리이고, 밑의 경우에도 스패닝 트리이다.하나의 그래프에서 스패닝트리는 여러개 존재할 수 있다.스패닝 트리의 가중치를 합하면 weight를 알 수 있는데, 그래프에서 weight의 값이 최소인 스패닝 트리를최소 스패닝 트리 (Minimum Spanning Tree) 이라고 한다. 위의 그래프에서 표시된 트리가 최소 스패닝 트리이다.크루스칼 알고리즘을 알기 위해서 또 알아야할 개념중에 하나가 Cut Property 라는 것이다.T1과 T2는 서로 다..
다익스트라 알고리즘 (Dijkstra's Algorithm) 최단경로를 구하는 알고리즘인 다익스트라 알고리즘을 공부하고자 한다.다익스트라 알고리즘은 한 점에서 모든 점까지 최단거리를 구하는 알고리즘인데, 가중치가 양수일 때만 사용하는 알고리즘이다.예시에서는 1에서 7까지 도달하는 최단경로를 구한다고 해보자. 먼저 시작정점 1까지는 최단경로 0으로 왔기 때문에 최단경로 0으로 도착했다고 표시한다.그리고 다음 경로로 2와 6으로 갈 수 있는데, 1에서 6으로 가는 방법은1 --> 6 과 1 --> 2 --> 6 두가지가 있다. 1에서 2로 가는 방법은 1 --> 6 --> 2 와 1 --> 2 가 있다. 1 --> 2 --> 6 과 1 --> 6 --> 2 를 구하려면2 --> 6 과 6 --> 2 를 알아야 하는데, 아직 1 --> 6 로 갈지 1 --> 2 로 갈..
최단경로 알고리즘 노드와 노드를 이어주는 간선의 어떤 값을 부여한 것을 간선의 가중치(weight)라고 한다.최단경로 문제는 어떤 노드부터 노드까지 가는 경로의 가중치의 최솟값을 구하는 문제이다. 위의 경로대로 A부터 B까지 가면 1+1+1+2+9 = 14 가 경로의 가중치를 모두 합한 값이다.하지만 이것은 최단경로가 아니므로 그래프에서 최단경로를 구해보면 12로 다음와 같다. 기초 최단경로 알고리즘은 세가지가 있는데, 특징은 위와 같다.플로이드 알고리즘은 모든 정점에서 모든 정점까지 최단거리를 구하지만, 그만큼 시간이 많이걸린다.다익스트라와 벨만포드 알고리즘의 차이점은 가중치의 음수값이 있느냐 없느냐에 따라 나뉜다. 최단경로 문제를 풀 때 중요한 특징은 2가지가 있는데첫번 째는 X까지 최단거리로 가기 위해서는 그 직전의..
넓이우선탐색 (Breadth First Search) BFS는 DFS와 다르게 Queue를 이용하여 그래프를 순회하는 방법이다. 제일 먼저시작하는 노드를 큐에 push하고 색칠한 후에 시작한다. 그 다음에① pop 하는 노드에서 인접한 노드들을 큐에 넣고 색칠한다.② 더이상 넣을 노드들이 없다면 큐에서 pop을 한다.이런식으로 동작한다. 예를 들어 설명해보자. 위에 그림에서 1에서부터 시작하므로1을 큐에 넣고 방문했다고 색칠한다. 1을 pop하고 나면, 이제 1에 인접한 노드들을 확인 한다. 즉 2와 4를 push 하고 방문했다고 색칠한다.현재 큐 상태는 1이 pop되어 있는 상태이고, 큐에 2와 4가 들어가있다.이제 1에 인접한 모든 노드 2와 4를 큐에 넣었으므로 더이상 넣을 노드가 없다.그러므로 현재 큐에서 pop을 해보면 front에 있는 2가 po..
깊이우선탐색 (Depth First Search) DFS는 자기가 방문했던 자취를 기억하는 스택의 특징을 이용하여 인적한 노드부터 차례대로 그래프를 순회하는 방법이다. 주어진 그래프에서 1부터 DFS를 한다고 예시를 들어보자. 여기에서는 더 작은 숫자가 먼저 탐색한다고 가정하면,2와 6중에서 2를 먼저 방문하게 된다. 2에서 다시 DFS를 시행하는데, 방문할 노드가 3과 6이 있으므로더작은 3을 방문하게 되고, 3에서 DFS를 다시 시행하여 4를 방문하고, 4에서 다시 DFS를 해서 5를 방문한다.이제 5에서 더 방문할 곳이 없기 때문에 그 동안 왔던 순서 대로5 --> 4 --> 3--> 2 로 돌아간다. 2로 다시 돌아와서 DFS를 하면 3과 6을 탐색하려고 하는데,3은 이미 방문한 노드이기 때문에 6을 방문한다. 6까지 방문하고 6에서 DFS를 해..
그래프 (Graph) 그래프는 트리와 비슷하게 생긴 자료구조로 정점과 간선으로 이루어져있다.먼저 용어정리를 하자면 정점(Node, Vertex)은 각각의 자료를 말한다.정점과 정점을 잇는 선을 간선(Edge)라고 한다.차수(Degree)는 한 정점에 몇 개의 간선이 연결되어 있는가라는 것인데, 위의 사진에서 보면정점 2의 차수는 4라는 것을 알 수 있다. 자기 자신으로 다시 돌아올 수 있는 경로를 사이클(Cycle)이라고 한다. 그래프는 사람과 사람을 연결해주는 네트워크에서 볼 수 있는 구조이기도 하고,지하철 노선도 역시 그래프로 해석할 수 있기 때문에, 현실의 많은 것들과연관이 되어있기 때문에 중요한 자료구조라고 할 수 있다.그러므로 수학적 정리가 매우 방대하고, 스택과 큐 같은 자료구조는 구현이 간단하지만그래프는 그만큼 ..
연속부분최대합L 문제N개의 정수가 주어질 때, 연속된 부분을 선택하여 합을 최대화 하는 프로그램을 작성하시오. 예를 들어, 아래와 같이 8개의 숫자가 있을 경우, 색칠된 부분을 선택했을 때 그 합이 가장 최대가 된다. 입력첫 번째 줄에 n이 주어진다. ( 1 ≤ n ≤ 1,000,000 ) 두 번째 줄에 n개의 정수가 주어진다. 출력연속된 부분을 선택하였을 때의 최댓값을 출력한다. 예제 입력8 2 3 -5 8 -3 4 2 -9 예제 출력11 예제 입력5 -1 -2 3 -2 4 예제 출력5 연속부분최대합을 동적계획법으로 푸는 풀이다. Table(i) 를 i번째 수를 오른쪽 끝으로 하는 연속부분 중 최대합이라고 정의한다. 그러면 Table에 대한 점화식은 Table(i) = max ( Table(i-1) + Data(i) ..
[DP-예제 2] 숫자 만들기 입력 N 과 M 이 주어지면, 1~M 까지 숫자를 더하여 N을 만드는 경우의 수를 구해보자.5와 3 같은 경우는 1~3의 숫자를 임의로 골라 더해서 5를 만드는 경우의 수를 구하는 것이다. 숫자 1~3을 가지고 더해서 5를 만드는 경우의 수를 따지면 위와 같이 13가지가 나온다.이제 문제를 해결하기 위해서 부분 문제를 정의해야 한다.동적 계획법으로 기준을 세우기 위에서 마지막 숫자를 기준으로 3가지로 나눌 수 있다.① 마지막에 숫자 1을 더하는 경우② 마지막에 숫자 2를 더하는 경우③ 마지막에 숫자 3을 더하는 경우 세분류로 나눈 것들이 뜻하는 것은 이렇게 해석 할 수 있다.① 마지막에 숫자 1을 더하는 경우 -> 5에서 1을 뺀 나머지 부분에서 4를 만들어야 한다.② 마지막에 숫자 2를 더하는 경우 -..

티스토리툴바