2JINISHAPPY 2JINISHAPPY

#include #include #include #define INF 987654321 using namespace std; vector graph; int V, E; int prim() { vector cost(V + 1, INF); vector prev(V + 1, -1); vector visit(V + 1, false); priority_queue pq; pq.push(make_pair(0, 1)); cost[1] = 0; while (!pq.empty()) { int u = pq.top().second; pq.pop(); visit[u] = true; for (auto next : graph[u]) { int v = next.second; int weight = next.first; if (!vi..

c++의 구조체를 이용해서 직접 Doubly Circular Linked List를 구현해봤다 구현한 총 연산은 create, traversal, insert(first, middle, last), delete(first, middle, last) typedef struct Node { int data; struct Node* next; struct Node* prev; }Node; void create(Node* head) { head = NULL; } void traversal(Node* head) { Node* cur = head; if (head == NULL)return; do { printf("%d ", cur->data); cur = cur->next; } while (cur!= head);..

자료구조를 처음 구현할 때, C를 사용하는 사람들은 보통 array를 많이 사용한다. Stack과 Queue에는 원소의 위치를 가리키는 변수 top, front, rear가 존재한다. 이 때, Stack의 마지막 원소의 위치를 가리키는 top은 원소의 증감에 따라 함께 증가하고 감소하기에 문제가 없다. 하지만 Queue의 front와 rear는 연산을 반복하면서 값이 계속해서 증가한다. 따라서 단순한 array로 Queue를 구현하면, 원소의 push와 pop을 반복하면서 앞의 공간은 사용하지 않아 낭비되고 뒤의 공간은 부족할 수 밖에 없다. 따라서 Circular Array를 통해 Queue를 구현하는 방법이 존재한다. Circular Array란, 일반적으로 정의하는 선형의 array가 아니라 '배열..

C++의 vector는 다양한 연산들이 존재한다 (아래 포스팅 참조) 2jinishappy.tistory.com/67 [STL] vector 생성자, 함수 및 iterator 사용법 C++에서 사용되는 벡터(vector)는 배열과 유사한 자료구조지만 자동 크기 조절과 객체의 추가 삭제를 제공한다 크기가 가변적이거나 객체의 추가 및 삭제가 자주 일어날 때, 동적인 상황에서 자주 2jinishappy.tistory.com 정적 array와 비교되는 vector의 가장 큰 장점은 stl 라이브러리 내에서 자동으로 크기를 조절해주고, element들의 추가 및 삭제가 굉장히 용이하다. 또한 다양한 멤버함수들을 제공해줘서 vector를 이용한 다양한 연산을 할 수 있다. 우리는 vector의 자동 크기 조절에 대..

다익스트라 알고리즘은 가중치가 양수로만 이루어져 있는 무방향/방향 그래프에서 최단거리를 찾는 알고리즘이다 (unweighted 그래프의 경우는 BFS로 최단거리를 탐색 가능하다) 알고리즘은 다음과 같다🤗 1️⃣ 임의의 출발점 u에서부터 최단거리를 저장할 배열 dist[vertex]를 선언하고 dist[u]에는 0을, 다른 노드들에는 INF를 저장한다 2️⃣ 출발점 u를 현재 노드(cur)로 저장한다 3️⃣ cur와 인접한 노드(next)에 대해 dist[cur] + edge[cur][next]와 dist[next]를 비교한다 4️⃣ 둘 중 최솟값을 dist[next]에 갱신한다(INF일 경우 전자의 값으로 한다) 5️⃣ cur와 인접한 모든 노드에 대해 이 작업을 수행한다 6️⃣ cur의 상태 배열 vi..

배열 또는 벡터를 초기화할 때 memset과 fill을 자주 사용한다 memset 헤더파일을 포함하여 사용한다 memset(배열 이름, 초기화 값, 배열 크기); ( ex. memset(visit, false, sizeof(visit)); ) 1바이트 단위로 메모리를 초기화하기 때문에 배열값을 0으로 초기화 할 때 주로 사용한다 하지만 bool형이 아닌 배열을 1로 초기화는 불가능하다 위의 사진처럼, int형은 4바이트 중 1바이트 단위로 1로 초기화하기 때문에 10000000100000000... 이 되어 위와 같은 값이 나온다 그렇기 때문에 bool형 배열 초기화 혹은 0으로 초기화할 때 사용하자 fill 헤더파일을 포함하고 std namespace를 사용한다 fill(시작 위치, 끝나는 위치 +1,..

C++에서 사용되는 벡터(vector)는 배열과 유사한 자료구조지만 자동 크기 조절과 객체의 추가 삭제를 제공한다 크기가 가변적이거나 객체의 추가 및 삭제가 자주 일어날 때, 동적인 상황에서 자주 사용한다😲 사용 시 헤더 파일을 추가하고, using namespace std;를 표기해주어야 한다 vector var_name 으로 선언한다 생성자 vector v : 빈 vector 생성 vector v (n) : 기본값으로 초기화된 n개의 원소를 가진 vector 생성 vector v (n, x) : x값으로 초기화된 n개의 원소를 가진 vector 생성 vector v (v2) : v2 vector의 복사본 생성 자주쓰는 멤버함수 v.assign(n, x) : v에 x값으로 n개의 원소 할당 v.at(i..

유형 이름 바이트 범위 (signed)int 4 -2,147,483,648 ~ 2,147,483,647 unsigned int 4 0 ~ 4,294,967,295 char 1 -128 ~ 127 unsigned char 1 0 ~ 255 short, (sighed)short int 2 -32,768 ~ 32,767 (signed)long long 8 -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 unsigned long long 8 0 ~ 18,446,744,073,709,551,615 bool 1 true or false float 4 3.4E+/-38(7개의 자릿수) double 8 1.7E+/-308(15개의 자릿수) 코딩할 때 자주 쓰는 변수 자..