전체 글
[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
[Life] 첫 취업
2차면접을 끝내고 게임회사 신입프로그래머로 취업했다. 내 백수생활 안녕. 서류 > 실무면접 > 인사면접이 있었는데, 시스템이나 문법지식이 부족해도 그동한 해온 프로젝트들의 경험을 좋게 평가해주신거 같다. 역시 기록이 중요하다. 입사하면 포스팅 열심히 해야지 ㅋㅋ...
[Blog] 티스토리 스킨 업데이트
정보처리기사 필기를 공부하면서, 이곳 저곳 블로그를 탐색하다가 hELLO 스킨을 발견하였다. hELLO 티스토리 스킨을 소개합니다. hELLO hELLO 스킨은 본래 기능의 많이 없었다가, 최근 반응이 나쁘지 않아서 여러 기능의 추가와 함께 업데이트를 여러 번 하게 되었습니다. hELLO 1.0 때와 비교하면 비교할 수도 없을 만큼의 기능과 pronist.dev 다크모드 깔끔한 UI가 너무 맘에 든다. 예전 블로그 스킨 코드와 파일은 싹다 삭제하고, 다시 세팅하였다. 모바일 페이지 리다이렉션 코드도 다시 업로드했다. 티스토리 모바일 스킨을 완전히 없애서 광고 송출하는 방법 티스토리 블로그의 주소에서 /m을 더하면 카카오에서 제작한 모바일 스킨으로 강제적으로 넘어갑니다. 모바일 스킨의 경우 다음과 같은 단..
[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&..