최소 신장 트리 •트리(Tree)는 싸이클이 없는 연결 그래프, n개의 정점(vertex)을 가지는 트리는 n-1개의 간선(edge)을 가짐 •신장 트리(Spanning Tree)는 그래프 G(V,E)에서 정점 집합 V를 그대로 두고 간선을 |V|-1개만 남겨 트리가 되도록 만든 것 (|V|=n) •너비 우선 트리와 깊이 우선 트리도 신장 트리 •간선 가중치의 합이 가장 작은 트리를 최소 신장 트리 (Minimum Spanning Tree, MST)라 함 -> 최소 신장 트리를 대표하는 알고리즘으로는 프림 알고리즘과 크루스칼 알고리즘이 존재한다. 프림 알고리즘(Prim’s Algorithm) 프림 알고리즘은 로버트 프림(Robert C. Prim)이 만든 최소 신장 트리 알고리즘이다. 프림 알고리즘은 최..
비트마스크란? - 비트마스크(BitMask)는 이진수를 사용하는 컴퓨터의 연산 방식을 이용하여, 정수의 이진수 표현을 자료 구조로 쓰는 기법을 말한다. - 이진수는 0 또는 1을 이용하므로 하나의 비트(bit)가 표현할 수 있는 경우는 두 가지이다. - 보통 어떤 비트가 1이면 "켜져 있다"라고 말하며, 0이면 "꺼져 있다"라고 말한다. - 8 bits = 1byte 비트마스크를 사용하면 다음과 같은 이점을 얻을 수 있다. 수행시간이 빠르다. 코드가 짧다 메모리 사용량이 더 적다. 비트 연산자 AND연산 (&) 대응하는 두 비트가 모두 1일 때, 1을 반환 1010 & 1111 = 1010 OR연산(|) 대응하는 두비트가 모두 1 또는 둘 중 하나라도 1이면, 1을 반환 1010 | 1111 = 1111..
동적 계획법(Dynamic Proframming)이란? 부분 문제를 해결한 결과를 이용하여 전체 문제를 해결하는 것 작은 나를 해결함으로써 더 큰 나를 해결함 동적 계획법의 문제 풀이 순서 1. 부분 문제를 정의한다. - 무슨 값을 구할지를 정의한다. 2. 점화식을 구한다. - 그 값을 어떻게 구할지에 대한 식을 세운다. ( 부분은 풀려있다고 가정) 3. 문제를 해결한다. - 값을 직접 구하는 코드를 작성한다. 동적 계획법을 활용한 대표적인 예시 피보나치 수 구하기가 있다. 점화식을 활용하기 위해 index 0,1에 해당하는 값을 미리 채워주어야 한다. 반복문을 통해 이전의 값을 활용하여 채워주면서 나아가면 된다. 동적 계획법 활용 문제 개인적으로 동적 계획법 자체는 쉽지만 부분 문제를 정의하는 것이 어..
그래프를 활용하여 최단 경로를 구할 수는 없을까? 최단경로 알고리즘은 크게 3가지가 존재한다. 이번 시간에는 다익스트라만 다루도록 하겠다. 다익스트라란? 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘이다. 정점 사이에는 가중치가 존재한다. 최단경로의 특징 정점 x까지 최단거리로 가기 위해서는 그 직전까지도 최단거리로 가야 한다. 위의 그림을 보면 1 - 6 - 2 - 3 - 8 - 7 순으로 이동한다. 최단경로의 특징을 이용하면 1~8까지 이동할 때에도 최단 경로로 이동한다. 그래서 최단경로 트리를 어떻게 만들 것인가? T(i) = i까지 도달하는 최단거리 -> 파란색 숫자 순서를 그림을 이용하여 천천히 설명하겠다. 보라 색원은 이미 탐색을 완료했다는 의미이다...
그래프 순회 저번에 배운 깊이 우선 탐색(Depth First Search) - 스택을 이용하여 그래프를 순회하는 방법 너비 우선 탐색(Breadth First Search) - 큐를 이용하여 그래프를 순회하는 방법 너비 우선 탐색(BFS) 인접한 노드들을 우선 모두 색칠해 두고 뻗어나간다. 위의 그림에서 너비 우선 탐색을 사용한다고 하자. 우선 1을 큐에 넣고, (1)을 제거한다. -> 현재 노드 위치 1의 인접 노드인 2와 4를 큐에 넣는다. 이후 1의 이웃한 노드들이 모두 색칠되었으므로, 큐의 제일 앞 노드를 제거한다.(2) 2가 제거되었으므로 현재 노드 위치는 2이다. 2의 인접 노드인 3을 큐에 넣는다. 4는 이미 추가되어있으므로 추가하지 않음. 2의 인접 노드가 모두 색칠되었으므로, 큐의 제일..
그래프 순회 - 그래프라는 자료구조에 어떠한 값이 저장되어 있는가? 깊이 우선 탐색(Depth First Search) 스택을 이용하여 그래프를 순회하는 방법 스택 = 선행 관계 - 나를 먼저 방문하고 그다음으로 인접한 노드를 차례로 방문(단, 방문했던 노드는 방문하지 않는다.) 깊이 우선 탐색의 예시 위 그래프는 1 - 2 - 3 - 4 - 5 - 6 순으로 방문하게 된다. 중요한 점은 더 이상 갈 곳이 없다면, 왔던 곳으로 돌아간다.(재귀) 좀 더 복잡해 보이는 그래프를 보자. 위에 보이는 순서대로 방문하게 되고, 화살표의 모양대로 다시 돌아오게 된다. 가장 깊은 4까지 간 뒤 더 이상 갈 곳이 없기 때문에 돌아오면서 방문하지 못한 곳을 방문하게 된다. DFS 구현 DFS를 구현하고, 코드를 보며 자..
그래프란 다음과 같은 모습을 가지고 있다. 즉 그래프는 각각의 정점이 간선으로 연결되어있는 모습이다. 그래프는 왜 중요한가? 현실 세계의 많은 것들을 그래프로 나타낼 수 있다. - 즉 그래프와 관련된 문제가 매우 많다. 그래프와 관련된 수학적 정리가 매우 많다. - 그래프 이론이라는 분야가 따로 있다. 그래프에 관한 중요한 수학적 지식 간선의 개수는 정점의 제곱보다 작거나 같다. -> 항상 참 각 정점의 차수의 합은 간선의 개수의 2배와 같다. -> 항상 참 - 차수는 각 정점에 연결되어 있는 간선의 수 차수의 합을 구할 때, 각 간선을 두 번씩 세기 때문이다. 그래프의 구현 : 인접 행렬 정점의 연결 관계를 2차원 배열에 0,1로 표현한다. 장점: 연결 여부를 O(1)에 알 수 있다. 단점: 인접한 정..
자료구조에서 트리는 다음과 같은 모습을 가진다. 아마 위의 사진만 보고도 대충 짐작을 할 수 있을 것이다. 트리는 자식 노드와 부모 노드로 이루어져 있다. 자식 노드에서 부모 쪽으로 계속해서 타고 올라가다 보면 결국 부모가 없는 하나의 노드로 이어지게 되는데, 이 노드를 루트 노드라고 부르며, 루트 노드를 중심으로 뻗어나가는 모습이 나무의 구조와 비슷하여 '트리'라는 이름이 붙여졌다. 트리의 재귀적 성질 트리는 그 안에 또 트리가 존재하게 된다. 트리안의 다른 트리를 서브 트리라고 한다. 이진트리(Binary Tree) 이름에서도 알 수 있듯이 자식 노드가 2개 이하인 트리를 이진트리라고 한다. 트리 순회 트래 내에 어떠한 자료가 담겨있는지를 알기 위해 사용한다. 전위 순회: Root - Left - R..
스택과 큐는 선형 자료구조이다. (Linear) 스택 스택은 말 그대로 쌓다는 의미를 가지고 있다. 스택은 Last In First Out이다. 즉 마지막에 들어간 값이 제일 처음 나온다. 1,2,3,4를 순서대로 넣는다고 생각해보자. 위와 같이 1,2,3,4 순서대로 담기게 된다. 뺄 때는 위에서부터 한 개씩 빼게 된다. 스택을 구현할 때 우리가 생각할 부분은 스택 오버플로우와 스택 언더플로우이다. 오버플로우는 스택이 가득 찼는데, 우리가 원소를 더 넣으려 할 때 발생한다. 언더플로우는 스택이 비었을 때, 우리가 원소를 더 빼려고 할 때 발생한다. 스택 구현 구현하기에 앞서 우리가 어떤 기능을 구현할지 생각해보자. S를 스택이라 하자 S.create(x) : S의 크기를 x로 지정한다. S.push(x..
오늘은 이진 탐색에 대해 정리해보려 한다. 영어로는 Binary Search라고 한다. 이진 탐색은 정렬되어 있는 숫자들 중에서 특정 숫자를 찾는다. -값들 중에 절반을 기준으로 원하는 값을 찾는다. -절반을 나눈 값을 기준으로 원하는 값이 있는 쪽에서 다시 절반을 나눈다. 즉 이진 탐색은 숫자를 절반씩 지워나가면서 찾는다. 따라서 시간 복잡도는 O(log n)이 된다. 여기서 의문점이 들 수 있다. 정렬해야 하면 O(log n)이 아니라 결국 O(n log n) 아닌가요? -> yes 따라서 이미 배열이 정렬되어 있다면 Binary Search가 효율적이다. 또는 숫자 찾기를 엄청 많이 해야 하는 경우에는 오히려 정렬을 한 뒤에 Binary Search를 하는 것이 좋다. 이제 이진 탐색을 구현해보자...
