본문 바로가기

분류 전체보기

제1종 스털링 수 원소의 개수가 N인 집합을 구분되지 않는 K개의 원순열로 분할하는 방법의 수이다. 이를 D[N][K]로 정의하면 D[N][K]=D[N-1][K-1]+(N-1)*D[N-1][K] 라는 점화식을 얻을 수 있다. 관련 문제: https://www.acmicpc.net/problem/1413 더보기
Minimum Path cover in DAG DAG(Directed Acyclic Graph)에서 모든 정점을 커버하는 겹치지 않는 최소의 경로의 수를 구하는 문제 전체 정점의 수가 V 커버한 경로상의 간선이 X라면 V-X개의 경로로 커버할 수 있다. 따라서 X를 최대화 시켜야한다. 간선을 고를 때 제약 조건은 한 정점이 선택 될 때 오직 하나의 indegree와 오직 하나의 outdegree가 선택되어야 한다는 점이다. 즉, indegree와 outdegree가 최대한으로 매칭되어야 한다. 이를 이용하여 indegree를 상징하는 정점과 outdegree의 정점을 상징하는 정점으로 그래프를 구성하여 해당 그래프의 이분 매칭을 구함으로서 Minimum Path cover in DAG를 구할 수 있다. 참조: http://koosaga.com/ent.. 더보기
BOJ)5624 좋은 수 문제:icpc.me/5624 좋은 수의 조건은 나보다 먼저 들어온 수 i, j ,k 의 합이 나와 같은 경우가 존재하는 경우이다. 우리는 이 수식을 i+j+k=x 로 생각할 수 있고 이 수식을 i+j=x-k로 바꿔 생각할 수 있다. 그러면 우리는 x를 받기전에 들어온 모든 수들의 합의 셋(i+j)들을 배열로 저장하여 O(1)만에 존재하는지 확인할 수 있다. 고로 모든 x-k에 대하여 같은 i+j가 존재하는지 확인해 준다면 O(N^2)에 문제를 해결할 수 있다. 1234567891011121314151617181920212223#include #include #define mid 200000using namespace std;int a[5010], n, b[400040], res;int main() { s.. 더보기
BOJ)12961 체스판2 문제:icpc.me/12961 체스판에 조건을 만족시키면서 동시에 채울 수 있는 타일의 최대 개수를 출력하는 문제이다. 타일의 모서리가 항상 검은칸을 덮게 체스판에 채울 경우 인접한 두 칸은 한 칸은 홀수 행에 한 칸은 짝수 행에 위치함을 알 수 있다. 고로 우리는 하얀 칸중 홀수 -> 검은 칸 -> 하얀 칸중 짝수 로 플로우를 흘려주어 얻을 수 있는 최대 유량이 답이 됨을 알 수 있다. 단 이 때 검은 칸을 통하여 플로우는 1만 흘러야 하므로 검은 칸을 정점 분할 시켜주어 정점 사이의 capacity를 1로 주어 풀어야한다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545.. 더보기
BOJ)3654 L퍼즐 문제:icpc.me/3654 L퍼즐 모양으로 패턴을 완성시킨다고 가정하였을 경우 B 정점은 인접한 W정점중 하나는 홀수행의 정점에 하나는 짝수행의 정점에 매칭이 되어야 한다. 따라서 두개의 플로우 모델링을 하여 하나는 홀수행의 W들과 B의 최대 매칭 하나는 짝수행의 W들과 B의 최대 매칭을 구한 뒤 두 값과 B의 개수가 같은지와 모든 W의 수와 2*B가 같은지 두 경우를 검사해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394.. 더보기
BOJ)13308 주유소 문제: icpc.me/13308 1->n까지의 최소 비용을 원하는 문제이므로 다익스트라로 해결해줄 수 있다. 다만 문제에서 비용과 거리가 동시에 존재하므로 현재 보는 경로상에서 정점 x까지 순회하는 동안 발견한 가장 저렴한 주유소의 주유가격을 저장하여 d[here][mincost]로 2차원 테이블을 잡아 문제를 해결해주어야 한다. 1234567891011121314151617181920212223242526272829303132333435363738394041#include #include #include #include #include using namespace std;typedef long long ll;vector vt;ll n, m, l[2550], x, y, z, d[2550][2550], r.. 더보기
BOJ)9460 메탈 문제: icpc.me/9460 최대중의 최소를 구하는 문제이므로 이분탐색으로 해결할 수 있다. 이 때 검사 조건은 현재 보고 있는 점들의 집합의 최솟값과 최댓값의 차이의 1/2이 mid보다 큰지 확인해주어 클 경우 새로운 수평터널을 생성하면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142#include #include using namespace std;int t, n, k;pair dat[10001];bool posb(double maxdist) { double minn = dat[0].second; double maxx = dat[0].second; int cnt = 1; for (int i = 1; i 더보기
BOJ)3683 고양이와 개 문제: icpc.me/3683 투표하는 시청자 v명중에서 고양이를 좋아하는 사람과 개를 좋아하는 사람으로 구분시켜 놓은 뒤 의견이 충돌하는 사람끼리 간선을 이어주면 이분그래프가 완성된다. 문제에서 물어보는건 의견충돌이 최소한이 되야하므로 이분 그래프에서의 min cut을 구해주면 된다. 답은 v-min cut이 된다. 이분매칭에서 mincut문제는 이분매칭으로 해결할 수 있다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include #include #include #include #include #include using namespace std;int t, c.. 더보기
스터디를 위한 링크드 리스트 ※ 발코딩이라 오류가 있을 수 있습니다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697#include #include using namespace std;struct Node { int data; char cdata; //... 원하는 자료형을 선언하면 됨 Node* prev; Node* next; Node(int data, char cdata) :data(data), cdata(cdata) { prev = next = N.. 더보기
BOJ)2610 회의준비 문제: icpc.me/2610 각각의 컴포넌트에서 해당 컴포넌트에 속한 모든 정점으로 가는 최단거리들의 최댓값이 최소가 되는 정점들을 출력하는 문제이다. 각 정점들간의 최단거리는 플로이드 워셜을 이용하여 구해주면 되고 어떤 컴포넌트에 속한 정점에서 해당 컴포넌트에 속한 모든 정점으로 가는 최단거리들 중 최댓값을 힙에 저장하여 순서대로 답에 넣어주는 것으로 문제를 해결할 수 있다. 힙을 볼 때 이미 처리한 컴포넌트에 속한 정점은 지나쳐주어야하는데 이는 disjoint-set을 이용하면 간단하게 해결해줄 수 있다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859.. 더보기

티스토리툴바