dh_0e

문제를 읽고 생각해 보면 greedy 문제라는 것은 쉽게 알 수 있다. 하지만 매번 gi~1까지 빈 출구를 찾으면서 greedy 하게 도킹하게 되면 G, P  풀이 과정분리 집합을 사용하여 그리디하게 출구들을 도킹시키면 $O(N)$만에 풀 수 있다. 도킹이 끝난 출구들이 연결되어 있을 때 한 집합으로 보고 연결해 준다.i번 출구를 도킹시켰을 때, i-1 출구가 비어있으면 새로운 집합(i-1이 도킹할 수 있는 가장 큰 번호의 출구인 집합)을 만들어준다.i-1 출구가 비어있지 않다면, i-1 출구의 집합에 포함시킨다.1번 출구가 포함된 집합은 더 이상 포함될 집합(i-1이 0이기 때문)이 없기 때문에 1번 출구에 -1을 저장해 주고, union_find에서 이미 도킹된 1번 출구까지 내려오게 된다면 -1을 ..

관계형 데이터 모델Introdeuced by E.F. Codd (1970)Strong theoretical foundations (강력한 기초 이론) & very simpleNumerous commercial systems (수많은 상업 시스템에 이용됨)A collection of relations and integrity constraints (관계와 무결성 제약의 묶음)Relations are unordered & Order of tuples is irrelevant (관계 간에 순서나 상하관계 X)  Attributes(속성)각 속성은 속성 값으로 허용할 수 있는 값의 집합인 domain(도메인)을 가짐속성 도메인에 속하는 값은 분할할 수 없는 atomic(원소성)을 지닌 값을 가짐도메인이 없는 것..

BFS로 풀 수 있는 간단한 문제greedy 방식이 왜 항상 최적의 값을 찾을 수 없는지 알려주기 좋은 문제같다. #include#include#includeusing namespace std;int d[101], vi[101];queue> que;int f(int cur, int c) { for (int i = 1; i pa = que.front(); que.pop(); if (pa.first == 100) { printf("%d\n", pa.second); break; } f(pa.first, pa.second); } return 0;}

조합론이 기본이 되는 문제로 계산식 발상에 좀 애먹은 문제결론적으로 메뉴들을 맵기 순으로 정렬하면, 메뉴마다 가장 높은 수치, 낮은 수치일 경우의 수가 정해져 있으므로 각각의 메뉴마다 경우의 수를 조합론으로 구해 계산해주면 된다. 풀이과정한 메뉴가 포함되는 조합의 수는 총 $2^{n-1}-1$가지이다.하지만 스코빌 수치가 이용되는 경우만 따지면 되기 때문에 i번째 메뉴가 가장 높은 스코빌 수치일 때와 가장 낮을 때만 구해주면 된다. 식으로 나타내면 다음과 같다. (i가 0~n-1일 때)가장 높은 스코빌 수치일 경우 >> $2^i-1$가장 낮은 스코빌 수치일 경우 >> $2^{n-i-1}-1$i번째 메뉴보다 높거나 낮은 스코빌을 선택할 때 모두 선택하지 않은 경우의 수가 있기 때문에 -1을 해줌 $2^n$..