본문 바로가기

알고리즘 관련

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.. 더보기
BOJ)2610 회의준비 문제: icpc.me/2610 각각의 컴포넌트에서 해당 컴포넌트에 속한 모든 정점으로 가는 최단거리들의 최댓값이 최소가 되는 정점들을 출력하는 문제이다. 각 정점들간의 최단거리는 플로이드 워셜을 이용하여 구해주면 되고 어떤 컴포넌트에 속한 정점에서 해당 컴포넌트에 속한 모든 정점으로 가는 최단거리들 중 최댓값을 힙에 저장하여 순서대로 답에 넣어주는 것으로 문제를 해결할 수 있다. 힙을 볼 때 이미 처리한 컴포넌트에 속한 정점은 지나쳐주어야하는데 이는 disjoint-set을 이용하면 간단하게 해결해줄 수 있다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859.. 더보기
BOJ)5913 준규와 사과 문제: icpc.me/5913 (1,1)에서 (5,5)까지 모든 정점을 한번씩 다 들린 뒤 갈 수 있는 경로의 수를 구하는 문제이다. dfs를 이용하여 나올 수 있는 모든 경우를 탐색해주면 된다. 주의할점은 한번의 경로의 탐색이 끝난 뒤 visited를 해제해주어 다음 경로 탐색 때 그 정점을 방문할 수 있게 해주어야 한다. 1234567891011121314151617181920212223242526272829303132333435#include #include using namespace std;int a[6][6], visited[6][6], k, x, y, r;int dx[] = { 0,0,1,-1 };int dy[] = { 1,-1,0,0 };bool chk(int x, int y) { retu.. 더보기
BOJ)3109 빵집 문제: icpc.me/3109 맨 왼쪽부터 맨 오른쪽 까지 중복되지 않는 최대 경로의 개수를 구하는 문제이다. 우리는 x->y로 가는 경로가 있을 경우 무조건 오른쪽으로만 이동가능하므로 h라는 지점에서 갈 수 있는 길이없다면 다시 h를 밟아도 경로가 없다는걸 그리디하게 생각하면 알 수 있다. 이 생각에 기반하여 dfs를 이용하여 갈 수 있는 경우가 나오면 다른 방향을 탐색하지 않는 것으로 경로의 중복을 막아 답을 구해줄 수 있다. 123456789101112131415161718192021222324252627282930313233#include #include using namespace std;int r, c, visited[10002][502], res;char a[10002][502];int dx.. 더보기
BOJ)1251 단어 나누기 문제: icpc.me/1251 단어를 세 단어로 나눈 뒤 나눈단어를 전부 뒤집어 다시 붙인 단어들 중 사전순으로 가장 앞서는 단어를 출력하는 문제이다. N이 50까지 밖에 안들어오기 때문에 가능한 경우를 전부 뽑아내도 50C3 밖에 안되므로 모든 경우를 탐색하여 결과를 확인해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839#include #include #include #include #include using namespace std;vector vt;string a;void rev(string &x, int lo, int hi) { string z = x; for (int i = lo; i = a.length() .. 더보기

티스토리툴바