본문 바로가기

분류 전체보기

BOJ)2146 다리만들기 문제: icpc.me/2146 dfs를 이용하여 각 나라들을 구분해준 후 bfs를 이용하여 각 나라들에서 어떤 다른 나라로 갈 수 있는 최단 거리를 모두 구해준 뒤 그 중 최솟값을 출력해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172#include #include #include #include #include using namespace std;int n, a[101][101], disc[101][101], c;bool chk(int x, int y) { return 0 더보기
BOJ)5427 불 문제: icpc.me/5427 가중치가 없는 그래프에서의 최단경로 이므로 BFS를 이용하여 문제를 해결해준다. 단 불이라는 새로운 조건이 존재하는데 우리는 queue에 상근이와 불을 동시에 삽입해주어 불일 경우와 상근이일 경우를 다르게 처리해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384#include #include #include #include using namespace std;int t, w, h, sx, sy;char a[1001][1001];in.. 더보기
BOJ)1745 숨기 문제: icpc.me/1745 F개의 방이 있을 때 각방마다 학생들이 숨을 수 있는 수와 현재 몇명의 학생들이 있는지 수가 주어진다. 이 때 방 A에서 B로 이동할 때 걸리는 시간이 주어질 때 모든 학생이 숨을 수 있는 최소 시간을 구하는 문제이다. 우리는 소스 -> I번 방 -> I번 방에서 ->J번 방으로 연결 된 정점 -> J번 방 ->싱크로 모델링을 하여 모든 학생들이 숨을 수 있는지 여부를 알 수 있다. 이때 capacity를 소스 -> I번 방은 현재 i번방에 있는 학생 수 / J번 방 -> 싱크는 j번 방에 숨을 수 있는 학생 수 나머지는 INF를 주면 된다. 이렇게 하여서 흘린 maximum flow가 현재 있는 학생들의 수의 총합과 같다면 현재 모델링에서 학생들이 전부 숨을 수 있는것이다.. 더보기
BOJ)5397 키로거 문제:icpc.me/5397 메모장에 커서의 입력하는 단어와 커서의 움직임과 누른 백스페이스가 기록될 때 최종적으로 남는 단어를 출력하는 문제이다. 중간에 삽입 삭제가 가능한 링크드리스트를 구현하여 해결할 수 있다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091#include #include using namespace std;struct Node { char data; Node *prev, *next; Node() :data('\0'), pr.. 더보기
BOJ)2075 N번째 큰 수 문제:icpc.me/2075 N^2개의 수가 들어올 때 N번째로 큰 수를 구하는 문제이다. N이 최대 1500 밖에 안들어오므로 단순히 값을 다 받아서 정렬해주는 N^2logN의 해법으로 해결할 수 있다. 하지만 메모리제한이 10MB이므로 힙을 이용하여 수를 받을 때 마다 큰 수 N개만큼만 저장해주고 그 수들중 가장 작은 수와 들어오는 수를 비교를하여 힙을 관리해주면 된다. 123456789101112131415161718192021222324#include #include #include using namespace std;int n, x;priority_queue pq;int main() { scanf("%d", &n); for (int i = 0; i 더보기
BOJ)1326 폴짝폴짝 문제: icpc.me/1326 각 징검다리에 숫자가 써있고 해당 징검다리에서는 숫자의 배수만큼 떨어져 있는 징검다리까지 점프 할 수 있을때 a에서 b까지 의 최단거리를 출력하는 문제이다. 해당 징검다리에서 갈 수 있는 모든 징검다리까지 cost가 1인 간선을 연결해주고 다익스트라를 이용하여 최단거리를 구해줄 수 있다. 이 때 주의할 점은 배수 이기 때문에 나보다 작은 지점으로도 점프할 수 있다. 12345678910111213141516171819202122232425262728293031323334353637#include #include #include #include #include using namespace std;int n, a[10001], s, e, dp[10001];vector vt;in.. 더보기
BOJ)13166 범죄 파티 문제: icpc.me/13166 범죄자 N명과 친구 2*N명의 친구 관계와 임계점이 주어질 때 모든 범죄자가 친구랑 매칭 될 수 있는 파티 비용의 최솟값을 구하는 문제이다. 파티 비용의 최솟값을 파라메트릭 서치로 탐색할건데 이 때 탐색 기준은 mid를 파티 비용으로 정했을 때 모든 범죄자가 친구들과 매칭 되야 하므로 범죄자와 친구의 이분 매칭이 N이 됨을 기준으로 한다. 단, 정점의 개수가 20만이나 되므로 일반 이분매칭 소스로는 TLE를 보게되니 호프크로프트 카프 알고리즘을 이용하여 구해줘야 한다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162.. 더보기
BOJ)3736 System Engineer 문제: icpc.me/3736 작업 세트와 서버로 이루어진 이분 그래프에서 최대 매칭을 구하는 문제이다. 정점의 개수가 10000개 이므로 일반 이분 매칭 소스로는 TLE가 나므로 hopcroft-karp 알고리즘을 이용하여 최대매칭을 구해줘야 한다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182#include #include #include #include #define INF 987654321using namespace std;struct hopcroft_karp { in.. 더보기
BOJ)2660 회장뽑기 문제:icpc.me/2660 두 사람의 친구 관계가 주어질 때 어떤 사람이 가장 먼 친구 관계가 n다리 걸쳐서 친구관계가 된다면 그 사람의 점수는 n점이라 할 때 최소 점수를 갖는 사람들이 회장 후보가 된다. 회장 후보를 출력하는 문제이다. 두사람의 친구 관계를 cost가 1인 간선으로 표현한다면 플로이드 워셜을 통하여 n:n 최단거리를 구해주면 두 사람의 친구 관계가 몇다리 걸쳐있는지 알 수있다. 이를 이용하여 답을 구해주면 된다. 123456789101112131415161718192021222324252627282930313233343536#include #include #include using namespace std;int n, x, y, a[51][51], r, b[51];int main().. 더보기
BOJ)1755 숫자놀이 문제: icpc.me/1755 m과 n 이 주어질 때 m부터 n까지의 사이의 수들을 숫자 하나당 영어로 표현하였을 때 정렬된 순서대로 숫자를 출력하면 된다. map을 이용하여 string 정렬해주면 해결해줄 수 있다. 123456789101112131415161718192021222324252627282930313233343536373839404142#include #include #include #include #include using namespace std;map res;map cvt;int m, n, c;int main() { scanf("%d%d", &m, &n); cvt[0] = "zero "; cvt[1] = "one "; cvt[2] = "two "; cvt[3] = "three "; c.. 더보기

티스토리툴바