분류 전체보기

[골4] 11404 - 플로이드

#include #include using namespace std; #define MAX 987654321 int info[101][101]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); // 0번부터 100번까지 채움 fill(info[0], info[101], MAX); int n, m; cin >> n >> m; for (int i = 1; i > from >> to >> cost; info[from][to] = min(info[from][to], cost); } for (int k = 1; k

[골5] 15686 - 치킨 배달

#include #include #include #include #include using namespace std; using IntPair = pair; #define y first #define x second vector board; vector house, chicken; int m, n, res = 0; bool vis[13]; int distance(IntPair a, IntPair b) { return abs(a.y - b.y) + abs(a.x - b.x); } void DFS(int start = 0, int end = 0) { if (end == m) { int tmpRes = 0; for (int i = 0; i < house.size(); i++) { int dist = INT_M..

[골4] 1504 - 특정한 최단 경로

#include #include #include #include using namespace std; using IntPair = pair; #define y first #define x second vector adj[805]; int d[805]; priority_queue pq; const int MAX = 4e8; int N, E; void Dijk(int start) { fill(d, d + N + 2, MAX); d[start] = 0; //첫 번째 길이, 두 번째 정점 pq.push({ d[start],start }); while (!pq.empty()) { auto cur = pq.top(); pq.pop(); if (d[cur.x] != cur.y) continue; for (auto n..

[골4] 1043 - 거짓말

#include #include #include #include using namespace std; #define MAX 50 vector v(MAX); vector know; int parents[MAX]; int n, m, k; int Find(int x) { return x = (parents[x] == x) ? x : Find(parents[x]); } void Union(int x, int y) { parents[Find(x)] = Find(y); } int main() { ios::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(NULL); cin >> n >> m >> k; // 배열 초기화 while (k--) { int t; cin >> t; k..

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

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

[골5] 1916 - 최소 비용 구하기

#include #include #include #include #define INF 1e9 + 10 #define MAX 1001 #define y first #define x second using namespace std; using IntPair = pair; vector g[MAX]; priority_queue pq; vector dist(MAX, INF); int src, dst; void Dijkstra() { pq.push({ 0,src }); dist[src] = 0; while(!pq.empty()) { int cost = -pq.top().y; int cur = pq.top().x; pq.pop(); if (dist[cur] < cost) continue; for (int i = 0;..

C/C++ 예외상황에서의 포인터의 동작

포인터의 사용법의 구문과 의미는 C 표준 문서(http://bit.ly/173cDxJ)에 매우 자세히 설명되어 있다. 그러나 표준 문서가 포인터의 동작을 명확히 정의하지 못하는 경우가 있다. 이러 떄 표준 문서는 포인터의 동작을 다음과 같이 정의한다. - 구현 방법에 따라 정의된 행동(Implementation-defined behavior) 동작에 대한 문서화된 구현을 제공한다. 구현 방법에 따라 정의된 행동의 예로, 정수에 대한 오른쪽 시피트 연산에서 상위 비트의 확장 방법이 있다. - 명시되지 않은 행동(Unspecified behavior) 동작에 대한 구현을 제공하지만 문서화하지 않는다. malloc함수에 인자로 0을 주고, 실핼할 때 메모리가 얼마나 할당되는가 하는 것이 명시되지 않은 행동의 ..

페이징(Paging)이란? 페이지 테이블이란?

페이징(Paging)이란? 논리주소의 메모리를 고정된 크기의 페이지(Page)로 나누어 관리하는 기법이다. 페이징은 아래와 같은 특징들을 갖고 있다. 물리주소 공간(Physical address)은 연속적이지 않을 수 있다(noncontiguous) 페이지는 모두 같은 크기를 가진다. 물리주소 공간을 페이지와 같은 사이즈로 나눈 것들을 프레임(Frame)이라고 한다. 페이지 사이즈(=프레임 사이즈)는 하드웨어에 의해 정해진다. 페이지의 크기는 일반적으로 2의 제곱수를 사용한다. 일반적으로 4KB(2^12) ~ 1GB(2^20) 페이지 테이블(page table)을 이용해 논리주소에서 프레임을 가리키는 물리주소로 매핑한다. 외부 단편화는 발생하지 않으나, 내부 단편화는 발생한다. 페이지 테이블(Page T..

[Unreal] Construction Script

블루프린트 내의 각각의 인스턴스에 다양성을 줄 수 있는 스크립트. 게임 내 레벨을 구축하거나, 블루프린트 내의 프로퍼티를 업데이트 할 때 등등을 구현한다. 블루프린트 인스턴스 생성시 컴포넌트 리스트 다음에 실행되는 부분이다. 따라서 블루프린트 인스턴스에서 필요한 초기화 작업을 할 수 있다. 블루프린트와 관련된 가장 최신의 정보를 제공 같은 블루프린트로 만든 인스턴스라도 이 Construction Script 을 통해 인스턴스마다 개별적인 특성을 부여할 수 있다. 이 Construction Script 안에서 각각의 인스턴스마다 다르게 부여할 프로퍼티들을 public 변수로 에디터에서도 열고 에디터에서 각각의 인스턴스마다 이 변수 값들을 설정하게 한 후 이를 Setting 하는 작업을 한다. 2 개의 변수..

[골4] 1753 - 최단 경로

#include #include #include #include #define INF 1e9 + 10 #define pi pair int v, e, st; using namespace std; vector adj[20005]; int d[20005] = { 0, }; void Dijkstra() { fill(d, d + 20005, INF); priority_queue pq; d[st] = 0; pq.push({ d[st],st }); while (!pq.empty()) { auto cur = pq.top(); pq.pop(); int dist = cur.first, idx = cur.second; if (d[idx] != dist) continue; for (auto& [cost, nidx] : adj..