CS/자료구조 & 알고리즘

C++ 다익스트라(Dijkstra) 알고리즘 개념 및 구현 (무방향 그래프)

다익스트라 알고리즘 다익스트라(dijkstra) 알고리즘은 그래프에서 한 정점(노드)에서 다른 정점까지의 최단 경로를 구하는 알고리즘 중 하나이다. 이 과정에서 도착 정점 뿐만 아니라 모든 다른 정점까지 최단 경로로 방문하며 각 정점까지의 최단 경로를 모두 찾게 된다. 매번 최단 경로의 정점을 선택해 탐색을 반복하는 것이다. 참고로 그래프 알고리즘 중 최소 비용을 구하는 데는 다익스트라 알고리즘 외에도 벨만-포드 알고리즘, 프로이드 워샬 알고리즘 등이 있다. 동작 단계 ① 출발 노드와 도착 노드를 설정한다. ② '최단 거리 테이블'을 초기화한다. ③ 현재 위치한 노드의 인접 노드 중 방문하지 않은 노드를 구별하고, 방문하지 않은 노드 중 거리가 가장 짧은 노드를 선택한다. 그 노드를 방문 처리한다. ④ ..

[C#] 연결 리스트(Linked List)란?

1. 연결 리스트(Linked List)란? * 연결 리스트(Linked List) : 데이터를 저장하는 자료구조. 각 노드가 데이터와 포인터를 가지고 있으면서 노드들이 한 줄로 쭉 연결되어 있는 방식. 2. 단일 연결 리스트(Singly Linked List) : 단방향으로 노드들을 연결한 간단한 자료 구조. (ex) 아래는 4개의 노드를 갖는 단일 연결 리스트를 그림으로 표현한 것. using System; public class LinkedList_Study { public T Data { get; set; } public LinkedList_Study Next { get; set; } public LinkedList_Study(T data) { this.Data = data; this.Next =..

[C#] .NET의 연결 리스트 : LinkedList<T>

LinkedList : 이중 연결 리스트로 되어 있으며, 리스트 노드는 LinkedListNode 클래스를 사용. 노드를 추가하기 위한 AddFirst(처음), AddLast(끝), AddBefore(특정 노드 앞), AddAfter(특정 노드 뒤) 등 다양한 메서드가 있음. LinkedList의 메서드 종류 코드 예시) LinkedList list = new LinkedList(); list.AddLast(1); list.AddLast(2); list.AddLast(3); list.AddLast(4); var node = list.Find(2); var newNode = new LinkedListNode(3); list.AddAfter(node, newNode); //2가 들어있는 노드 다음에 3을 집..

[C#] 힙 (Heap)

1. 힙이란? : 완전 이진 트리(Complete Binary Tree)의 일종. 여러 값의 데이터들 중 최대값과 최소값을 빠르게 찾아낼 수 있는 자료구조입니다. (시간복잡도로 따지면 O(logn)이 걸림) * 힙의 특징 - 중복 값을 허용 - 루트가 최대값(새로운 데이터가 추가될 때 부모노드와 크기를 비교해 크기가 더 큰 값을 부모노드로 올리기 때문) - 새로운 데이터를 추가할 때 작은 레벨 순서대로 채움(왼쪽부터) 2. 이진 탐색 트리와 힙의 차이 * 공통점 : 둘 다 이진 트리. * 차이점 - 힙은 이진 탐색 트리와 달리 중복 값을 허용. - 힙은 각 노드들이 부모노드의 데이터 값보다 작거나 같음. - 이진 탐색 트리는 말 그대로 탐색을 위한 자료구조이고, 힙은 최대값과 최소값 검색을 위한 자료구조..

비헤이비어 트리 (Behavior Tree)

1. 비헤이비어 트리 소개 ​​비헤이비어 트리는 게임 AI같은 거를 빠르고 쉽게, 그리고 가독성도 좋고 재활용성도 좋게 만드는데 특화되어있다. FSM, HFSM이 상태가 많아지면 유지보수, 가독성 등을 잃게 되는 단점을 보완했다고 볼 수 있다. (FSM과 BT의 차이를 대략적으로 보여줌) 비헤이비어 트리는 HFSM과 마찬가지로 계층적인 특성을 띄고 있는데, (HFSM이랑 약간 유사한데, BT가 더 조직화 됐다고 보면됨.) 다만 HFSM처럼 각 상태에서 조건을 체크하고, 직접 상태를 이전시키는 것이 아닌, 각 노드는 True, False, (Running) 값을 조건에 따라서 결과값을 반환 하지만, 전이 자체는 다른 노드가 처리한다. FSM의 경우에는 A에서 B로 전이를 하려면, 해당 상태 내부에서 Set..

C++ 프림(Prim) 알고리즘으로 MST 찾기

1. 프림(Prim) 알고리즘이란? 최소신장트리(MST, Minimum Spanning Tree) 를 찾기 위한 대표적인 알고리즘이다. 여기에서 최소신장트리란, 아래와 같이 모든 노드를 연결하는 부분 그래프 중, 가장 비용이 적은 것이다. 하늘색으로 표시한 경로가 최소신장트리이다. 여기에서 최소신장트리의 길이는 (4 + 8 + 16 + 20) = 48다. 최소신장트리를 찾는 알고리즘은 크루스칼(Kruskal) 과 프림(Prim) 이 대표적이다. 2. 동작원리 프림 알고리즘에서는 MST의 후보가 될 간선을 담을 우선순위 큐가 필요하다. 우선순위 큐는 최소의 비용을 가지는 경로가 우선순위를 갖게 한다. (보통 Min Heap을 이용해서 구현한다.) 가장 먼저, 그래프에서 아무 노드나 선택하므로 가장 번호가 ..

[C++] STL 연관 컨테이너(associative container), set, multiset

set 세트set 컨테이너는 요소가 그 값에 따라 정렬되는 형태이다 즉, key라 불리는 원소(value)의 집합이다. 또한 이 원소들에 중복을 허용하지 않는다는 것이 특징이다.#include#includeusing namespace std;int main(){ set is; is.insert(55); is.insert(7); is.insert(23); is.insert(61); is.insert(7); is.insert(9); is.insert(58); set::iterator it; for(it = is.begin(); it != is.end(); it++) { cout 그냥 제멋대로 insert를 해도 알아서 정렬이 된다.​실제 트리구조는 항상 균형 이진 트리로 구성된다.이 ..

[C++] STL 연관 컨테이너(associative container), map, multimap

map, 맵 맵은 앞서 보았던 set과 거의 동일한 자료 구조다. 다만 차이점이 있다면 set은 key값만 저장하였고, map의 경우 key와 value로 구성되어 저장된다. 한마디로 key와 value 한 쌍을 이루어 자료를 보관할 수 있다. 그림은 추상적으로 map의 자료형태를 나타낸 것이다. 실제로 set과 동일하게 트리구조형태로 정렬되어 저장된다. #include #include using namespace std; int main() { map name; name.insert(pair(4, "kim")); name.insert(pair(1, "kim")); name.insert(pair(3, "lee")); name.insert(pair(5, "park")); name.insert(pair(4,..

[C++] STL list(리스트), 시퀀스 컨테이너

리스트는 대충 위그림 처럼 생겼다. 각 요소들은 앞 뒤 노드를 가지고 있어서 이중 연결 리스트로 구현된다. 리스트는 랜덤 액세스가 불가능하다. 즉, 중간에 3번째에 자료에 접근하려면 처음부터 두번째, 세번째 이런식으로 거쳐가야한다. 반면에 장점은 어떠한 위치의 자료를 삭제, 삽입 하더라도 그 속도가 빠르다는 것이다. 배열 구조와는 달리 연결된 링크만 끊어내고 다시 이어붙이는 작업만 하면 되기 때문이다. #include #include using namespace std; int main() { list alpha_list; for(char c = 'a'; c

Union-Find (합집합 찾기) 알고리즘

Disjoint Set의 개념 서로 중복되지 않는 부분 집합들 로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조 즉, 공통 원소가 없는, 즉 “상호 배타적” 인 부분 집합들로 나눠진 원소들에 대한 자료구조이다. Disjoint Set = 서로소 집합 자료구조 Union-Find의 개념 Disjoint Set을 표현할 때 사용하는 알고리즘 집합을 구현하는 데는 비트 벡터, 배열, 연결 리스트를 이용할 수 있으나 그 중 가장 효율적인 트리 구조 (아래 참고*)를 이용하여 구현한다. 아래의 세 가지 연산을 이용하여 Disjoint Set을 표현한다. Union-Find의 연산 make-set(x) 초기화 x를 유일한 원소로 하는 새로운 집합을 만든다. union(x, y) 합하기 x가 속한 집합과 y..