https://www.acmicpc.net/problem/1647예제7 121 2 31 3 23 2 12 5 23 4 47 3 65 1 51 6 26 4 16 5 34 5 36 7 4ans : 8문제의 요구사항은 다음과 같다.도시를 2개로 분할하라.분할된 2개의 도시 사이에는 간선이 존재하지 않는다.각 도시의 마을은 MST로 구성되어 있다.일단 3번 조건을 보면 MST를 구현해야하긴 하는데 어떻게 2개로 분할해야 가장 Minimum한 MST를 만들 수 있을지가 고민된다.N이 100개정도면 완전탐색으로 구현해도 될테지만 N은 10만... 완전탐색은 아니다. 만약 도시 분할 조건이 없다면 바로 MST를 구해도 된다. 그렇다면 MST를 구하는 과정에 Union-Find를 하게 되고 이 부분을 응용해서 2개의 ..

https://www.acmicpc.net/problem/2637 예제785 1 25 2 27 5 26 5 26 3 36 4 47 6 37 4 5출력 : 1 162 163 94 17하나의 완제품을 완성하는데 필요한 기본 부품의 수를 구하는 문제이다. 어떤 부품이 기본 부품인지를 구하고, 중간 부품을 기본 부품으로 치환하는 방식으로 풀이를 떠올렸다. dp를 사용한 방식인데 2차원 배열로 dp 배열을 선언해서 dp [i][j]를 i번 부품을 만드는데 필요한 j 부품의 수 (j는 기본 부품)로 생각하고 구현했다. 해당 풀이의 점화식은 다음과 같다.i번 부품에 대해(i는 중간 부품) dp[i] = dp [next.first] * next.second. next는 i번 부품을 만드는데 필요한 부품이다. 백준에서 ..

https://www.acmicpc.net/problem/21276문제를 보고 떠올린 방법은 다음과 같다.indegree를 측정하는데, 편하게 측정하기 위해 string -> int로 index를 가지고 있는 map list를 생성하였다.indegree가 0인 노드가 가문의 시조가 되고, 위상 정렬을 하면서 사전순으로 방문해야 한다.위상 정렬을 하면서 하나 방문하고 직계 자식을 구해야 하는데, 직계 자식은 indegree가 1이어야 한다. 즉, 현재 노드와 현재 노드와 연결된 간선을 제거했을 때 indegree가 0인 노드가 직계 자식이다.이 정도로 알고리즘을 생각해 두고 구현해 봤는데 정렬을 하면서 직계 자식을 구하고, 위상 정렬을 수행하고 하는 과정이 너무 번거롭고 시간 복잡도 상으로 비효율적이었다...

https://www.acmicpc.net/problem/2250예제 191 2 32 4 53 6 74 8 -15 9 106 11 127 13 -18 -1 -19 14 1510 -1 -111 16 -112 -1 -113 17 -114 -1 -115 18 -116 -1 -117 -1 1918 -1 -119 -1 -1ans :3 18depth와 col을 구하면 된다. depth는 dfs와 함께 부모의 depth + 1로 구할 수 있다. col이 문제가 되는데 col을 구하는 방법은 처음에 두 가지를 떠올렸다.각 레벨의 가장 왼쪽 노드와 가장 오른쪽 노드 사이의 노드 개수 구하기 -> widthdp로 푸는데, dp [k] = k 레벨의 width로 두고 dp [k+1] = dp [k] + k 레벨의 가장 왼쪽..

https://www.acmicpc.net/problem/20955그래프를 트리로 바꾸면 된다. 이때 사용할 수 있는 특성은 트리는 n개의 노드에 대해 n-1개의 간선을 가지며 사이클이 없는 연결 그래프이다. 처음 떠올린 풀이는 우선, 연결 요소들을 파악해서 sub graph로 나누고, 그 그래프를 트리로 만든 뒤 그래프끼리 잇는 간선을 추가하는 풀이였다. 그런데 문제를 보면 N, M이 굉장히 크다. 따라서 sub graph를 트리로 만드는 과정을 시뮬레이션 방식으로는 절대 불가능하다고 판단하고 연산 횟수만 구하면 된다는 점에 집중했다. 우리는 어떤 간선을 제거할지는 생각할 필요가 없고, 적절한 간선을 선택했다고 가정하고 제거하는 횟수만 구하면 된다. 그렇다면 그 횟수는 어떻게 구할 수 있을까? 일단, ..

20920번: 영단어 암기는 괴로워 첫째 줄에는 영어 지문에 나오는 단어의 개수 $N$과 외울 단어의 길이 기준이 되는 $M$이 공백으로 구분되어 주어진다. ($1 \leq N \leq 100\,000$, $1 \leq M \leq 10$) 둘째 줄부터 $N+1$번째 줄까지 외울 단 www.acmicpc.net 7 4 apple ant sand apple append sand sand ans : sand apple append 100,000개의 단어를 기준에 따라 정렬하면 된다. 우선 빈도를 저장해둬야 하는데 최대 O(n log n)으로 저장해야 하므로 맵에 저장을 했다. 그리고 기준에 따라 정렬을 해주면 되는데 우선순위 큐를 사용했다. 정렬 기준을 설정하는 건 항상 헷갈리는데 구조체에 () 연산자 오버..