Technology

[BOJ] 18138번: 리유나는 세일러복을 좋아해

18138번: 리유나는 세일러복을 좋아해 너비가 3인 티셔츠와 너비가 2인 세일러 카라를 붙이고, 너비가 5인 티셔츠에 너비가 5인 세일러 카라를 붙이고 너비가 7인 티셔츠에 너비가 4인 세일러 카라를 붙이고 너비가 10인 티셔츠에 너비 www.acmicpc.net 제한 조건 - 시간 제한 : 1s - 공간 제한 : 256MB 풀이 사용 - 사용 언어 : C++17 - 사용 시간 : 0ms - 사용 공간 : 1232KB 풀이 설명 - DFS를 이용한 이분매칭에서 셔츠와 카라를 연결하는 조건을 만들어줘야하는 문제 #include #include #include using namespace std; #define MAX 201 // 카라와 티셔츠의 최대개수 vector vt[MAX]; int match[MA..

[Unity] Singleton 패턴 Generic 으로 쉽게 구현하기

Monobehavior를 상속받는 Singleton 객체를 쉽게 구현할수 있다. Unity Singleton을 제네릭으로 만들어놓고 써봅시다. 안녕하세요. 오늘은 유니티에서 자주 사용하는 대표적인 디자인 패턴인 Singleton을 쉽게 사용하기 위하여 제네릭으로 만들 겁니다. 제네릭이란 C++ 을 사용하신 분은 다들 아시는 템플릿과 비슷한 sillyknight.tistory.com

[Algorithm] Parametric Searching

개요 매개변수 탐색은 정해진 범위 내에서 어떤 조건 P(x)를 만족하는 x의 최대 혹은 최소값을 구하는 알고리즘이다. 탐색범위내에서 임의로 x를 선택하여 해당 x가 문제의 조건을 만족시키는 값인지 검증하고 최적의 값을 찾는 방향으로 범위를 좁혀나가는 방법이다. 탐색방법으로 이분탐색을 사용하는데, 이분탐색 과정에서 선택된 x가 - 조건 P(x)를 만족한다면 : x보다 최적인 범위를 다음 탐색 범위로 설정한다. - 조건 P(x)를 만족하지 않는다면 : x보다 좋지않은 범위를 다음 탐색 범위로 설정한다. Parametrix Searching Code // 조건을 만족하는 최소값을 구하는 경우 // min : 매개변수 범위의 최소값 // max : 매개변수 범위의 최대값 int Minimum_Parametric..

[Algorithm] Bellman-Ford Algorithm

개요 가중치가 있는 방향성 그래프에서 한 특정 정점에서 다른 모든 정점으로 가는 최단 경로를 구할수 있는 알고리즘. Dijkstra's Algorithm과 같지만, 음의 가중치를 갖는 그래프에서도 사용가능하다. 다만, 음의 cycle을 갖는 그래프에서는 사용불가하다. (문제로서 성립되지 못하기때문에) 그래프를 bfs순회처럼 v1에서 hop을 뛰어넘으면서 최단경로를 갱신해나가는 방법이다. BellmanFord Algorithm // vertices : 정점 리스트 // edges : 간선 리스트 // source : 시작점 위치 // distance : 시작점으로부터 vi까지 최단경로길이 // predecessor : 시작점으로부터 vi까지 최단경로에서 vi이전정점(부모정점) function Bellman..

[Algorithm] Dijkstra's Algorithm

개요 가중치가 있는 방향성 그래프에서 한 특정 정점에서 다른 모든 정점으로 가는 최단 경로를 구할수 있는 알고리즘이다. 비슷한 목적을 가진 알고리즘으로 Bellman-ford Algorithm이 있다. 시작 정점인 v1에서 집합 V-Y까지 최단 경로의 정점을 구해서 Y로 편입시켜나가는 방법이다. High-level Algorithm F = {}; Y = {v1}; While (the instance is not solved) { select a vertex v from V-Y, that has a shortest path from v1, using only vertices in Y as intermediate; add the new vertex v to Y; add the edge (on the shor..

[Algorithm] Prim's Algorithm

개요 Kruskal's Algorithm 과 같이 최소신장 트리를 구하는 또다른 방법. Dijkstra's Algorithm 이랑 코드 흐름이 유사한 부분이 있다. 집합 Y에서 집합 V-Y를 연결하는 가장 낮은비용의 edge를 포함시켜나가는 방법이다. High-level Algorithm F = {}; // 최소신장 트리 Y = {v1}; // 집합 Y. 처음에는 v1만 포함되어있다. While (the instance is not solved) { select a vertex in V-Y that is nearest to Y; add the vertex to Y; add the edge to F; if (Y==V) the instance is solved; } Prim's Algorithm W[i][j..

[Algorithm] Kruskal's Algorithm

개요 최소 신장트리를 구하는 알고리즘. 비용이 낮은 edge부터 편입시키는 방법이다. High-level psudo code Set F = {}; // 최소신장트리 create disjoint subsets of V, one for each vertex and containing only that vertex; // 모든 정점마다 해당 점만 존재하는 부분집합을 생성한다. sort the edges in E in nondecreasing order; // 모든 Edge를 비용 오름차순으로 정렬한다. While (the instance is not solved) { select next edge; // 가장 비용이 낮은 edge를 선택된다. if (the edge connects 2 vertices in d..

[Algorithm] Spanning Tree

Spanning Tree - A connected subgraph that contains all the vertices in G and is a tree. - 비방향성 그래프 G의 모든 정점을 포함하고 있는 연결된 부분그래프이며 트리(사이클이 제거됨)이다. Minimum spanning Tree - A spanning tree with minimum weight in G and is a tree - 신장트리중에 비용이 최소인 트리 최소비용신장트리의 적용 예 - 도로 건설 : 도시들을 모두 연결하면서 도로의 길이가 최소가 되도록 하는문제 - 통신 : 전화선의 길이가 최소가 되도록 전화 케이블 망을 구성하는 문제 - 배관 : 파이프의 총 길이가 최소가 되도록 연결하는 문제 관련 알고리즘 - Kruskal&..

[Algorithm] 최대 유량 문제

Maximum Flow Problem란? Source s에서 Target t까지 최대한 보낼수 있는 유량을 구하는 문제 Ford-Fulkerson method Residual Network에서 augmenting path가 더이상 존재하지 않을때까지 path에 augment값만큼 flow를 늘려나간다. 수도코드 1 Initialize flow f = 0; while( there exists an augmenting path p in Gf ) { augment the flow along p; } Output the final flow f; 수도코드 2 Ford-Fulkerson(G, s, t) { for (each edge (u, v) in E) f(u,v) = 0; f(v,u) = 0; // Gf : R..

[Algorithm] 최대 이분 매칭 문제

문제 Given a bipartite undirected graph G=(XUY, E), find the maximum-cardinality matching M*. 주어진 이분 비방향 그래프 G에서 (중복되지 않는) 최대 매칭 집합크기를 구해라. Matching이란? A subset M of E is called Matching if no two edges in M are adjacent in G. E의 부분집합 M에 인접한 두 edge가 존재하지 않는다면, M은 Matching이라고 부른다. 성질 In a bipartite undirected graph G=(XUY,E), if every vertex has degree k>0, then there exists a perfect matching M. 이..