CS/자료구조 & 알고리즘

C++ vector empty()와 size()간 차이

vector::empty() 벡터가 비어있는지 확인하는 함수이다. Input : myvector = 1, 2, 3, 4, 5 myvector.empty(); Output : False Input : myvector = {} myvector.empty(); Output : True 시간 복잡도 : O(1) #include #include using namespace std; int main() { vector myvector{}; if (myvector.empty()) { cout

C++ vector사용법 및 설명 (장&단점)

vector vect; // vect는 stack, 각 원소들은 heap vector *vect = new vector; // vect와 각 원소들 모두 heap vector vect; // vect는 stack, 각 원소들은 heap 그리고 가리키는 대상들은 heap 또는 stack https://stackoverflow.com/questions/8036474/when-vectors-are-allocated-do-they-use-memory-on-the-heap-or-the-stack 속도적인 측면에서 array(배열)에 비해 성능은 떨어지지만 메모리를 효율적으로 관리하고 예외처리가 쉽다는 장점이 있다. Vector의 초기화 vector 변수명 백터 생성 vector 변수명(숫자) 숫자만큼 백터 생성 ..

C 정렬 코드

선택 정렬 #include int size; // 배열의 크기 void selectionSort(int a[], int size) { int t, temp; printf("\n정렬할 원소 : "); for (t = 0; t = 1) { for (int i = 0; i >", interval); for (t = 0; t < inde..

컨테이너 어댑터 (스택, 큐, 우선순위 큐)

컨테이너 어댑터(container adapter)란 기존 컨테이너의 인터페이스를 제한하여 만든 기능이 제한되거나 변형된 컨테이너를 의미한다. 이러한 컨테이너 어댑터는 각각의 기초가 되는 클래스의 인터페이스를 제한하여, 특정 형태의 동작만을 수행하도록 한다. 단, 반복자를 지원하지 않으므로 STL 알고리즘에서는 사용할 수 없다. 컨테이너 어댑터의 종류 STL에서는 컨테이너 어댑터로 다음과 같은 클래스 템플릿을 제공한다. stack queue priority_queue 스택(stack) 스택(stack) 컨테이너는 vector 클래스의 인터페이스를 제한하여, 전형적인 스택 메모리 구조의 인터페이스를 제공한다. 스택 컨테이너는 stack 헤더 파일에 정의되어 있다. 스택 메모리 구조는 선형 메모리 공간에 데이..

[C++] Deque 데크

데큐는 double-ended queue의 약어이다. 즉, 양방향으로 입출력이 가능한 큐이다. (큐는 한쪽방향으로만 입력이 가능하고 반대방향으로 출력이 가능하다). #include #include using namespace std; int main() { deque dq; for(int i = 1; i

선형(Linear) / 비선형(Non Linear) 자료구조

선형 자료구조 (Linear) 선형 자료구조란 하나의 자료 뒤에 하나의 자료가 존재하는 것이다. 자료들 간의 앞뒤 관계가 1:1의 선형관계 배열과 리스트가 대표적이고 더 나아가서 스택, 큐도 이에 해당된다. 비선형 자료구조 (NonLinear) 비선형 자료구조란 하나의 자료 뒤에 여러개의 자료가 존재할 수 있는 것이다. 자료들 간의 앞뒤 관계가 1:n, 또는 n:n 의 관계 트리와 그래프가 대표적이며 계층적 구조를 나타내기에 적절하다. 정리 출처 : https://goodgid.github.io/DS-Linear-and-NonLinear/

그래프 개념

다음 두 가지 요소로 구성된다. Vertex의 집합 Edge의 집합 여기서 Vertex는 "어떤 대상의 객체"를 의미하고, Edge는 "Vertex간의 관계"를 뜻한다. 그래프는 Vertex와 Edge의 set으로 정의되며, 구성된다고 볼 수 있다. Graph와 관련된 용어정리 Graph와 관련되서 알고 있어야할 용어의 종류는 다음과 같다. Vertex : 실세계에서의 어떤 대상을 표현하는 객체 문헌에 따라서 Vertex를 "node"라고 표현하기도 함. Edge : 두 Vertex간에 관계가 존재하는 경우 Edge가 존재한다. 문헌에 따라서 Edge를 "arc"라고 표현하기도 한다. Adjacent : 두 Vertex 간에 Edge가 존재함을 의미 Path : 두 Vertex간에 Edge로서 연결되는 ..

시간 복잡도 (Time Complexity)와 공간 복잡도 (Space Complexity)

알고리즘 성능 평가 평가하기 위해 '복잡도(Complexity)'의 척도를 사용한다. 그중 시간 복잡도와 공간 복잡도의 개념이 나오며, 동일한 기능을 수행하는 알고리즘이 있을 때 복잡도가 낮을 수록 좋은 알고리즘이라 말한다고 한다. 시간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석 공간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석 1. 시간 복잡도 시간 복잡도는 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 의미한다. 같은 결과를 갖는 프로그래밍 소스도 작성 방법에 따라 걸리는 시간이 달라지며, 같은 결과를 같는 소스라면 시간이 적게 걸리는 것이 좋은 소스다. 빅-오 표기법 예를 들어, 동전을 튕겨 뒷면이 나올 확률을 이야기 할 때 운이 좋으면 1번에 뒷..

C++ 그래프를 이용한 BFS / DFS 계속 업데이트할 예정

출처 : https://www.youtube.com/watch?v=tWVWeAqZ0WU 첫번째 문제 #include #include #include #include #include using namespace std; #define TOTAL_SIZE 1000 #define y first #define x second vector graph[TOTAL_SIZE]; bool visited[TOTAL_SIZE]{ false }; int edge = 0; void DFS(int _start) { cout

BOIDS (군중 알고리즘) RTS AI

스타크래프트의 하이브리드 최적 경로 마이크로 관리는 RTS 게임의 가장 중요한 기능이다. 싱글 유닛 또는 한 그룹의 유닛을 드래그해서 선택을 하여 적을 공격하게끔 하는 것이며 이러한 AI 기능은 구현하고자 할 때 큰 골치거리다. 두 가지의 구현 방법이 있다. 퍼텐셜 필드 알고리즘 : 목표점으로 이끄는(attractive) 인공적인 포텐셜 필드와 장애물로부터 멀어지게 내보내는(repulsive) 인공적인 포텐셜 필드를 형상공간에 구축하는 알고리즘. 군중 이동 알고리즘 : 군중 이동(새 떼라던지 물고기들의 움직임 등 여러 집단이 함께 움직이는)에 대한 알고리즘. 게임 유닛들의 내비게이션은 주로 A*와 같은 최단 경로 알고리즘을 사용한다. 하지만, RTS와 같이 월드가 수시로 변화하는 게임에는 적합하지가 않다..