목록2022/02 (10)
Developer_Neo
Spanning Tree란 (최소 연결 부분 그래프)(신장트리) 그래프 내의 모든 정점을 연결하되 사이클이 없는 그래프를 의미한다. 최소 연결이라는 것은 간선의 수가 가장 적다라는 것이다. n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개이고, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 이것이 바로 Spanning Tree가 된다. 따라서 모든 노드를 포함한 것이 서로 연결되어있어야하고 사이클이 존재하지 않는 것이다. Minimum Spanning Tree(최소 신장 트리) - MST 라고 불리고 가능한 Spanning Tree 중에서, 간선의 가중치 합이 최소인 Spanning Tree를 지칭한다. - 가장 가중치가 낮은 간선부터 선택을 하여 사이클이 없도록 만들면 ..
최단 경로 문제란? 두 노드를 잇는 가장 짧은 경로를 찾거나 가중치가 있는 그래프(Weighted Graph)에서 간선의 가중치의 합이 최소가 되도록 하는 경로를 찾으려는 것이 목적 최단 경로 문제 종류 단일 출발 및 단일 도착 (single-source and single-destination shortest path problem) 최단 경로 문제 그래프 내의 특정 노드 u 에서 출발, 또다른 특정 노드 v 에 도착하는 가장 짧은 경로를 찾는 문제 단일 출발 (single-source shortest path problem) 최단 경로 문제 그래프 내의 특정 노드 u 와 그래프 내 다른 모든 노드 각각의 가장 짧은 경로를 찾는 문제따지고 보면 굉장히 헷깔릴 수 있으므로 명확히 하자면, 예를 들어 A,..
대표적인 그래프 탐색 알고리즘 너비 우선 탐색 (Breadth First Search): 정점들과 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 탐색하는 방식 깊이 우선 탐색 (Depth First Search): 정점의 자식들을 먼저 탐색하는 방식 BFS(Breadth First Search) - 너비 우선 탐색으로써 같은 레벨에 있는 노드들을 왼쪽에서부터 모두 탐색한 후에 다음 레벨로 넘어가는 것이다. - A - B - C - D - G - H - I - E - F - J 순서이다. 코드로 나타내어보자 파이썬에서 제공하는 딕셔너리와 리스트 자료 구조를 활용해서 그래프를 표현할 수 있음 graph = dict() graph['A'] = ['B', 'C'] graph['B'] = ['A', 'D'] g..
그래프 (Graph) 란? 노드(node)와 그 노드를 연결하는 간선(edge)을 하나로 모아 놓은 자료 구조 노드 (Node): 위치를 말함, 정점(Vertex)라고도 함 간선 (Edge): 위치 간의 관계를 표시한 선으로 노드를 연결한 선 그래프 (Graph) 종류 무방향 그래프 (Undirected Graph) 방향이 없는 그래프 간선을 통해, 노드는 양방향으로 갈 수 있음 보통 노드 A, B가 연결되어 있을 경우, (A, B) 또는 (B, A) 로 표기 방향 그래프 (Directed Graph) 간선에 방향이 있는 그래프 보통 노드 A, B가 A -> B 로 가는 간선으로 연결되어 있을 경우, 로 표기 가중치 그래프 (Weighted Graph) 또는 네트워크 (Network) 간선에 비용 또는 ..
이진 탐색 - 컴퓨터과학, 수학등에서 오름차순으로 정렬된 정수의 리스트를 같은 크기의 두 부분 리스트로 나누고 필요한 부분에서만 탐색하도록 제한하여 원하는 원소를 찾는 알고리즘 리스트의 중간 부분에 찾는 원소가 있는지 확인하고, 없으면 위쪽에 있는지 아래쪽에 있는지 판단하여 맨 앞부터 검색하거나 중간부터 검색한다 위의 이미지 출처 Binary Vs Linear Search Through Animated Gifs Average Case Worst Case Binary Search Best Case Binary Search If you're into searching, maybe you're also into sorting! Check out our Sort Detective for exploring com..
https://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 문제 요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다. N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램..
https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 예제 입력 1 복사 2 예제 출력 1 복사 2 예제 입력 2 복사 9 예제 출력 2 복사..
동적 계획법 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법으로 이미 했던 연산이 반복되는 결점을 보완하기 위해서 고안되었다 주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것이다. 각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다. 이러한 방법으로 동적 계획법은 계산 횟수를 줄일 수 있다. 특히 이 방법은 하위 문제의 수가 기하급수적으로 증가할 때 유용하다. 링크 동적 계획법 - 위키백과, 우리 모두의 백과사전 수학과 컴퓨터 과학, 그리고 경제학에서 동적 계획법(動的計劃法, dynamic programming)이란 복잡한 문제를 ..