분류 전체보기 (146) 썸네일형 리스트형 [ BOJ 백준 12015번 - 가장 긴 증가하는 부분 수열 2 ] 해설 및 코드 https://www.acmicpc.net/problem/12015 목적 LIS(longest increasing subsequence, 최장 증가 부분 수열)의 길이를 구하자. 접근법 1. 이분탐색을 이용하여 NlogN의 복잡도로 LIS를 구한다. 2. LIS에 원소를 오름차순으로 삽입하는데, 이전 LIS의 가장 큰 원소보다 큰 원소가 주어지는 경우에만 삽입하여 길이를 늘린다. 3. 그렇지 않으면, LIS의 원소를 갱신한다.(갱신 가능한 경우는 기존 원소보다 크기가 작은 경우이다.) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 #include #define f(i,l,r) for(int i=l;i>n; vector v; while(n--){ int num;cin>>n.. [ BOJ 백준 3780번 - 네트워크 연결 ] 해설 및 코드 https://www.acmicpc.net/problem/3780 목적 통신센터와 각 기업을 잇는 라인의 길이를 구하자. 접근법 1. disjoint-set으로 접근하는데, 라인의 길이 정보를 어떻게 처리할 지가 관건이다. 2. 병합하는 과정은 클러스터 A의 센터가 클러스터 B의 기업들 중 하나에 연결되어 진행된다. 따라서 클러스터 A의 기업-센터 사이의 거리만 갱신해주면 된다. (클러스터 B의 기업-센터 사이의 거리는 변함이 없으므로...) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 #include #define f(i,l,r) for(int i=l;i>.. [ BOJ 백준 17398번 - 통신망 분할 ] 해설 및 코드 https://www.acmicpc.net/problem/17398 목적 통신망을 주어진 순으로 나누는데 필요한 비용을 구하자. 접근법 1. 통신망을 구축해 나가는데에는 disjoint-set을 이용하면 될 것이란 생각은 든다. 하지만 해당 알고리즘으로 합친 집합을 분리하는 것은 불가능(?방법이 있을 수도 있습니다...)하다. 하지만, 분리하는 과정을 거꾸로 한다면 union-find 만으로 해결이 가능하다. 2. 제거해야 할 열결 번호를 저장하고, 일단은 제거할 번호 리스트에 없는 연결만 수행하자. 그리고 제거할 번호 리스트의 역순으로 연결을 수행하며 비용을 연산하면 된다. 3. 하마터면, link/cut tree 자료구조를 공부할 뻔.... 아직은 미뤄두고 싶은... 1 2 3 4 5 6 7 8 9 .. [ BOJ 백준 10775번 - 공항 ] 해설 및 코드 https://www.acmicpc.net/problem/10775 목적 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 도킹시키자. 접근법 1. 탐욕적으로 접근하자. 비행기를 최대한 gi에 가깝게 도킹시켜야 최대한 많은 비행기를 도킹시킬 수 있을 것이다. 2. 도킹할 게이트의 위치를 찾기 위해서 하나의 배열이 필요하다. i번째 게이트가 도킹에 사용되었다면, 다음으로 도킹 가능한 게이트를 가리키는 용도이다. Disjoint-set의 루트노드를 찾는 함수를 사용하면 될 것이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 #include #define f(i,l,r) for(int.. [ BOJ 백준 11085번 - 군사 이동 ] 해설 및 코드 https://www.acmicpc.net/problem/11085 목적 Baekjoon World의 수도 c에서 Cube World의 수도 v로 가는 어떤 경로에서, 가장 작은 길의 너비를 x라고 할 때, 이 x가 가장 큰 경로를 찾자. 접근법 1. 탐욕적으로 해결한다. w개의 길을 너비 순으로 정렬하여, 큰 너비부터 해당 길의 양 지점을 잇는다. 즉, Disjoint-set을 이용하여 한 집합으로 병합한다. 2. 매번 이 과정을 진행하면서, c와 v가 한 집합에 있는지 확인한다. 3. 다른 방법으로는, BFS을 이용하여 역시 탐욕적으로 큰 너비의 길부터 이어나가면서, 이를 v에 도달할 때까지 반복하여 해결할 수도 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 .. [ BOJ 백준 3197번 - 백조의 호수 ] 해설 및 코드 https://www.acmicpc.net/problem/3197 목적 호수의 얼음이 녹아 두 마리의 백조가 만나게 되는 순간을 구하자. 접근법 1. Disjoint-set을 이용해서 얼음에 의해 분리된 지역을, 시간이 흘러 얼음이 녹으면 하나로 합쳐준다. 2. 얼음을 녹이는 과정을 BFS로 진행하면서 두 마리의 백조가 같은 집합에 속해있는지 검사한다. 3. 다른 방법으로는 BFS를 두단계로 진행하는 것이 있다. 한 가지는 얼음을 녹이는 것이고, 다른 한 가지는 백조를 퍼뜨리는 것이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 .. [ BOJ 백준 4195번 - 친구 네트워크 ] 해설 및 코드 https://www.acmicpc.net/problem/4195 목적 두 사람의 친구 네트워크에 몇 명이 있는지 구하자. 접근법 1. 분리집합 자료구조로 친구 관계를 나타내보자. disjoint-set을 구현해 봤다면 어렵지 않은 문제이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 #include #define f(i,l,r) for(int i=l;i t; while (t--) { unordered_map m; memset(p, -1, sizeof(p)); int idx = 0; int n; cin >> n; while (n--) { string a, b; cin >>.. [ BOJ 백준 16562번 - 친구비 ] 해설 및 코드 https://www.acmicpc.net/problem/16562 목적 친구의 친구도 친구라는 규칙(?)에 따라 모든 학생과 친구가 되기 위해 필요한 최소 비용을 구하자. 접근법 1. 분리집합을 이용한다. 다만, 비용이 적은 학생을 루트 노드로 하는 집합을 형성하자. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 #include #define f(i,l,r) for(int i=l;i n >> m >> k; f(i, 1, n) { cin >> cost[i]; a[i] = i; } while (m--) .. 이전 1 ··· 6 7 8 9 10 11 12 ··· 19 다음
