스패닝 트리?스패닝 트리(ST)는 최소한의 간선으로 모든 정점이 연결되어 있는 구조단, 사이클이 생성되선 안된다.어떤 그래프로 스패닝(신장) 트리를 만들 때 사이클을 만드는 간선은 선택하지 않는다.최소 연결간선의 수가 가장 적다.정점의 수가 n개 일 때, 스패닝 트리의 간선의 수는 언제나 n - 1개이다. 사이클이 발생해서는 안된다. 사이클이 있다는 것은 최소로 연결되지 않았다는 의미1 - 2 - 3으로 연결되어 있을 때 1과 3은 직접적으로 연결되어 있지 않더라도 연결되어 있다고 본다.DFS, BFS를 사용해여 그래프에서 스패닝 트리를 찾을 수 있다.한 그래프에서 스패닝 트리는 여러개 존재할 수 있다.최소 비용 스패닝 트리(MST)가장 적은 비용으로 모든 노드를 연결하고자 할 때 사용가정 적은 비용이라..
Algorithm
Knuth-Morris-Pratt(KMP) 알고리즘패턴을 문장안에서 좌에서 우로 비교하는 것완전 탐색과 다르게 효율적으로 패턴을 찾을 수 있다.패턴과 문장의 불일치가 발생하였을 때 중복 연산을 최대한 피하면서 패턴을 우로 이동시킨다.문장 불일치 발생 시 얼마만큼 건너뛴뒤에 비교 연산을 진행할 것인지 판단해야함예시문자열의 부분 문자열과 패턴을 비교하며 문자열 속 패턴의 존재 여부를 알 수 있음문자열에서 "abcac"라는 패턴 찾기문자열 [... a b c a d ...]패턴 a b c a c패턴을 찾는 중에 위 상황이 발생 시 abca까지는 맞았지만 그 다음 문자열에서 찾고 있는 패턴이 아님을 알아낸 경우문자열 [... a b c a d ...]패턴 a b c a c우로 한칸 옮..
다익스트라 알고리즘?그래프에서 최소 비용을 구하는 경우 사용되는 알고리즘최소 비용 중, 주어진 두 노드(시작 노드, 도착 노드) 사이의 최소 비용인 경로를 찾을 때 유용하게 사용된다.동작 원리시작 노드와 직접적으로 연결된 모든 정점들의 거리를 비교해서 업데이트 시켜주고, 시작 노드를 방문한 노드로 체크한다.방문한 정점들과 연결되어 있는 정점들 중, 비용이 적게드는 정점을 선택하고, 해당 정점을 방문한 정점으로 선택해준다.2번 과정으로 갱신될 수 있는 정점들의 거리를 갱신시켜준다.2번 과정과 3번 과정을 반복한다.시작노드를 0번 노드로 가정dist 배열이 초기 INF로 초기화되어 있다고 생각한다.1번 과정에 의해 0번 노드로 갈 수 있는 1번노드와 4번 노드, 5번 노드의 거리를 갱신0번 노드를 방문한 노..
1. 다익스트라 알고리즘? 다익스트라 알고리즘은 최소거리를 구할 때 사용하는 알고리즘이다. 다익스트라는 시작 노드로부터 모든 노드까지의 최소 거리를 구해준다. 다익스트라를 구현하기 위해서는 비용 배열, 방문 배열, 시작점에서 각노드까지의 비용 배열이 필요하다. weight 배열의 값을 통해 노드간의 연결을 판단한다. 특정 값이 있다면 연결되어 있다는 뜻이다. INF이면 연결되지 않았다는 뜻이다. weight 배열을 통해 단방향 노드나 양방향 노드로 만들 수 있다. 2. 다익스트라 알고리즘 구현 다익스트라 알고리즘의 순서는 다음과 같다. dist 배열의 값을 weight[시작 노드]의 값으로 초기화 시작점을 방문 표시 dist 배열에서 최소 비용 노드를 찾고 방문 처리. 이때 이미 방문한 노드는 무시 최소..
What? Red - Black Tree는 자가 균형 이진 탐색 트리이다. 레드 - 블랙 트리는 아래와 조건을 만족한다. 모든 노드는 빨간색 혹은 검은색이다. 루트 노드는 검은색이다. 모든 리프 노드들은 검은색이다. (NIL, Null leaf, 자료를 갖고 있지 않고 트리의 끝을 나타내는 노드) 빨간색 노드의 자식은 검은색이다. (빨간색 노드가 연속으로 나올 수 없다 - Double Red) 모든 리프 노드에서 Black Depth는 같다. (리프 노드에서 루트 노드까지 가는 경로에서 검은색 노드의 개수가 같다) Red- Black Tree는 STL의 map, set에서 사용한다. 삽입 과정 레드 블랙 트리에서 새로운 노드를 삽입할 때 새로운 노드는 항상 빨간색으로 삽입한다. 이는 4번 조건을 위배되는..
그리디 알고리즘은 개념은 굉장히 단순하다. 말 그대로 탐욕적으로, 눈 앞의 가장 큰 이익을 추구하는 기법이다. 탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 예제) 500원, 100원, 10원 동전이 무수히 많다고 가정할 때 가장 적은 수의 동전을 이용해서 1410원을 만든다고 하자. 이때 사용하는 동전의 개수는 몇개인가? 이 문제를 접했다면 일반적으로 최대 500원의 개수를 사용할 것이다. 그래서 500원짜리 2개로 1000원을 만들고, 100원짜리 4개로 400원을, 10원 동전 1개로 10원을 만들어 1410원을 완성할 것이다. 따라서 이 문제의..
Dynamic Programming이란? 큰 문제를 작은문제로 나누어 푸는 문제를 일컫는 말. Dynamic Programming이란 말 때문에 어떤 부분에서 동적으로 프로그래밍이 이루어지는 찾아볼 필요는 없다. 바로 동적프로그래밍이란 말을 창조한 사람도 이것이 단지 멋있어서 부여한 이름이라고 한다. Dynamic Programming 방법 모든 작은 문제들은 한번만 풀어야 한다. 따라서 정답을 구한 작은 문제를 어딘가에 저장해 두어야 한다. 다시 그보다 큰 문제를 풀어나갈 때 똑같은 작은 문제가 나타나면 앞서 저장한 작은 문제의 결과값을 이용한다. Dynamic Programming의 조건 작은 문제가 반복이 일어나는 경우. 같은 문제는 구할 때마다 정답이 같다. 위 와같은 조건을 만족하는 경우에만 동..
- DFS란, 그래프 전체를 탐색하는 하나의 방법으로써, 하나의 가지(branch)를 모두 탐색한 이후에 다음 branch로 이동하는 방법이다. - 시작 노드에서 깊이가 커지는 방향으로 탐색을 진행하여 더 이상 방문할 인접 노드가 없는 경우 이전 노드로 돌아가서, 다시 깊이우선 탐색을 반복 - 시작점부터 다음 branch로 넘어가기 전에 해당 branch를 완벽하게 탐색하고 넘어가는 방법 https://commons.wikimedia.org/wiki/File:Depth-First-Search.gif# stack 또는 recursive(재귀 함수)로 구현. 1. 탐색 시작 노드를 스택에 삽입하고 방문처리 2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리..
