코드트리 청약통장 완주 회고
코드트리 청약 통장 챌린지 전에 약 15문제 정도 기출을 푼 기록 제외하고 13페이지에 20문제씩이니 가끔 최적화나 다른 풀이로 같은 문제로 제출한 몇몇 문제들을 빼면 49일동안 240문제 정도 풀었다. 확실히 예전에 골드나 플레 한두문제 풀고 하는 것보다는 난이도는 낮았지만 기초를 다지고 문제를 봤을 때 아이디어만 생각나고 구현 스케치는 잡히지만 정작 구현 디테일 미스라던지 구현력이 딸렸던 상황이 해결되었다. 확실히 PS는 최대한 많이 푸는 게 답인 것 같다.
글 번호는 0번부터 시작해서 6번이긴 한데 7주동안 한번도 빠짐없이 문제를 풀고 해당 주차의 글을 남겨왔다. 날도 더워지고 해서 중간에 좀 하기 싫긴 했는데 리트코드나 프로그래머스에서 문제를 풀 때 전과는 다른 접근을 하는 나를 보고 뿌듯했고 더 열심히 해야겠다고 다짐했다. 예전에는 경험에 의거해서 이런 거였으면 이거였지가 대부분이었는데 이제는 문제 제한을 보고 계산해서 이런 걸로 접근하면 여기서 최적화할 여지가 있고 남은 시간에 그걸 구현할 수 있는지를 생각하면서 전략적으로 접근하는 사고 단계와 습관을 기를 수 있었다.
코드트리에도 기출문제가 있다. 그러나 현대와 삼성만 보이고 다른 회사 문제들은 어디 있는지 모르겠어서 다른 회사 문제들도 올려주면 좋을 것 같다. 왜냐하면 프로그래머스는 다른 사람의 풀이로 해설을 확인해야하는데 좀 검증되지 않은 느낌이고 코드트리는 질문글을 올리면 주말에도 답변이 오는 성실함이 다르다. 솔직히 그때 좀 놀랐다 토요일이었나 그랬는데 주말에도 AI 답변이 아닌 직원 답변을 받을 수 있었다.
AI 시대에 코테나 PS가 무의미하다는 관점도 많이 생겼다. 그런데 알파고가 이세돌을 바둑으로 이기고 나서 바둑이 망하지는 않았다. 국어사전이 있다고 해도 신문 뒷면의 crosswords 퍼즐을 푸는 사람이 존재한다. PS나 코테공부도 그 흐름이라고 생각한다. AI 딸깍이면 답이 나오기는 하나 그런 답을 찾아가는 과정에서의 성취감, 그리고 그걸 자신만의 풀이로 증명하고 다른 성질을 활용해서 최적화하는 쾌감같은건 AI 딸깍 따위로는 느낄 수 없는 것이다.
DSU (Disjoint Set Union, 서로소 집합 자료구조)
여러 원소를 몇 개의 집합(컴포넌트)로 관리하면서, 두 원소가 같은 집합인지 확인하고 두 집합을 합치는 연산을 빠르게 처리하는 자료구조임. find를 구현할 때 return parent[x] = find(parent[x]) 로 경로압축을 적용하면 시간복잡도는 find, union 모두 O(a(N)).
-> a(N)은 역 아커만 함수인데 거의 O(1) 수준.
문제 - 트리 완성
https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-tree-completion/description
트리 완성 설명 | 코드트리
트리 완성에서 요구하는 복합 로직과 알고리즘 구성을 분석해, 고급 코딩테스트 합격에 한 걸음 다가가세요.
www.codetree.ai
public class Main {
static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int read() throws IOException{
sst.nextToken();
return (int) sst.nval;
}
static int N, M;
static int[] parent;
static int[] size;
static int cycle=0;
static int find(int x){
if(parent[x] == x)
return x;
return parent[x] = find(parent[x]);
}
static void union(int a, int b){
int pa = find(a);
int pb = find(b);
if(pa == pb){
cycle++;
return;
}
if(size[pb] < size[pa]){
int t = pa;
pa = pb;
pb = t;
}
parent[pb] = pa;
size[pa] += size[pb];
}
public static void main(String[] args) throws IOException{
N = read();
M = read();
parent = new int[N+1];
size = new int[N+1];
for(int i = 1; i<=N; i++){
parent[i] = i;
size[i] = 1;
}
while(M-->0){
int a= read();
int b = read();
union(a,b);
}
Set<Integer> ss = new HashSet<>();
for(int i = 1; i<=N; i++){
ss.add(find(i));
}
System.out.print(ss.size()-1 + cycle);
}
}사고의 흐름 및 풀이
간선을 하나씩 추가하는 과정에서 (a,b)를 추가하려할 때 find(a) == find(b) 이면 해당 연산은 사이클을 만들게 된다.
문제에서 주어진 입력은 이미 그래프를 형성하고 있고, union 연산이 이뤄지지 않았다고 해서 간선이 연결되지 않은 경우가 아니다.
그러나, union 연산을 할 때 두 정점의 루트 노드를 검사해서 pa==pb면 연산을 진행하지 않는다.
-> 이때 끊어주는 연산 += 1
union 연산을 전부 하고 나서 모든 정점에 대해 find를 하게 되면 각 컴포넌트의 루트 노드가 구해진다.
이때, 컴포넌트끼리 연결해주어야 하므로 components-1개 연산이 필요하다.
-> 총 연산 합은 cycle + comp - 1
문제 - 최소 간선의 크기
https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-minimum-edge-size/description
최소 간선의 크기 설명 | 코드트리
최소 간선의 크기에서 요구하는 복합 로직과 알고리즘 구성을 분석해, 고급 코딩테스트 합격에 한 걸음 다가가세요.
www.codetree.ai
public class Main {
static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int read() throws IOException{
sst.nextToken();
return (int) sst.nval;
}
static int N,M,A,B;
static int[] parent;
static int[] size;
static ArrayList<int[]> li = new ArrayList<>();
static ArrayList<int[]>[] g;
static int find(int x){
if(parent[x] == x)
return x;
return parent[x] = find(parent[x]);
}
static void union(int a, int b, int w){
int pa = find(a);
int pb = find(b);
if(pa == pb)
return;
if(size[pb] < size[pa]){
int t = pa;
pa = pb;
pb = t;
}
parent[pb] = pa;
size[pa] += size[pb];
//g[a].add(new int[]{b,w});
//g[b].add(new int[]{a,w});
}
static final int INF = 1000000001;
static int ans = INF;
static void dfs(int cur, int dest, int min, int p){
if(cur == dest){
ans = min;
return;
}
for(int[] v : g[cur]){
int ni = v[0];
int nw = v[1];
if(p == ni)
continue;
int nm = Math.min(min, nw);
dfs(ni, dest, nm, cur);
}
}
public static void main(String[] args) throws IOException{
N = read();
M = read();
A = read();
B = read();
//g = new ArrayList[N+1];
parent = new int[N+1];
size = new int[N+1];
for(int i = 1; i<=N; i++){
//g[i] = new ArrayList<>();
parent[i] = i;
size[i] = 1;
}
while(M-->0)
li.add(new int[]{read(), read(), read()});
Collections.sort(li, Comparator.comparingInt(a->-a[2]));
for(int[] v : li){
int s = v[0];
int e = v[1];
int w = v[2];
union(s,e,w);
if(find(A) == find(B)){
ans = w;
break;
}
}
//dfs(A,B,INF,0);
System.out.print(ans);
}
}사고의 흐름 및 풀이
문제에서 간선마다의 만족도가 주어지고 만족도가 클수록 편안한 길이라 함. 만족도의 최솟값이 최대가 될때 만족값 출력.
그러면 A-B가 같은 컴포넌트에 있을 때까지 union을 해서 MST를 구성해 나가다가 중단한다.
트리 내부에서 특정 노드에서 노드로 가는 경로는 유일하므로 DFS를 돌리면 된다고 생각했다.
-> DFS 때문에 그래프도 구성했었는데 사실 이것도 공간 낭비다.
근데 생각을 해보면 어차피 내림차순으로 간선 정렬해서 크루스칼로 MST 구성할 건데 A-B가 같은 컴포넌트에서 연결된 순간의 간선 가중치는 해당 컴포넌트를 이루는 간선들의 집합에서 가장 작은 가중치를 갖게 되는 순간이다.
따라서 그 때의 가중치를 정답으로 저장하고 출력하면 끝
문제 - 특정한 정점과 연결하지 않기
특정한 정점과 연결하지 않기 설명 | 코드트리
특정한 정점과 연결하지 않기에서 요구하는 복합 로직과 알고리즘 구성을 분석해, 고급 코딩테스트 합격에 한 걸음 다가가세요.
www.codetree.ai
public class Main {
static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int read() throws IOException{
sst.nextToken();
return (int) sst.nval;
}
static int N,M,A,B,K;
static int[] parent;
static int[] size;
static int[] cnt;
static int find(int x){
if(parent[x] == x)
return x;
return parent[x] = find(parent[x]);
}
static void union(int a, int b){
int pa = find(a);
int pb = find(b);
if(pa == pb)
return;
if(size[pb] < size[pa]){
int t = pa;
pa = pb;
pb = t;
}
parent[pb] = pa;
size[pa] += size[pb];
}
public static void main(String[] args) throws IOException{
N = read();
M = read();
parent = new int[N+1];
size = new int[N+1];
cnt = new int[N+1];
for(int i = 1; i<=N; i++){
parent[i] = i;
size[i] = 1;
}
while(M-->0){
union(read(), read());
}
A = find(read());
B = find(read());
K = read();
// 루트노드마다 얼마나 연결되어있는지 갯수셈
for(int i = 1; i<=N; i++){
int cur = find(i);
if(cur == B)
continue;
cnt[cur]++;
}
// 최소힙
PriorityQueue<Integer> pq = new PriorityQueue<>();
for(int i= 1; i<=N; i++){
// A가 루트노드인건 이미 연결되어있으므로 ans 초기값으로 설정
// B가 루트노드인건 넣으면 안됨
if(i == A || i == B || cnt[i] == 0)
continue;
if(pq.size() < K)
pq.add(cnt[i]);
else if(K > 0 && cnt[i] > pq.peek()){
pq.poll();
pq.add(cnt[i]);
}
}
int ans = cnt[A];
while(!pq.isEmpty()){
ans += pq.poll();
}
System.out.print(ans);
}
}사고의 흐름
N개의 정점과 M개의 간선으로 이루어진 그래프가 있을 때, 추가로 최대 K개의 간선을 놓아서 정점 A가 최대한 많은 정점과 연결되게 하고 싶은데 이 때, 정점 B와 연결되면 안될 때 A를 포함해서 A와 연결된 정점의 갯수를 출력하는 문제이다.
루트 노드끼리 간선을 하나 추가하면 전체 서브트리를 연결할 수 있으니 그걸 생각해서 풀면 된다.
풀이
일단 간선 정보에 대해 union 연산을 해 주고, A와 B를 find 연산으로 루트노드로 미리 구해둔다.
-> 왜냐하면 union 연산 결과도 루트노드 기준으로 component 단위이기 때문
각 루트노드마다 서브트리 노드 갯수가 몇 개인지 구해서 저장하는 cnt 배열을 구한다.
그리고 A를 포함한 연결 정점 갯수를 구하는 거니까 ans의 초기값을 cnt[ A ] 로 해 준다. ( A는 이미 find(A) )
최소힙을 사용해 최대 K개의 연결을 시도할 수 있으므로 힙의 크기를 K 이하로 유지한다.
컴포넌트 갯수를 C라 하면
-> 처음에는 최대 힙으로 풀었는데 최대 힙은 C log C의 시복을 가지고 최소 힙은 C log K의 시복을 가진다.
-> 최대 힙 : i가 A, B 가 아닐 때 전부 넣고 K개만큼 뽑게 된다. 구현이 최소 힙보다 간단하다.
1) 힙 크기가 K 미만일때는 cnt [ i ] 를 삽입한다.
2) K가 0 이상이고 힙에서 현재까지 선택된 K개의 컴포넌트중 가장 작은 컴포넌트보다 현재 컴포넌트 ( cnt [ i ] ) 가 더 크다면,
더 좋은 선택이므로 poll 해준 뒤 cnt [ i ] 를 삽입해서 교체한다.
-> 힙의 크기가 K이하로 유지되므로 힙이 빌 때까지 뽑아서 누적해주면 답
문제 - 가장 많은 정점과 연결
가장 많은 정점과 연결 설명 | 코드트리
가장 많은 정점과 연결에서 요구하는 복합 로직과 알고리즘 구성을 분석해, 고급 코딩테스트 합격에 한 걸음 다가가세요.
www.codetree.ai
public class Main {
static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int read() throws IOException{
sst.nextToken();
return (int) sst.nval;
}
static int N,M,K;
static int[] cost;
static int[] parent;
static final int INF = 100000001;
static int find(int x){
if(parent[x] == x)
return x;
return parent[x] = find(parent[x]);
}
static void union(int a, int b){
int pa = find(a);
int pb = find(b);
if(pa == pb)
return;
if(cost[pb] < cost[pa]){
int t = pa;
pa = pb;
pb = t;
}
parent[pb] = pa;
}
public static void main(String[] args) throws IOException{
N = read();
M = read();
K = read();
parent = new int[N+1];
cost = new int[N+1];
for(int i = 1; i<=N; i++){
cost[i] = read();
parent[i] = i;
}
while(M-->0){
union(read(), read());
}
ArrayList<Integer> s = new ArrayList<>();
boolean[] v = new boolean[N+1];
for(int i = 1; i<=N; i++){
int pi = find(i);
if(v[pi])
continue;
v[pi] = true;
s.add(pi);
}
/*
10 10 20 30 40
10+10
10+20
10+30
10+40
-> sum + (N-2) * min
제일 작은걸 중앙으로 잡고 연결함
*/
long sum = 0;
int min = INF;
for(int n : s){
sum += cost[n];
min = Math.min(min, cost[n]);
}
long ans = s.size() == 1 ? 0 : sum + (long)(s.size()-2)*min;
System.out.print(ans > K ? "NO" : ans);
}
}사고의 흐름 및 풀이
N개의 정점이 M개의 간선으로 연결되어있는 그래프가 주어진다.
cost 배열은 cost[i] , cost [j] 가 주어질 때 정점 i와 j를 연결하는 비용은 cost [i] + cost [j] 이다.
-> union 내부 구현에서 부모 정점을 정할 때 pa와 pb 중 cost가 작은 쪽으로 해야 비용이 최소가 될 것이다.
그리고 모든 간선에 대해서 union을 마친 뒤 Set을 사용해서 모든 정점에 대해 find()의 결과를 넣는 대신,
boolean 배열을 사용해서 이미 구한 루트 노드는 스킵하는 식으로 현재 컴포넌트들의 루트 노드를 모은 리스트 s를 구한다.
그걸 다 떨어진 정점으로 보고 연결한다고 하면
그중 가장 cost가 작은 정점을 중앙 지점(hub)으로 두고 나머지 정점을 연결한다.
-> 어떤 트리의 루트 노드라고 하고 나머지 정점들의 cost를 더하면 전체 cost가 나온다.
-> 이를 일반화하면 Set에서의 cost 값을 전부 더한 뒤, sum 값을 구할때 순회를 하기 때문에 이때 minCost를 갱신해주고,
set.size - 2 * minCost 를 sum에 더해주면 문제 조건에 맞게 정점을 전부 연결할 때의 cost를 구할 수 있다.
문제 - 칸에 입력되는 정수(백준 공항)
https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-integer-in-the-cell/description
칸에 입력되는 정수 설명 | 코드트리
칸에 입력되는 정수에서 요구하는 복합 로직과 알고리즘 구성을 분석해, 고급 코딩테스트 합격에 한 걸음 다가가세요.
www.codetree.ai
public class Main {
static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int read() throws IOException{
sst.nextToken();
return (int) sst.nval;
}
static int N,M;
static int[] parent;
static int find(int x){
if(parent[x] == x)
return x;
return parent[x] = find(parent[x]);
}
public static void main(String[] args) throws IOException{
N = read();
parent = new int[N+1];
for(int i= 0; i<=N; i++)
parent[i] = i;
M = read();
int ans = 0;
while(M-->0){
int cur = read();
int pc = find(cur);
if(pc == 0)
break;
else{
parent[pc] = find(pc-1);
ans++;
}
}
System.out.print(ans);
}
}사고의 흐름 및 풀이
M개의 숫자가 주어지는데 각 숫자 이하의 칸에 그 숫자를 삽입할 수 있음. 최대한 많이 넣으려면 제한의 최대한 끝에 넣어야 함.
숫자가 선택되면 어떤 구간이 선택되는건데 그 구간에서 다음에 넣을 자리를 find를 통해 추적함
parent [x] = x 이하에서 현재 공을 삽입할 수 있는 최대 인덱스 로 정의하면
find(x)는 그걸 찾아주는 역할을 하고 이를 pc라 하자. 그러면 parent[pc] = pc-1이 된다.
-> 뒤에서부터 넣어야 최적이고 다음 인덱스를 저장하니까 -1
-> 만약 find 값이 0이라면 더이상 넣을 곳이 없으므로 종료함.
경로 압축을 사용하는 DSU를 통해 각 공에 대해 거의 O(1)에 다음 배치 위치를 찾을 수 있으므로
전체 시간복잡도는 O(M a(N)) 임
문제 - 홍팀과 백팀(이분그래프 판별)
홍팀과 백팀 설명 | 코드트리
홍팀과 백팀에서 요구하는 복합 로직과 알고리즘 구성을 분석해, 고급 코딩테스트 합격에 한 걸음 다가가세요.
www.codetree.ai
public class Main {
static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int read() throws IOException{
sst.nextToken();
return (int) sst.nval;
}
static int N,M;
static ArrayList<Integer>[] g;
static int[] color;
static boolean bfs(int s){
Queue<Integer> q = new ArrayDeque<>();
color[s] = 0;
q.add(s);
while(!q.isEmpty()){
int ci = q.poll();
for(int ni : g[ci]){
if(color[ni] == -1){
color[ni] = 1 - color[ci];
q.add(ni);
}
else if(color[ni] == color[ci])
return false;
}
}
return true;
}
public static void main(String[] args) throws IOException{
N = read();
M = read();
color = new int[N+1];
Arrays.fill(color, -1);
g = new ArrayList[N+1];
for(int i = 1; i<=N; i++)
g[i] = new ArrayList<>();
for(int i = 0; i<M; i++){
int u = read();
int v = read();
g[u].add(v);
g[v].add(u);
}
// 모든 컴포넌트 검사해야 함.
for(int i = 1; i<=N; i++){
if(color[i] != -1)
continue;
if(!bfs(i)){
System.out.print(0);
return;
}
}
System.out.print(1);
}
}사고의 흐름 및 풀이
DSU 파트긴 한데 그쪽으로는 생각이 잘 안나서 BFS로 color 배열을 사용해서 풀었다.
먼저 모든 정점에 대해 색과 칠해지지 않음 상태를 저장하는 color 배열을 정의한다.
-> -1 : 색칠안됨, 0 : 홍팀, 1 : 백팀
그리고 a,b 간선 입력에 대해 무방향으로 정보를 저장해서 그래프를 만든다.
BFS를 사용해서 아직 색칠되지 않은 정점이 발견되면 거기서부터 연결된 정점들을 순회한다.
-> 그래야 분리된 컴포넌트들도 검사할 수 있다.
처음 등장하는 정점을 루트라고 잡고 거기서부터 색이 칠해지지 않은 정점에 대해 1-color[cur] 로 칠해준다.
만약 다음 정점에 이미 색칠이 되어있고 현재 색과 같은 색이면 모순이 발생한 것이므로 false를 리턴하고 끝낸다.
문제 - 칸합치기 2 (2개의 DSU) (다시 풀기)
https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-can/description
칸 합치기 2 설명 | 코드트리
칸 합치기 2에서 요구하는 복합 로직과 알고리즘 구성을 분석해, 고급 코딩테스트 합격에 한 걸음 다가가세요.
www.codetree.ai
public class Main {
static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int read() throws IOException{
sst.nextToken();
return (int) sst.nval;
}
static int find(int x){
if(parent[x] == x)
return x;
return parent[x] = find(parent[x]);
}
static void union(int a, int b){
int pa = find(a);
int pb = find(b);
if(pa == pb)
return;
if(size[pb] < size[pa]){
int t = pa;
pa = pb;
pb = t;
}
parent[pb] = pa;
size[pa] += size[pb];
// 두개가 합쳐져서 1개됬으니 전체 컴포넌트수 -1
cnt--;
}
static int findNext(int x){
if(next[x] == x)
return x;
return next[x] = findNext(next[x]);
}
static int N,M;
static int[] parent;
static int[] next;
static int[] size;
static int cnt;
public static void main(String[] args) throws IOException{
N = read();
M = read();
parent = new int[N+1];
next = new int[N+1];
size = new int[N+1];
for(int i = 1; i<=N; i++){
parent[i] = i;
next[i] = i;
size[i] = 1;
}
/*
next에 i를 볼때 처리해야할 다음 위치를 저장
[next[pa], b]
*/
cnt = N;
StringBuilder sb = new StringBuilder();
while(M-->0){
int a = read();
int b = read();
int na = findNext(a);
while(na < b){
union(na, na+1);
next[na] = findNext(na+1);
na = findNext(na);
}
sb.append(cnt).append("\n");
}
System.out.print(sb);
}
}사고의 흐름 및 풀이
A, B가 주어지면 두개만 union 하는게 아니라 그 안에 있는 모든 요소를 union 시켜야 한다.
근데 문제 말대로 모든 인접한 정점에 대해 유니온하게 되면 최악의 경우 O(MN)이 되어서 10만 * 10만이라 TLE난다.
따라서 직접 시뮬레이션할 수 없으니 구간을 대표하는 값이나 포인터를 저장하고 해당 인덱스에 접근하면 포인터로 다음에 처리할 시작지점부터 처리하면 될 것 같다.
-> Successor DSU
유니온 자체는 서브트리 크기로 밸런싱을 하는 걸로 잡았고, 연결 요소의 갯수는 N에서 시작해서
한번 유니온되면 2개가 1개로 줄었으니 이는 -=1이 된다.
next [ i ] = i 에서 union을 시행해야 할 때 다음으로 처리해야하는 경계 위치 라고 정의하자.
na를 현재 제거하는 경계라고 할 때,
findNext에서 경로압축을 활용해서 구현하고 next[na] = findNext(na+1) 로 갱신한다.
이후 다음 처리 위치는 findNext(na).
이렇게 b가 될 때까지 반복하면 중복연산을 최대한 줄여서 점프하며 union 연산을 마칠 수 있다.
정답 조건은 연산이 한번 이루어질 때마다 정점 종류 갯수를 출력하는 것이므로 b까지 union 한 뒤 cnt 모아서 출력
각 경계는 최대 한번만 처리되므로 총 시간복잡도는 O((N+M) a(N))
문제 - MST 4 (크루스칼) (템플릿)
최소 스패닝 트리 4 설명 | 코드트리
최소 스패닝 트리 4에서 요구하는 복합 로직과 알고리즘 구성을 분석해, 고급 코딩테스트 합격에 한 걸음 다가가세요.
www.codetree.ai
public class Main {
static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int read() throws IOException{
sst.nextToken();
return (int) sst.nval;
}
static char rc() throws IOException{
sst.nextToken();
return sst.sval.charAt(0);
}
static int N,M;
static int[] parent;
static boolean[] color;
static int sum = 0;
static int cnt = 0;
static int find(int x){
if(parent[x] == x)
return x;
return parent[x] = find(parent[x]);
}
static void union(int a, int b, int w){
int pa = find(a);
int pb = find(b);
if(pa == pb)
return;
parent[pb] = pa;
sum += w;
cnt++;
}
public static void main(String[] args) throws IOException{
N = read();
M = read();
color = new boolean[N+1];
parent = new int[N+1];
for(int i= 1; i<=N; i++){
parent[i] = i;
if(rc() == 'a')
color[i] = true;
}
ArrayList<int[]> li = new ArrayList<>();
while(M-->0){
int a = read();
int b = read();
int w = read();
if(color[a] != color[b])
li.add(new int[]{a,b,w});
}
Collections.sort(li, (a,b)->{
return a[2] - b[2];
});
for(int[] l : li){
if(cnt == N-1)
break;
int u = l[0];
int v = l[1];
int w = l[2];
union(u,v,w);
}
System.out.print(cnt == N-1 ? sum : -1);
}
}크루스칼 구현 팁
MST의 간선 갯수는 총 정점 수 -1개 이므로 union이 성공할 때 cnt++해서 마지막에 검사한다.
그리고 union에서 미리 cnt를 검사해서 현재 MST를 구성하는 간선 수가 N-1이면 나머지는 볼 필요 없기 때문에 일찍 탈출한다.
문제 - 최소 거리 잇기(백준 1774)
https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-minimum-distance/description
최소 거리 잇기 설명 | 코드트리
최소 거리 잇기에서 요구하는 복합 로직과 알고리즘 구성을 분석해, 고급 코딩테스트 합격에 한 걸음 다가가세요.
www.codetree.ai
public class Main {
static class Info implements Comparable<Info>{
int x;
int y;
long w;
Info(int x, int y, long w){
this.x = x;
this.y = y;
this.w = w;
}
@Override
public int compareTo(Info o){
return Long.compare(this.w, o.w);
}
}
static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int read() throws IOException{
sst.nextToken();
return (int) sst.nval;
}
static int N,M;
static int[][] pos;
static int[] parent;
static int cnt = 0;
static double sum = 0;
static long getDist(int x1, int y1, int x2, int y2){
long a = (long) (x2-x1) * (x2-x1);
long b = (long) (y2-y1) * (y2-y1);
return a+b;
}
static int find(int x){
if(parent[x] == x)
return x;
return parent[x] = find(parent[x]);
}
static void union(Info in){
int a = in.x;
int b = in.y;
long w = in.w;
int pa = find(a);
int pb = find(b);
if(pa == pb)
return;
sum += Math.sqrt(w);
parent[pb] = pa;
cnt++;
}
// static long posToKey(int a, int b){
// if(b < a){
// int t = a;
// a = b;
// b = t;
// }
// return (((long)a<<32) | b);
// }
public static void main(String[] args) throws IOException{
N = read();
M = read();
pos = new int[N+1][2];
parent = new int[N+1];
for(int i = 1; i<=N; i++){
pos[i][0] = read();
pos[i][1] = read();
parent[i] = i;
}
// Set<Long> ss = new HashSet<>();
while(M-->0){
int a = read();
int b = read();
// ss.add(posToKey(a,b));
int pa = find(a);
int pb = find(b);
if(pa != pb){
parent[pb] = pa;
cnt++;
}
}
ArrayList<Info> li = new ArrayList<>();
for(int i = 1; i<=N; i++){
for(int j = i+1; j<=N; j++){
li.add(new Info(i,j,getDist(pos[i][0],pos[i][1],pos[j][0],pos[j][1])));
}
}
Collections.sort(li);
for(Info ll : li){
if(cnt == N-1)
break;
union(ll);
}
System.out.printf("%.2f", sum);
}
}사고의 흐름 및 풀이
1에서 1_000_000까지의 값을 갖는 x,y 좌표평면 위에서의 좌표들이 N개 주어지고 이미 연결되어있는 M개의 간선이 주어진다.
모든 정점을 최소의 거리로 연결하기 위해 간선을 연결할 때, 그때의 간선 추가 비용의 최소 합을 구하는 문제이다.
처음에는 미리 연결된 간선을 flag를 시켜놓고 좌표평면을 하나의 key로 나타내기 위해서 long으로 만들어서 탐지할까 싶었다.
-> 사실 기존 연결된 간선을 따로 관리할 필요가 없는 문제다.
더 설명하자면, 추가로 발생하는 비용을 구하는 문제이기 때문에
미리 연결된 그래프들을 union 연산을 해주는 대신 추가 비용을 누적하는 double형 sum에서 0으로 누적시킨다.
-> 이러면 이 간선이 MST에 기여하는 간선이든 아니든 간에 추가 비용에는 영향이 없으며 나중에 모든 정점에 대해 거리를 계산해서 간선 리스트로 만들더라도 따로 이 조건을 고려하지 않아도 된다.
또한, 거리 계산할때 double 오차 오류때문에 제곱을 유지한 채로 계산하려 했는데 이대로 누적시키게 되면
이상한 결과값이 나오기 때문에 sum을 해 줄 때 반드시 sqrt(cost) 를 해줘야 한다.
-> 정렬할 때는 long 타입으로 하는게 편해서 정렬할 때만 그렇게 해 준 것.
1) 주어진 좌표평면에 대해 모든 좌표쌍에 대한 간선 정보 list 만듬
2) 미리 연결된 간선에 대해 union 연산을 진행하되, sum에는 더해주지 않으나 union이 성공하면 cnt 수는 증가시킴.
3) list를 override 한 compareTo로 오름차순 정렬함.
4) list를 순회하며 union 연산을 진행하고 MST의 총 간선 수인 cnt가 N-1가 되면 break함
5) sum 출력
시간 복잡도 계산
| 간선 생성 | O(N^2) |
| 정렬 | O(ElogE) with E = N*(N-1) / 2 |
| Union-Find | 거의 O(Eα(N)) |
-> 총 시간 복잡도 : O(N^2 log N)
문제 - 3차원 평면의 점(좌표 축 정렬)
3차원 평면 위의 점 설명 | 코드트리
3차원 평면 위의 점에서 요구하는 복합 로직과 알고리즘 구성을 분석해, 고급 코딩테스트 합격에 한 걸음 다가가세요.
www.codetree.ai
public class Main {
static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int read() throws IOException{
sst.nextToken();
return (int) sst.nval;
}
static int N;
static int[][] pos;
static int[] parent;
static int cnt = 0;
static long sum = 0;
static final int INF = 2_000_000_000+1;
static int find(int x){
if(parent[x] == x)
return x;
return parent[x] = find(parent[x]);
}
static void union(int a, int b, int w){
int pa = find(a);
int pb = find(b);
if(pa == pb)
return;
parent[pb] = pa;
sum += w;
cnt++;
}
static int getDist(int[] p1, int[] p2){
int min = INF;
for(int i = 0; i<3; i++){
min = Math.min(min, Math.abs(p1[i] - p2[i]));
}
return min;
}
public static void main(String[] args) throws IOException{
N = read();
// pos가 0~N이라 0,0,0,0이 계속 정렬에 섞이는 문제있음
pos = new int[N][4];
parent = new int[N+1];
for(int i = 0; i<N; i++){
parent[i+1] = i+1;
pos[i] = new int[]{i+1,read(), read(), read()};
}
// a,b,w
ArrayList<int[]> li = new ArrayList<>();
// x
Arrays.sort(pos, (a, b) -> a[1] - b[1]);
for(int i = 0; i < N-1; i++){
li.add(new int[]{
pos[i][0],
pos[i + 1][0],
Math.abs(pos[i][1] - pos[i + 1][1])
});
}
// y
Arrays.sort(pos, (a, b) -> a[2] - b[2]);
for(int i = 0; i < N-1; i++){
li.add(new int[]{
pos[i][0],
pos[i + 1][0],
Math.abs(pos[i][2] - pos[i + 1][2])
});
}
// z
Arrays.sort(pos, (a, b) -> a[3] - b[3]);
for(int i = 0; i < N-1; i++){
li.add(new int[]{
pos[i][0],
pos[i + 1][0],
Math.abs(pos[i][3] - pos[i + 1][3])
});
}
// li를 x,y,z 정렬한걸로 간선 생성했으니까 전체 크루스칼용으로 정렬
Collections.sort(li, (a,b)->{
return Integer.compare(a[2], b[2]);
});
for(int[] ll : li){
union(ll[0], ll[1], ll[2]);
if(cnt == N-1){
break;
}
}
System.out.print(sum);
}
}사고의 흐름 및 풀이
3차원 축으로 10만개의 점이 있는데 이걸 전부 한 쌍으로 묶게 되면 터진다.
대신, 3차원 좌표를 입력을 받고 각 좌표축을 기준을 pos를 오름차순 정렬하게 되면 최대한 가중치를 적게 해서 연결하려면
가까운 점으로 간선 정보를 생성하면 되니까 총 3 * (N-1)개의 간선 정보가 만들어진다.
만들어진 간선 정보를 가중치 오름차순으로 정렬하고 크루스칼로 연결해서 가중치 합을 출력하면 끝
문제 - 화성 탐사 (BFS, DSU)
https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-explore-mars/description
화성 탐사 설명 | 코드트리
화성 탐사에서 요구하는 복합 로직과 알고리즘 구성을 분석해, 고급 코딩테스트 합격에 한 걸음 다가가세요.
www.codetree.ai
public class Main {
static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int read() throws IOException{
sst.nextToken();
return (int) sst.nval;
}
static int N;
static int M = 1;
static int[][] board;
static int[][] id;
static int[] di = {-1,0,1,0};
static int[] dj = {0,1,0,-1};
static ArrayList<int[]> li = new ArrayList<>();
static Map<Integer, int[]> m = new HashMap<>();
static final int INF = 50 * 50 + 1;
static void bfs(int s){
int si = m.get(s)[0];
int sj = m.get(s)[1];
boolean[][] v = new boolean[N][N];
v[si][sj] = true;
Queue<int[]> q = new ArrayDeque<>();
q.add(new int[]{si,sj,0});
while(!q.isEmpty()){
int[] cur = q.poll();
int ci= cur[0];
int cj = cur[1];
int cd = cur[2];
if(id[ci][cj] != 0 && id[ci][cj] > s){
li.add(new int[]{s, id[ci][cj], cd});
}
for(int d= 0; d<4;d++){
int ni = ci + di[d];
int nj = cj + dj[d];
if(ni < 0 || nj < 0 || ni >= N || nj >= N)
continue;
if(board[ni][nj] == -1)
continue;
if(v[ni][nj])
continue;
v[ni][nj] = true;
q.add(new int[]{ni,nj,cd+1});
}
}
}
static int sum = 0;
static int cnt = 0;
static int[] parent;
static int find(int x){
if(parent[x] == x)
return x;
return parent[x] = find(parent[x]);
}
static void union(int a, int b, int w){
int pa = find(a);
int pb = find(b);
if(pa == pb)
return;
parent[pb] = pa;
sum += w;
cnt++;
}
public static void main(String[] args) throws IOException{
N = read();
board = new int[N][N];
// map 대신 사용
id = new int[N][N];
for(int i = 0; i<N; i++){
for(int j = 0; j<N; j++){
board[i][j] = read();
if(board[i][j] == 1 || board[i][j] == 2){
id[i][j] = M;
m.put(M++, new int[]{i,j});
}
}
}
for(int p =1; p<M; p++){
bfs(p);
}
parent = new int[M];
for(int i = 1; i<M; i++)
parent[i] = i;
Collections.sort(li, Comparator.comparingInt(a->a[2]));
for(int[] ll : li){
union(ll[0], ll[1], ll[2]);
// 0~M-1 까지밖에 없어서
if(cnt == M-2)
break;
}
int prev = find(1);
for(int p = 2; p<M; p++){
if(prev != find(p)){
System.out.print(-1);
return;
}
}
System.out.print(sum);
}
}사고의 흐름
처음에는 longToInteger, IntegerToIJ 등을 생각하면서 map하나로 좌표값 <-> 정점 인덱스를 변환하는걸 생각했는데 구현 시간이 오래 걸려서 그냥 공간 제약이 작아서 N*N의 2차원 배열 id를 선언해서 정점 인덱스를 저장하기로 했다.
->기지의 위치를 매핑하는 id 2차원 배열이 필요하고 기지 번호 i가 가리키는 i,j 값을 저장하는 map이 필요하다.
그리고 제약이 작기 때문에 전체 경로를 다 구해서 했는데 현재 활성화된 정점들에서 시작해서 모든 정점에 대해서 거리를 구하고
그걸 PriorityQueue에 넣어서 peek해서 정점 하나를 리턴하는 식으로 해도 될 것 같긴하다.
-> 생각해보니 이건 Prim임
풀이
1) board 값을 입력받아서 1,2일 때 id[i][j] 에 인덱스 번호를 증가시키면서 저장하고
정점 번호로 좌표값을 저장하는 map에 인덱스, { i,j } 형태로 저장함
2) 정점 번호는 [1, M-1] 로 저장되므로 그것에 대해 bfs를 해서 거리를 겹치지 않게 구함
-> 여기서 si,sj가 아니면서 start 인덱스보다 큰 id 값을 가지는 좌표값에 대해서만 간선 정보 리스트에 저장
3) 간선 정보 리스트를 cost 오름차순으로 정렬하고 정점 갯수는 M-1이므로
cnt == M-2로 탈출 조건을 설정해서 union
4) 마지막에 모든 정점 [1, M-1] 에 대해서 find를 호출해서
루트 정점의 종류가 1개인지 검증하고 맞다면 sum 아니라면 -1 출력
문제 - Prim 템플릿
https://www.codetree.ai/ko/trails/complete/curated-cards/intro-minimum-spanning-tree-8/description
최소 스패닝 트리 8 설명 | 코드트리
최소 스패닝 트리 8에서 요구하는 복합 로직과 알고리즘 구성을 분석해, 고급 코딩테스트 합격에 한 걸음 다가가세요.
www.codetree.ai
public class Main {
static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int read() throws IOException{
sst.nextToken();
return (int) sst.nval;
}
static int N,M;
static ArrayList<int[]>[] g;
static boolean[] v;
static long prim(int s){
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a->a[1]));
pq.add(new int[]{s,0});
long sum = 0;
while(!pq.isEmpty()){
int[] cur = pq.poll();
int ci = cur[0];
int cd = cur[1];
if(v[ci])
continue;
v[ci] = true;
sum += cd;
for(int[] n : g[ci]){
pq.add(n);
}
}
return sum;
}
public static void main(String[] args) throws IOException{
N = read();
M = read();
g = new ArrayList[N+1];
v = new boolean[N+1];
for(int i = 1; i<=N; i++){
g[i] = new ArrayList<>();
}
while(M-->0){
int a = read();
int b = read();
int w = read();
g[a].add(new int[]{b,w});
g[b].add(new int[]{a,w});
}
long ans = 0;
for(int i=1;i<=N;i++){
if(!v[i])
ans += prim(i);
}
System.out.print(ans);
}
}정리
Prim 알고리즘은 MST(최소 신장 트리)를 구해야 할 때, 모든 간선을 한번에 생성해서 관리하기 어렵다면 현재 활성화되어있는 정점들에 대해 나가는 간선을 PriorityQueue에 넣는다. 일반적으로 간선 가중치가 가장 적은 후보를 poll 해서 우선순위 큐가 빌 때까지 아직 방문하지 않은 정점에 대해 간선을 연결하는 알고리즘이다.
코드 자체는 연결 그래프가 아닐 때를 고려해서 MSF로 안전하게 구하는 식으로 구현했다.
문제 - 물체 놓기 (가상 정점)
https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-place-object/description
물체 놓기 설명 | 코드트리
물체 놓기에서 요구하는 복합 로직과 알고리즘 구성을 분석해, 고급 코딩테스트 합격에 한 걸음 다가가세요.
www.codetree.ai
public class Main {
static StreamTokenizer sst =
new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int read() throws IOException {
sst.nextToken();
return (int) sst.nval;
}
static int N;
static int[][] cost;
static long prim() {
boolean[] v = new boolean[N + 1];
int[] minEdge = new int[N + 1];
Arrays.fill(minEdge, Integer.MAX_VALUE);
minEdge[0] = 0;
long sum = 0;
for (int cnt = 0; cnt <= N; cnt++) {
int cur = -1;
// 아직 방문하지 않은 정점 중 가장 싼 정점 선택
for (int i = 0; i <= N; i++) {
if (!v[i] && (cur == -1 || minEdge[i] < minEdge[cur]))
cur = i;
}
v[cur] = true;
sum += minEdge[cur];
// 비용 갱신
for (int next = 0; next <= N; next++) {
if (!v[next])
minEdge[next] = Math.min(minEdge[next], cost[cur][next]);
}
}
return sum;
}
public static void main(String[] args) throws Exception {
N = read();
cost = new int[N + 1][N + 1];
// 가상 정점 0 -> i
for (int i = 1; i <= N; i++) {
int c = read();
cost[0][i] = c;
cost[i][0] = c;
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
cost[i][j] = read();
}
}
System.out.print(prim());
}
}사고의 흐름 및 풀이
처음 문제를 읽었을 때 i -> j 방향의 cost가 2차원 배열에서 주어진다 했으니 cost[i][j] != cost[j][i]로 생각하고 최소 아보레센스로 접근하려 했다. 이는 사이클이 생겼을 때 부모 정점으로 압축하는 방식으로 방향성 MST를 구하기 위해 Chu-liu/Edmonds를 적용하는 것인데 대체 Prim 챕터의 easy 문제에서 이게 나올 이유가 뭔가 싶었다. 아마도 prim을 전제하고 있으니 무방향으로 생각한다.
각 물체를 직접 놓는 비용과 간선을 연결하는 비용이 따로 있다. 이미 물체가 존재하는 정점 (활성화된 정점)에서 간선을 연결하면 도착 정점에는 물체가 무료로 생기므로 물체를 직접 놓는 비용을 최소화하면 될 것 같았다.
처음에는 가장 물체 놓는 비용이 적은 정점 하나만을 놓고 hub 방식으로 이어나가는 것을 생각했는데 반례가 있었다.
여러 물체를 직접 놓고 이어나가는 방식이 더 싼 경우이다.
-> 가상 정점 0을 두고 물체를 직접 놓는 cost를 간선 가중치 cost로 통합한 뒤, N+1 * N+1 2차원 cost 배열을 생성해서 배열 기반 Prim으로 풀이했다.
문제 - 도시 연결하기 (라벨링, 가중치 배열 만들기)
https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-connecting-cities/description
도시 연결하기 설명 | 코드트리
도시 연결하기에서 요구하는 복합 로직과 알고리즘 구성을 분석해, 고급 코딩테스트 합격에 한 걸음 다가가세요.
www.codetree.ai
public class Main {
static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int read() throws IOException{
sst.nextToken();
return (int) sst.nval;
}
static int N,M,K;
static int id = 1;
static int[][] idBoard;
static int[][] board;
static ArrayList<int[]>[] g;
static int[] di = {-1,0,1,0};
static int[] dj = {0,1,0,-1};
static int[][] cost;
static long prim(){
boolean[] v = new boolean[K];
int[] dist = new int[K];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[1] = 0;
long sum = 0;
for(int t = 1; t<K; t++){
int cur = -1;
for(int i =1 ;i<K; i++){
if(v[i])
continue;
if(cur == -1 || dist[i] <dist[cur])
cur = i;
}
if(cur == -1 || dist[cur] == Integer.MAX_VALUE)
return -1;
v[cur] = true;
sum += dist[cur];
for(int n = 1; n<K; n++){
if(v[n])
continue;
if(cost[cur][n] < dist[n]){
dist[n] = cost[cur][n];
}
}
}
return sum;
}
public static void main(String[] args) throws IOException{
N = read();
M = read();
idBoard = new int[N][M];
for(int i = 0; i<N; i++)
Arrays.fill(idBoard[i], -1);
board = new int[N][M];
for(int i = 0; i<N; i++){
for(int j = 0; j<M; j++){
board[i][j] = read();
}
}
// 1) id 라벨링
for(int i = 0; i<N; i++){
for(int j = 0; j<M; j++){
if(idBoard[i][j] == -1 && board[i][j] == 1){
idBoard[i][j] = id;
Queue<int[]> q = new ArrayDeque<>();
q.add(new int[]{i,j});
while(!q.isEmpty()){
int[] cur = q.poll();
int ci = cur[0];
int cj = cur[1];
for(int d = 0; d<4; d++){
int ni = ci + di[d];
int nj = cj + dj[d];
if(ni < 0 || nj < 0 || ni >= N || nj >= M)
continue;
if(board[ni][nj] == 1 && idBoard[ni][nj] == -1){
idBoard[ni][nj] = id;
q.add(new int[]{ni,nj});
}
}
}
id++;
}
}
}
K = id;
g = new ArrayList[K];
for(int i = 1; i<K; i++)
g[i] = new ArrayList<>();
// 각 ID 땅마다 시작 지점 모아놓는 리스트배열
ArrayList<int[]>[] ss = new ArrayList[K];
for(int i = 1; i<K; i++)
ss[i] = new ArrayList<>();
for(int i = 0; i<N; i++){
for(int j= 0; j<M; j++){
if(idBoard[i][j] == -1)
continue;
ss[idBoard[i][j]].add(new int[]{i,j});
}
}
// 각 땅으로 이어지는 간선 가중치 구하기
// 1->2에 여러 값 들어갈 수 있음.
// 직선만 가능해서 bfs하면 안됨
// g에는 i->j min 값만 저장하기
cost = new int[K][K];
for(int i= 1; i<K; i++){
for(int j = 1; j<K; j++){
cost[i][j] = Integer.MAX_VALUE;
}
}
for(int i=1; i<K; i++){
for(int[] s : ss[i]){
int ci = s[0];
int cj = s[1];
// 직선으로 찾음
for(int d = 0;d<4; d++){
int l = 1;
while(true){
int ni = ci + l*di[d];
int nj = cj + l*dj[d];
// 범위 밖 나가면 멈춰야함
if(ni < 0 || nj < 0 || ni >= N || nj >= M)
break;
// 자기자신 만나도 멈추고
if(idBoard[ni][nj] == i)
break;
// 다른땅 만나도 갱신하고 멈춰야함
if(board[ni][nj] == 1 && idBoard[ni][nj] != i){
int nid = idBoard[ni][nj];
cost[i][nid] = Math.min(cost[i][nid], l-1);
cost[nid][i] = cost[i][nid];
break;
}
l++;
}
}
}
}
System.out.print(prim());
}
}사고의 흐름 및 풀이
입력으로 0은 바다 1은 땅인 지도가 주어지고 그걸 보면서 ID 라벨링을 먼저 수행하고 각 ID 마다 시작지점을 경계만 넣던지 땅을 전부 넣던지 해서 시작지점 리스트를 각 ID마다 저장한다.
그리고 직선으로만 다리 놓기가 가능하므로 4방향으로 보면서
1) 같은 땅을 만나면 종료 2) 경계 밖으로 나가면 종료 3) 다른 땅을 만나면 최소 거리로 i -> j 값을 갱신 을 수행한다.
사실 다른 땅을 만났을 때 그냥 인접 리스트 그래프로 만들어도 되긴 하는데
이러면 중복 간선이 너무 많아서 비효율적이기 때문에
배열 Prim을 위해서 cost [ id 개수 ] [ id 개수 ] 2차원 배열로 저장했다.
문제 - 트리 복원하기 (그래프 이론)
https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-restore-tree/description
트리 복원하기 설명 | 코드트리
트리 복원하기에서 요구하는 복합 로직과 알고리즘 구성을 분석해, 고급 코딩테스트 합격에 한 걸음 다가가세요.
www.codetree.ai
public class Main {
static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int read() throws IOException{
sst.nextToken();
return (int) sst.nval;
}
static int N;
static int[][] dist;
public static void main(String[] args) throws IOException{
N = read();
dist = new int[N+1][N+1];
for(int i = 1; i<=N; i++){
for(int j = 1; j<=N; j++){
dist[i][j] = read();
}
}
ArrayList<int[]> ans = new ArrayList<>();
for(int i = 1; i<=N; i++){
for(int j = i+1; j<=N; j++){
boolean e = true;
for(int k = 1; k<=N; k++){
if(k == i || k == j)
continue;
if(dist[i][j] == dist[i][k] + dist[k][j]){
e = false;
break;
}
}
if(e)
ans.add(new int[]{i,j,dist[i][j]});
}
}
StringBuilder sb = new StringBuilder();
for(int[] a : ans){
sb.append(a[0]+" "+a[1]+" "+a[2]).append("\n");
}
System.out.print(sb);
}
}사고의 흐름 및 풀이
거리 행렬로부터 원래 트리를 복원하라는 문제이다. 트리에서 두 정점 사이의 경로는 유일하다.
따라서 (k != i && k != j) 를 만족하는 어떤 정점 k가 존재하여
dist(i,j)=dist(i,k)+dist(k,j)를 만족한다면, k는 i - j 경로 위에 존재한다.
-> i 와 j 사이에는 중간 정점이 존재하므로 i, j 는 직접 연결된 간선이 아님.
반대로 i, j 가 실제 간선이 아니라면 트리의 성질상 i - j 경로에는 반드시 하나 이상의 중간 정점이 존재한다.
그 중 아무 정점 k를 선택하면 위의 dist 식이 성립한다.
-> 어떤 k 에 대해서도 위 식이 성립하지 않는 경우에만 i, j는 실제 간선이다.
모든 정점 쌍 i, j 에 대해 이를 검사하여 실제 간선만 남기면 원래 트리를 복원할 수 있다.
공식 해설과 비교
공식 해설은 MST를 활용해 풀었다. MST를 이루는 간선은 실제 간선이다를 활용한 것 같다.
주어진 거리 행렬을 완전 그래프의 가중치로 생각하면, 그 그래프의 MST가 원래 트리와 정확히 일치한다는 점이다.
이는 MST의 사이클 성질 (Cycle Property)를 활용한 것이다.
MST 이론에서 어떤 사이클에서 가장 무거운 간선은 MST에 포함될 필요가 없다는 정리가 있다.
실제 간선이 아닌 a, b에 대해
dist a, b = dist a, v1 + dist v1, v2 + ... + dist vn, b 가 된다.
그러므로 a, b와 원래 경로 간선들을 같이 보면 사이클이 생긴다.
그 사이클에서 a, b는 경로 간선들의 합과 같거나 더 크다.
따라서 MST는 굳이 a, b를 선택하지 않는다.
반대로 실제 간선은 반드시 선택된다.
이는 실제 간선 u-v w를 제거하면 트리가 두 컴포넌트로 나뉘어진다.
컴포넌트 A,B로 나뉘어진다고 하면, A의 어떤 정점 x, B의 어떤 정점 y에 대해서
dist ( x, y ) = dist (x, u) + w + dist (v, y) 이다.
즉, dist ( x, y ) >= w이고 u-v는 이 컷을 가로지르는 가장 가벼운 간선이다.
MST의 Cut Property에 의해 어떤 컷을 가로지르는 최소 간선은 MST에 반드시 포함된다.
1) 거리 행렬을 완전 그래프로 해석
2) 원래 트리의 실제 간선은 Cut Propery에 의해 MST에 반드시 포함된다.
3) 실제 간선이 아닌 정점쌍은 경로 간선들의 합으로 표현되므로 Cycle Property에 의해 제거됨
4) 따라서 MST = 원래 트리이므로 prim을 수행해 얻은 MST를 출력
문제 - 커지는 간선의 값
https://www.codetree.ai/ko/trails/complete/curated-cards/test-growing-edge-value/description
커지는 간선의 값 설명 | 코드트리
커지는 간선의 값에서 요구하는 복합 로직과 알고리즘 구성을 분석해, 고급 코딩테스트 합격에 한 걸음 다가가세요.
www.codetree.ai
public class Main {
static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int read() throws IOException{
sst.nextToken();
return (int) sst.nval;
}
static int N,M,K;
static ArrayList<int[]>[] g;
static long prim(){
PriorityQueue<int[]> q = new PriorityQueue<>(Comparator.comparingInt(a->a[1]));
q.add(new int[]{1,0});
boolean[] v = new boolean[N+1];
long sum = 0;
int k = 0;
boolean first = true;
while(!q.isEmpty()){
int[] cur = q.poll();
int ci = cur[0];
int cd = cur[1];
if(v[ci])
continue;
v[ci] = true;
if(first){
first = false;
}
else
sum += (k++ * K) + cd;
for(int[] n : g[ci]){
if(v[n[0]])
continue;
q.add(n);
}
}
return sum;
}
public static void main(String[] args) throws IOException{
N = read();
M = read();
K = read();
g = new ArrayList[N+1];
for(int i = 1; i<=N; i++)
g[i] = new ArrayList<>();
while(M-->0){
int u = read();
int v= read();
int w= read();
g[u].add(new int[]{v,w});
g[v].add(new int[]{u,w});
}
System.out.print(prim());
}
}사고의 흐름 및 풀이
MST의 간선을 하나 확정할때마다 K씩 나머지 간선의 가중치가 올라간다 해도 정렬 순서는 바뀌지 않으므로
Prim의 구현에서 sum을 계산할 때 k++로 증가시켜주면서 sum을 계산하고, first 플래그를 둬서 처음 1,0 은 간선이 아닌 시작지점이므로 처음에는 sum 계산을 건너뛰게끔 구현했다.
문제 - 원형 이동
https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-circular-movement/solutions
원형 이동 해설 | 코드트리
원형 이동에 대한 문제 해결 과정을 단계별로 파악하며, 복잡한 알고리즘을 효율적으로 구현하는 방법을 익히세요.
www.codetree.ai
public class Main {
static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int read() throws IOException{
sst.nextToken();
return (int) sst.nval;
}
static int N,M,K;
static final int INF = Integer.MAX_VALUE / 2;
static int[] midCost;
static Set<Integer> m = new HashSet<>();
public static void main(String[] args) throws IOException{
N = read();
M = read();
K = read();
midCost = new int[N];
for(int i = 0; i<N; i++){
midCost[i] = read();
}
while(M-->0){
int a = read()-1;
int b = read()-1;
if(b < a){
int t = a;
a = b;
b = t;
}
m.add(a);
}
int idx = 0;
while(m.contains(idx)){
idx++;
}
ArrayList<Integer> mins = new ArrayList<>();
// 원형이니까 idx는 살아있으니 그 바로뒤부터 보면서 한바퀴 돔
int s = (idx+1)%N;
int curMin = INF;
for(int i = 0; i<N; i++){
int cur = (s+i) % N;
curMin = Math.min(curMin, midCost[cur]);
//cur와 cur+1 공사중
if(m.contains(cur)){
mins.add(curMin);
curMin = INF;
}
}
long sum = 0;
int minVal = INF;
// mins에는 모든 지점을 star토폴로지로 연결하기 위한 가중치가 들어있음
// MST 비용 공식 : sum of component minimums + (global minimum) * (C - 2)
for(int x : mins){
sum += x;
minVal = Math.min(minVal, x);
}
sum += (long) minVal * (mins.size()-2);
System.out.print(sum <= K ? 1 : 0);
}
}사고의 흐름 및 풀이
1~N 지점을 원형으로 연결하는 건물이 있는데 중간 간선이 공사중이라 못 가기 때문에 중앙에서 1~N을 각각 연결하는 가중치가 주어질 때, 1~N 지점을 모두 방문하며 중간건물 통행료를 최소로 한다. 이때 통행료의 합이 K를 넘지 않는지의 여부를 묻는 문제.
Prim으로 풀이하게 되면 공사중인 간선을 제외하고 원래 건물간 간선은 가중치 0으로 추가하고 중앙 건물은 입력값대로 추가해서 그래프를 생성한 후, Prim을 수행하여 MST를 생성한다. 그리고 가중치 Sum이 K 이하 여부를 출력하면 된다.
이 풀이의 시간복잡도는 O(M log N) 정도이다.
사실 Prim까지 갈 필요 없이 원형인것과 스킵해야할 정점을 잘 고려해서
처음으로 공사 간선이 아닌 idx의 다음 정점을 고르고 거기서부터 직선 순회로 클러스터별 최소 연결값을 리스트에 저장한다.
MST 비용 공식에 따르면,
총 비용 = 컴포넌트 별 최소 비용 sum + (전체 최소 비용) * (컴포넌트 수 - 2)이므로 list에 저장한 최소 비용을 sum에 누적시키며 global minmum을 구해 전체 가중치 합을 저렇게 구하면 된다.
그리고 K 이하인지 여부 출력.
이 때의 시간복잡도는 O(M + N)이다.
문제 - 색칠된 정점에 연결하기 (크루스칼 풀이)
색칠된 정점에 연결하기 설명 | 코드트리
색칠된 정점에 연결하기에서 요구하는 복합 로직과 알고리즘 구성을 분석해, 고급 코딩테스트 합격에 한 걸음 다가가세요.
www.codetree.ai
public class Main {
static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int read() throws IOException{
sst.nextToken();
return (int) sst.nval;
}
static int N,M,K;
static int[] parent;
static boolean[] hasColor;
static int cnt = 0;
static long sum = 0;
static int find(int x){
if(parent[x] == x)
return x;
return parent[x] = find(parent[x]);
}
static void union(int a, int b, int w){
int pa = find(a);
int pb = find(b);
if(pa == pb)
return;
if(hasColor[pa] == true && hasColor[pb] == true)
return;
parent[pb] = pa;
hasColor[pa] |= hasColor[pb];
cnt++;
sum+=w;
}
public static void main(String[] args) throws IOException{
N = read();
M = read();
K = read();
hasColor = new boolean[N+1];
parent = new int[N+1];
for(int i = 1; i<=N; i++){
parent[i] = i;
}
while(K-->0){
hasColor[read()] = true;
}
ArrayList<int[]> li = new ArrayList<>();
while(M-->0){
int a = read();
int b = read();
int w = read();
li.add(new int[]{a,b,w});
}
Collections.sort(li, Comparator.comparingInt(a->a[2]));
for(int[] l : li){
if(cnt == N-1)
break;
union(l[0], l[1], l[2]);
}
System.out.print(sum);
}
}사고의 흐름 및 풀이
색칠된 정점 K가 있고 간선의 정보가 M개 제공되고 총 정점 수는 N개가 있을 때, 최소 하나의 색칠된 정점과 색칠되지 않은 나머지 정점이 전부 연결되는 MST를 만들 때, 그 가중치 합을 출력하는 문제이다.
Prim 챕터에 있는 문제인데 크루스칼식 풀이밖에 생각이 안나서 크루스칼로 풀긴했다.
아이디어는 어떤 컴포넌트에 이미 색칠된 정점이 포함되고 합치려는 컴포넌트에 색칠된 정점이 포함되어 있다면 굳이 합쳐봐야 합치는 cost가 증가할 뿐 두개는 분리되어 있어도 정답 조건을 만족한다.
-> hasColor boolean 배열을 두고 parent 배열 갱신하는 것처럼 서브트리의 root에 색칠된 정점 포함 여부를 갱신한다.
-> union 조건은 1) root가 서로 다르고 2) 각 root의 색칠된 정점 포함 여부가 둘 다 true가 아니라면 한다.
이후는 간선 정보 받아와서 Comparator로 가중치 오름차순 정렬하고 Kruskal 돌려서 가중치 출력
문제 - 최소 스패닝 트리 7 (MST 위에서의 최장경로)
최소 스패닝 트리 7 설명 | 코드트리
최소 스패닝 트리 7에서 요구하는 복합 로직과 알고리즘 구성을 분석해, 고급 코딩테스트 합격에 한 걸음 다가가세요.
www.codetree.ai
public class Main {
static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static int read() throws IOException{
sst.nextToken();
return (int) sst.nval;
}
static int N,M;
static ArrayList<int[]>[] g;
static ArrayList<int[]>[] t;
static long maxDist = 0L;
static int far = -1;
static void dfs(int cur, int p, long dist){
if(dist > maxDist){
maxDist = dist;
far = cur;
}
for(int[] n : t[cur]){
int ni = n[0];
int nd = n[1];
if(ni == p)
continue;
dfs(ni, cur, dist + nd);
}
}
static long prim(){
boolean[] v = new boolean[N+1];
PriorityQueue<int[]> q = new PriorityQueue<>(Comparator.comparingInt(a->a[2]));
q.add(new int[]{0,1,0});
long sum = 0;
boolean first = true;
while(!q.isEmpty()){
int[] cur = q.poll();
int s = cur[0];
int ci = cur[1];
int cd = cur[2];
if(v[ci])
continue;
v[ci] = true;
sum += cd;
if(first)
first = false;
else{
t[s].add(new int[]{ci,cd});
t[ci].add(new int[]{s,cd});
}
for(int[] n : g[ci]){
if(v[n[1]])
continue;
q.add(n);
}
}
return sum;
}
public static void main(String[] args) throws IOException{
N = read();
M = read();
g = new ArrayList[N+1];
t = new ArrayList[N+1];
for(int i = 1; i<=N; i++){
g[i] = new ArrayList<>();
t[i] = new ArrayList<>();
}
while(M-->0){
int a = read();
int b = read();
int w = read();
g[a].add(new int[]{a,b,w});
g[b].add(new int[]{b,a,w});
}
StringBuilder sb = new StringBuilder();
sb.append(prim()).append("\n");
dfs(1,0,0);
dfs(far,0,0);
sb.append(maxDist);
System.out.print(sb);
}
}사고의 흐름 및 풀이
N개의 정점과 M개의 간선 정보가 있을 때 모든 정점을 최소의 cost로 연결하기 위해 M개의 간선에서 몇개를 제거해서 연결한 후 cost의 sum과 해당 그래프에서의 최장 경로를 구하는 문제이다.
정답 조건을 만족하는 그래프는 MST이고 트리이다. 트리에서의 최장 경로란 a->b로 가는 경로는 유일하므로 아무 정점에서 dfs를 돌려서 가장 먼 정점 하나를 구해주고 거기서 가장 먼 정점을 구했을 때 dist의 값이 정답이 된다.
-> 이를 트리의 지름이라 한다.
-> void dfs ( int cur, int parent, long dist)
#코드트리 #코딩테스트 #코테공부 #코딩테스트사이트추천 #공채합격
'공부 > 알고리즘' 카테고리의 다른 글
| [코드트리] 8 - DP, Bitonic Cycle (0) | 2026.06.29 |
|---|---|
| [코드트리] 7 - Topological Sort, DAG DP (0) | 2026.06.22 |
| [코드트리] 5 - 구현/시뮬레이션 및 해결 전략 총정리 (0) | 2026.06.13 |
| [코드트리] 4 - 트리 DP, LCA, 한 달 공부 후기, 2차 갭체크 (0) | 2026.06.03 |
| [코드트리] 3 - DP, LIS, 부분 합 DP 복습, 북마크 활용 (0) | 2026.05.27 |
