C++/알고리즘

Disjoint Set 상호 배타적 집합은 최소 스패닝 트리를 배울 때 매우 좋은 역할을 하기 때문에 미리 알아보자. 다른 이름으로는 Union-Find라고 부른다. 예를 들어, 리지니라는 게임이 인기가 있고 배그가 인기가 있으니 리비지 배틀그라운드 라는 혼종 게임을 만들자고 해보자. 혈맹전 + 서바이벌을 같이 하는 것이다. 그래서 생각해보면 1인 팀 1000명(팀 id 0~999)가 있고 동맹을 맺을 수 있다.(1번팀 + 2번팀 을 동맹하면 = 1번팀으로 합쳐진다) 우리가 만약 vector 자료구조만 알고 있다고하면 다음과 같이 코딩을 할 것이다. void LineageBattleground() { struct User { int temaId; // TODO }; // TODO : UserManager..

버블 정렬 버블 정렬은 앞에서부터 2개씩 짝을 지어 두개의 값을 비교해 순서를 바꾼다. 한 사이클이 끝나면 맨 뒤의 가장 큰 값이 배치하는 것을 보장할 수 있다. 따라서, 다음 사이클에 2번째의 값을 찾아내고 이 사이클을 계속하면 순서가 정렬이 될 것이다. 효율성은 거의 최악에 가깝다. void BubbleSort(vector& v) { const int n = (int)v.size(); for (int i = 0; i v[j + 1]) { swap(v[j], v[j + 1]); } } } } int main() { vector v{1, 5, 3, 4, 2}; BubbleSort(v); } 시..

이진 탐색 c++ 같은 경우에 map을 사용할 경우 우리는 아무런 위화감 없이 이진 탐색 트리를 사용할 수 있다. 하지만 면접이나 자료구조를 배울 때는 실제로 구현해 봐야 와닿기 때문에 구현까지 해보겠다. 이진 탐색은 무엇인가. 어떤 배열에 데이터가 정렬되어 있다고 할 때, 특정 데이터를 찾을 때 처음부터 끝까지 순회를 돌아 찾을 경우 O(N)의 시간 복잡도를 가진다. 되게 효율적이지 못하기 때문에 우리가 친구들끼리 놀 때, 업다운게임과 같이 생활의 지혜를 도입한 것이다. 데이터를 찾는 범위를 반으로 줄이고 줄이고 하기 때문에 O(logN)의 시간복잡도를 가진다. 이진 탐색을 구현해보자. #include #include #include #include #include using namespace std;..

트리 힙과 우선순위 큐가 트리 형태로 이루어져있기 때문에 어느정도 알고 있어야한다. 트리란? 계층적 구조를 갖는 데이터를 표현하기 위한 자료구조이다. 노드와 간선으로 이루어져있다. 이것만 보면 그래프와 매우 유사한 형태를 가지고 있다. 트리와 그래프의 큰 차이는 트리는 계층 구조를 가지는 것이다. 그래프는 동등한 위치의 데이터들을 간선으로 이은 것이라 할 수 있다. 제일 중요한 것은 root와 leaf이다. 간단하게 코드로 나타내보자. #include #include #include #include #include using namespace std; using NodeRef = shared_ptr; struct Node { Node() { } Node(const string& data) : data(d..

그래프 그래프란 현실 세계의 사물이나 추상적인 개념 간의 연결관계를 표현 한 것이다. 정점(vertex)는 데이터를 표현(사물, 개념 등)하고 간선( edge)는 정점들을 연결하는데 사용한다. 예시는 다음과 같다. 그래프를 사용해서 정말 많은 유용한 기술들을 구현 할 수 있기 때문에 무조건 공부해야하는 내용이다. 그래프에는 여러 종류가 존재하는데 위의 사진 뿐만아니라 edge에 가중치를 부여한 가중치 그래프도 있다. 또한 edge의 방향이 존재하는 방향그래프가 존재한다. 이는 두 사람 사이의 호감도나 일방 통행이 포함된 도로망 등에 사용된다. 그렇다면 그래프를 코드로 어떻게 표현해야 할까?? void CreateGraph_1() { struct Vertex { vector edges; // data };..

스택 스택은 LIFO를 따른다. 즉 Last In First Out 후입 선출을 따른다. 먼저 들어온 데이터가 나중에 나가는 구조의 자료구조이다. 게임에서 자주 사용하는 기능중 하나인 되돌기기 기능을 구현할 때 스택을 사용한다. #include #include using namespace std; int main() { stack s; s.push(1); s.push(2); s.push(3); // 비었나?? while (s.empty() == false) { int data = s.top(); // 최상위 원소 삭제 s.pop(); cout

선형 자료구조 선형 구조는 자료를 순차적으로 나열한 형태이다. 배열이나 연결리스트, 스택, 큐 등을 말한다. 비 선형 구조는 하나의 자료 뒤에 다수의 자료가 올 수 있는 형태를 의미한다. 트리나 그래프 등이 있다. 선형 구조는 어떤 언어에서든 구현되어 있다. 배열 배열은 사용할 방 개수를 고정해서 계약하고 절대 변경이 불가능하다. 연속된 방을 배정 받아 사용한다. 장점은 연속된방이라는 점이고 단점은 방을 추가하거나 축소가 불가능하다는 점이다. 호텔에서 우리가 친구 3명이서 체크인 할 때 101호 , 102호, 103호를 배정 받았지만 친구 한명이 갑자기 급한일로 읺 ㅐ집에 가면 103호를 환불 받을 수 없는 것과 동일하다. 동적 배열 동적 배열은 사용할 방 개수를 유동적으로 계약하는 것이다. 이 역시 연..

C++ 알고리즘을 다루기 위해 미로게임을 통해 차근차근 하나씩 쌓아 올릴 예정이다. 가령 미로를 탈출하는 알고리즘을 처음에는 오른손 법칙부터 그걸 개선하고 길 찾기 알고리즘으로 수정하는 식으로 말이다. 환경 설정 Visual Studio 2022으로 진행한다. 콘솔앱으로 진행할 것이기 때문에 어떤 버전으로 해도 상관은 없다. 일반 algorithm을 공부할 때는 algorithm 프로젝트에, maze는 maze 프로젝트에서 관리를 하겠다. 그리고 ConsoleHelper 클래스를 하나 만들겠다. 이는 콘솔에 출력하는 것을 도와주는 클래스 이다. Maze의 속성에 들어가 미리 선언된 컴파일러 헤더를 '사용'으로 바꿔주고 헤더 파일은 pch.h로 설정한다. pch 클래스를 만들고 pch.cpp 속성을 들어거..