해당 포스팅은 "코딩 테스트 합격자 되기 C++편" 의 책 및 강의를 보며 포스팅 한 내용입니다.
[지금 무료] 코딩 테스트 합격자 되기 - C++ 강의 | dremdeveloper - 인프런
dremdeveloper | 코딩 테스트 합격을 위한 C++ 강의, 책 없이도 가능! 저자와 직접 소통 가능한 커뮤니티 제공!, [사진]여기에 문의 하세요https://open.kakao.com/o/gX0WnTCf📘 코딩 테스트 합격자 되기 - C++편
www.inflearn.com
💬주요 키워드
집합 : 코테에서의 집합이란, 중복되지 않은 요소를 트리구조로 묶어놓는 것을 말하며, 보통 배열로 많이 표현하는데 index를 자기 자신, element로 부모를 가리켜 노드간의 관계를 표현하였다.
상호배타적 집합 : 집합의 구조에서 서로 이어지지 않은 노드가 있다면 서로 다른 집합이라고 판단하여, 상호배타적 집합이라고 표현한다. 코테에서는 대부분 상호배타적 집합이 나온다고 한다.
루트노드 : 집합을 대표하는 원소를 부모노드라고 하며, index와 element가 같다면 해당 집합을 대표하는 루트노드 라고 표현한다.
유니온-파인드 알고리즘 : 유니온 - 파인드 알고리즘이란, 상호배타적 집합에서 서로 다른 집합들의 노드를 이어 같은 집합으로 만드는 것이 유니온, 하나의 노드에 이어져있는 루트 노드를 찾는 것을 파인드 알고리즘 이라고 한다.
경로 압축 알고리즘 : 파인드 알고리즘을 사용하는 와중, 시간복잡도가 최대 O(n)이기 때문에 이 문제를 방지하기 위하여, 모든 노드의 부모 노드를 루트노드로 만드는 것을 경로 압축 알고리즘이라고 한다.
랭크 기반 알고리즘 : 유니온 알고리즘을 사용 할 때, 말단노드와 루트노드의 깊이가 달라지는 현상을 방지하기 위하여 집합간의 레벨을 비교하여 레벨이 낮은 쪽이 높은 쪽에 붙을 수 있도록 만들어 주는 알고리즘이다.
📝내용
집합(DisjointSet)
1. 정의
집합이란 트리구조에서 노드간의 연결관계를 두고 집합이라고 표현한다.
수학에서의 집합과 비슷하면서 다른데, 서로 다른 트리에서 같은 노드의 값을 가지고 있다면 교집합으로 표현할 수 있고
합집합과 같이 서로 다른 두개의 트리에 연결관계를 이어줌으로서 각각 두개의 트리를 하나의 트리로 이어줄 수 있다.
일단, 코테에서의 집합은 교집합은 없다. 라고 생각하면 되고 이러한 교집합이 없는 관계를 상호-배타적 집합(disjointSet) 이라고 한다.
또한, 상호배타적 집합의 두 트리를 합치는 과정을 Union이라고 한다.
마지막으로, 두 개의 트리에는 각각 루트노드의 개념이 있는데 이러한 루트 노드를 찾는 과정을 Find라고 한다.
이정도만 알고 있으면, 어느정도 유니온-파인드 알고리즘을 구현할 수 있을듯 하다.
find함수에는 각 노드별 부모노드를 루트노드로 통일하는 경로 압축 알고리즘이 적용되고,
union함수에는 랭크(높이)가 낮은 트리가 높은 트리에 붙는 랭크 기반 알고리즘이 적용된다.
2. 집합의 ADT
1) find : 트리의 루트노드를 확인
2) merge : 원래는 union이나, std에 다른 내장함수가 있으므로 merge로 변경
3) isCycle : 최단경로를 구하는데 필요한 요소로서, 트리 내부에서 노드가 순환하는 현상이 있는지 확인하는 용도이다.
ADT를 바탕으로 구현한 코드
class DisjointSet
{
private:
vector<int> parent, rank;
public:
DisjointSet(int size) : parent(size, -1), rank(size, 0) {}
int find(int node)
{
if(parent[node] == -1) return node;
return parent[node] = find(parent[node]);
}
void merge(int node1, int node2)
{
int root1 = find(node1);
int root2 = find(node2);
if(root1 != root2)
{
if(rank[root1] > rank[root2])
{
parent[root2] = root1;
}
else if(rank[root1] < rank[root2])
{
parent[root1] = root2;
}
else
{
parent[root2] = root1;
rank[root1]++;
}
}
}
bool isCycle(int node1, int node2) { return find(node1) == find(node2);}
};
3. 문제 풀이
1) 유니온-파인드 알고리즘 구현하기(연습문제)
a. 문제 설명
상호배타적 집합을 표현하고 관리하는데 다음 두 연산이 필요합니다.
- union(x, y) : x와 y가 속한 두 집합을 합칩니다.
- find(x) : x가 속한 집합의 대표 원소를 찾습니다.
operations라는 배열은 수행할 연산을 의미합니다. 연산의 종류는 2개입니다.
- ['u',1,2]는 노드1과 노드2에 대해 union 연산을 수행
- ['f',1,2,]는 노드1과 노드2의 루트노드가 같은지 find연산으로 확인해서 같으면 true, 다르면 false를 반환
경로압축과 랭크 기반 합치기를 활용해서 유니온-파인드 알고리즘을 구현해주세요. operations배열에 있는 연산을 모두 수행한 후 find 연산 결과를 순서에 맞춰 벡터에 담아 반환하는 solution() 함수를 구현해주세요.
ex)
| k | operations | result |
| 3 | [u, 0, 1], [u,1,2], [f,0,2] | true |
| 4 | [u,0,1] , [u,2,3],[f,0,1],[f,0,2] | true,false |
b. 의사 코드
- 우선 집합은 배열이라고 했으니, 배열을 통해 구현해보자.
- 모든 노드들은 index 가 element가 되게 하여 수많은 노드방울을 만든다.
- 각 2개의 노드를 받는 union함수를 만들어 트리를 구성할 수 있도록 한다.
- 트리를 구성하면 find()함수를 만들어 트리의 부모노드를 만든다.
- 경로 압축 알고리즘과 랭크기반 알고리즘을 적용시킨다.
c. 문제 풀이
#include <bits\stdc++.h>
#include <iostream>
using namespace std;
int find(int x, vector<int>& disjointset)
{
if (disjointset[x] == x) return x;
return disjointset[x] = find(disjointset[x], disjointset);
}
void merge(int x, int y, vector<int>& disjointset, vector<int>& rank)
{
int rootX = find(x, disjointset);
int rootY = find(y, disjointset);
if (rootX == rootY) return; // 2개의 루트노드가 같을 경우는 1개의 트리라는 뜻으로 이미 합쳐져있음.
if (rank[rootX] > rank[rootY]) disjointset[rootX] = rootY;
else if (rank[rootX < rank[rootY]]) disjointset[rootY] = rootX;
else
{
disjointset[rootY] = rootX;
rank[rootX]++;
}
}
vector<int> solution(int k, vector<vector<char>> operations)
{
vector<int> answer;
vector<int> disjointset;
vector<int> rank;
for (int i = 0; i < k; i++)
{
disjointset.push_back(i);
rank.push_back(0);
}
for (const auto& e : operations)
{
if (e[0] == 'u') merge(e[1] - '0', e[2] - '0', disjointset, rank);
else
{
int rootX = find(e[1] - '0', disjointset);
int rootY = find(e[2] - '0', disjointset);
answer.push_back(rootX == rootY);
}
}
return answer;
}
int main()
{
vector<vector<char>> operations;
operations.push_back({ 'u', '0', '1' });
operations.push_back({ 'u', '1', '2' });
operations.push_back({ 'f', '0', '2' });
vector<int> result = solution(3, operations);
for (auto e : result) cout << e << " ";
cout << endl;
vector<vector<char>> operations2;
operations2.push_back({ 'u', '0', '1' });
operations2.push_back({ 'u', '2', '3' });
operations2.push_back({ 'f', '0', '1' });
operations2.push_back({ 'f', '0', '2' });
vector<int> result2 = solution(4, operations2);
for (auto f : result2) cout << f << " ";
return 0;
}
d. 문제 후기
- 시간복잡도 O(n) : operations에 주어진 명령만큼만 실행하기 때문에 1번 순회하는 n의 시간복잡도를 갖는다.
- 이제는 구현에 꽤나 자신감이 붙어, 맨땅에서도 이론만 들어서 구현할 수 있게 된 것 같다.
2) 폰켓몬(링크)
a. 문제 설명
문제 참조
b. 의사 코드
- 우선 unordered_map을 이용하여 종류가 몇개인지 세는 용도로 해시를 등록해준다.
- 그리고 maxnum이라는 함수를 만들어서, 문제에 주어진 폰켓몬 N/2를 가져가도록 변수를 넣어준다.
- 마지막으로 unordered_map과 maxnum중 작은 것을 return해준다.
c. 문제 풀이
#include <vector>
#include <bits/stdc++.h>
using namespace std;
int solution(vector<int> nums)
{
int answer = 0;
int maxnum = nums.size()/2;
unordered_map<int,int> um;
for(int i = 0; i < nums.size(); i++)
{
um[nums[i]] = i;
}
if(um.size() < maxnum)//최댓값과 숫자의 종류 중 누가 더 큰지
{
return um.size();
}
else
{
return maxnum;
}
return answer;
}
d. 문제 후기
- 시간복잡도 O(N) : nums의 개수만큼만 중복되지 않도록 unordered_set이나 unordered_map에 넣어주기 때문에, nums를 넣어주는 순회의 수만큼 시간복잡도가 구성된다.
- unordered_map이 시간복잡도상으로 좋은 성능을 보여주기 때문에 기회만 된다면 자주 써먹는 습관을 들여야 겠다.
3) 섬 연결하기(링크) <-- 12.5% 오답 ⭐⭐⭐⭐⭐
a. 문제 설명
링크 참조
b. 의사 코드
- 문제를 읽어보면 연결할 수 없는 섬은 존재하지 않으므로, 작은 코스트 먼저 섬끼리 이을 수 있도록 코스트 오름차순으로 정렬한다.
- 정렬된 costs를 순회하며 2개의 노드를 unordered_map으로 체크하여 n번 언급될 경우 break하여 그동안 순회하며 모은 cost를 더한 값을 리턴한다.
c. 문제 풀이
#include <bits/stdc++.h>
using namespace std;
bool rule(vector<int> a, vector<int> b)
{
return a[2] < b[2];
}
int solution(int n, vector<vector<int>> costs)
{
int answer = 0;
unordered_map<int,int> um_cnt;
sort(costs.begin(), costs.end(), rule);
for(const auto& e : costs)
{
um_cnt[e[0]]++;
um_cnt[e[1]]++;
answer += e[2];
if(um_cnt.size() == n) break;
}
return answer;
}
d. 문제 후기
- 결국에는 트리의 사이클 문제에 대해 확인해야 하므로, 사이클과 최대신장트리라는 개념을 알아야 풀 수 있는 문제였다. 사이클이 걸리는지 확인하기 위해 결국, disjointSet을 구현하며 풀어야 하는 문제로 보인다.
- 정답
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
class DisjointSet
{
private:
vector<int> parent, rank;
public:
DisjointSet(int size) : parent(size, -1), rank(size, 0) {}
int find(int node)
{
if(parent[node] == -1) return node;
return parent[node] = find(parent[node]);
}
void merge(int node1, int node2)
{
int root1 = find(node1);
int root2 = find(node2);
if(root1 != root2)
{
if(rank[root1] > rank[root2])
{
parent[root2] = root1;
}
else if(rank[root1] < rank[root2])
{
parent[root1] = root2;
}
else
{
parent[root2] = root1;
rank[root1]++;
}
}
}
bool isCycle(int node1, int node2) { return find(node1) == find(node2);}
};
int solution(int n, vector<vector<int>> costs)
{
sort(costs.begin(), costs.end(), [](const vector<int> &a, const vector<int> &b) {return a[2] < b[2];});
DisjointSet disjointSet(n);
int totalCost = 0;
for(const auto& e : costs)
{
int cost = e[2];
int node1 = e[0];
int node2 = e[1];
if(!disjointSet.isCycle(node1,node2))
{
disjointSet.merge(node1,node2);
totalCost += cost;
}
}
return totalCost;
}
'GroupStudy > [C++]코딩 테스트 합격자 되기' 카테고리의 다른 글
| [코딩 테스트 합격자 되기] 6주차 - 그래프 (0) | 2024.08.12 |
|---|---|
| [코딩 테스트 합격자 되기] 4주차 - 트리 (0) | 2024.08.01 |
| [코딩 테스트 합격자 되기] 3주차 - 해시 (0) | 2024.07.25 |
| [코딩 테스트 합격자 되기] 2주차 - 스택/큐 (0) | 2024.07.13 |
| [코딩 테스트 합격자 되기] C++ - 알고리즘 (0) | 2024.07.11 |