Disjoint Set을 배웠는데 왜 쓰질 못 하니
알고리즘 문제는 자료구조 설계가 전부이다
스포일러 주의: 본 글은 SW Expert Academy의 1849번 문제 “영준이의 무게측정” 풀이법을 포함하고 있습니다.
어라 이게 왜 안 풀리지?
알고리즘 문제 풀다가 하도 안 풀려서 이 글을 적어본다. 알고리즘 교육에서 하루에 3문제 정도를 푸는데, 2문제가 평소보다 빨리 풀려서 기분 좋게 마지막 문제를 플고 있었다. 레벨이 좀 높은 문제이기도 했고input과 output이 좀 복잡해서 무엇을 해결해야 하는 지 이해하는데 시간이 좀 걸렸다. 다행히도 머릿속에 로직이 바로 떠올랐고 생각한대로 구현하기만 하면 되었다.
주어진 input 테스트케이스는 3개. 아주 단순했다. 시험삼아 몇 번 돌려보며 부호나 순서 정리 좀 하니 정확한 결과값이 출력되었다. 코드 그대로 사이트에 올려서 채점하기를 눌렀는데, 어라, Timeout이 나왔다. 메모리는 넉넉해서 메모이제이션 쓰면서 시간을 줄여보려 했지만 주어진 시간이 너무 짧아 Stack Overflow도 아니고 Timeout만 계속 나왔다.
하루 종일 Timeout을 없엘 수 있는 방법을 강구했지만 해결하지 못 했다. 다음 날 오전 문제풀이 시간에 해설을 좀 들으려고 했는데 문제 난이도 대비 설명이 너무 짧았다. 어쩔 수 없이 모범답안을 보고 해당 문제를 분석해보기로 했다. 제시된 정답은 C로 작성되었는데 로직 그대로 C++로 만들어도 Timeout이 나왔다. 다시 C로 바꾸고 나서야 Pass 되는 것을 보고 해당 언어에 해당 Approach가 아니고선 풀 수 없는 문제였음을 알게 되었다. 방법만 맞으면 되었지 아주 괘씸한 문제라는 생각이 들었지만, 모범답안의 Approach는 이번 기회에 확실하게 머릿속에 정리하기로 결심했다.
대략적인 문제 설명
여러 물건들이 있고 두 물건의 무게 차이만 측정할 수 있는 상황에서, 임의의 두 물건의 무게 차이를 계산해야 한다. 모든 측정이 끝난 후 계산하는 것이 아니라, 측정값과 계산해야 할 값이 임의로 입력된다. 특정 시점에서 갖고 있는 측정값으로 계산을 할 수 없다면 “UNKNOWN”을 출력하면 된다.
먄약 1번과 2번의 무게 차이가 2라는 측정값이 입력된 상태에서 2번과 1번의 무게
차이를 계산해야 한다면 -2를 출력하면 된다. 이후 2번과 3번의 무게 차이가
3이라는 측정값이 새롭게 입력되었다고 하자. 1번과 3번의 무게 차이는 2와
3을 더한 5를 출력하면 된다.
이 문제에서 생각해볼만한 점은 측정값과 계산해야 할 값이 임의로 들어온다는 것이다. 측정값 입력과 계산결과 출력이 구분되어 있었다면 그 사이에 탐색시간을 줄일 수 있는 최적화 작업을 한 번에 할 수 있다. 그러나 지금 상황에서는 측정값을 저장할 때 탐색 과정에 대한 염두도 함께 이루어져야 한다.
나의 풀이 방법
그래서 내 눈길을 끈 것은 3단 논법과 같은 구조였다. 1번과 2번의 무게 차이와 2번과 3번의 무게 차이를 알 수 있다면 1번과 3번의 무게 차이를 계산할 수 있다는 것이다. 하나의 물건으로부터 측정값들을 사슬 형식으로 탐색하다 비교 대상을 만날 때 누적된 무게 차이가 바로 두 물건의 무게 차이가 될 것이다.
효율적인 탐색을 위해 무게 차이를 저장할 때는 작은 번호의 물건 기준으로 큰
번호의 물건을 비교하기로 했다. 만약 2번과 1번의 무게 차이가 3이라고
측정되었으면 이를 1번과 2번의 무게 차이가 -3이라고 저장하는 방식 처럼
말이다. 이렇게 저장하게 된다면 탐색하는 과정에서 오름차순 만을 따르면 되니 더
효율적일 것이다.
1차시기: Map을 써보자
사슬처럼 이어진 탐색을 염두하니 Map이 떠올랐다. key는 int a (두 물건 중 작은
번호 a) value는 Vector<{ int b, int w }> (큰 번호 b와 무게 차이 w) 으로
정했다. 측정값들이 손실 없이 저장되기 때문에 계산할 때 이미 측정값으로 저장이
되어있거나 사슬을 따라 측정값들이 필요한 경우 모두 탐색 가능하다.
typedef struct comp_s {
int b;
int w;
} comp_t;
// key 기준으로 비교 대상의 번호와 무게 차이들을 저장
map<int, vector<comp_t>> m;
// 작은 번호부터 DFS
stack<comp_t> s;
s.push({a, 0});
while (!s.empty()) {
comp_t e = s.top();
s.pop();
if (e.b == b) return e.w;
for (auto c : m[e.b]) {
// 무게 차이를 누적
s.push({c.b, e.w + c.w});
}
}
return "UNKNOWN";
첫 번째 시도는 Timeout. 아무래도 Primitive Type이 아닌 STL들을 활용하다보니 그럴만도 했다. 오래걸리긴 해도 결과가 오답이 아니니 속도를 끌어올릴 수 있는 방법들을 강구해보기로 했다.
2차시기: 정렬과 가지치기를 하자
개선의 여지가 보이는 곳은 map에서의 value에 해당하는 vector<{ int b, int w }>
를 탐색할 때 이다. 만약 비교 대상의 번호(int b)가 큰 것부터 고른다면 찾고자
하는 사슬에 일찍 다다를 수 있을 것이다. 또한 vector 배열을 순회하면서 찾고자
하는 번호보다 큰 경우들의 탐색을 생략할 수 있을 것이다.
// ...
while (!s.empty()) {
// ...
// vector가 정렬되어있다고 할 때 큰 수부터 탐색 시작
for (int i=m[e.b].size(); i>=0; i--) {
comp_t c = m[e.b][i];
// 탐색 범위를 벗어나는 경우는 제외
if (c.b > b) continue;
s.push({c.b, e.w + c.w});
}
}
이번에도 결과는 Timeout. 차라리 틀렸다면 마음이 더 편했을 것 같은데 속상하기만 했다.
3차시기: 중간 결과값을 저장하자
이번에 내 머릿속에 떠오른 생각은 남아도는 메모리를 활용하자는 것이었다. 사슬을
따라가는 과정에서 e.w + c.w의 값을 누적하는데, 헨젤과 그레텔에서의 과자
부스러기처럼 중간 결과값의 흔적을 map에 남겨두면 좋을 것 같은 생각이 들었다.
// ...
while (!s.empty()) {
// ...
for (int i=m[e.b].size(); i>=0; i--) {
comp_t c = m[e.b][i];
if (c.b > b) continue;
// c.b 까지 계산한 값을 map에 저장
m[a].insert({c.b, e.w + c.w});
s.push({c.b, e.w + c.w});
}
}
메모리를 팔았으니 좀 나아지려나 싶었지만 여전히 Timeout이었다. 이전의 테스트케이스보다 눈에 띄게 메모리 사용량이 증가했지만 남아도는 메모리를 다 써버리기 전에 Timeout으로 끝난 듯 싶었다.
결국 이 문제는 나 혼자선 해결하지 못 했다. 다음 날 아침 코드리뷰 시간에 다시 머리를 굴려볼 생각이었다.
패러다임의 전환
코드리뷰 전에 강사님꼐선 수강생들 전반적으로 정답률이 저조한 것을 언급하셨다. 문제 해설을 해 주실때 Disjoint Set을 쓰면 된다고 하셨고 전체적인 설명은 몇분 만에 끝났다. 내가 체감한 문제 난이도에 비해 좀 허무하게 코드리뷰 시간이 끝나버렸고 당시 나는 왜 그 방법을 써도 되는지 조차 이해하지 못 했다.
그래도 내가 처음 구상한 접근방법이 틀리지 않았던 것은 확실했다. 하지만
그것보다 Disjoint Set을 활용했을 때 월등히 더 뛰어난 성능이 나왔다. 만약 더
시간을 내어 이 문제를 풀 때 Disjoint Set을 떠올렸을 지라도 나는 결코 map에서
벗어나지 못했을 것이다. 그 정도로 이 두 가지의 방법은 페러다임 차원만큼이나
차이가 났다.
Disjoint Set?
Disjoint Set을 모르던건 아니었다. 2021년 2학기 알고리즘및응용 수업시간에 이미 배웠고 Python으로 구현도 해봤으며, 이번 교육에서 들을 떄도 관련 함수들의 동작들이 새록새록 기억났다. 하지만 이 문제를 풀 때 Disjoint Set이 떠오르지 않은 것을 보면 다 무용지물이었다.
내가 아는 Disjoint Set은 집합 연산을 할 때 쓰이는 자료구조로 알고 있었다. 특정 집합에 포함 또는 비포함 여부를 찾아내는 정도로만 쓰이겠지 하고 짐작하고 있었다. 하지만 이번에 2년 전에 배운 슬라이들을 열어보니 그게 아니었다.
위의 슬라이드에서 Dynamic Graph에서 Disjoint Set이 DFS보다 더 낫다고 설명하고 있다. 딱 지금 이 문제와 같다. 측정값 입력과 탐색이 무작위라 따지고보면 Dynamic Graph를 그리고 있고, DFS로 탐색 알고리즘을 채택하여 효율성 향상을 추구하고 있었다. 이런 상황일 수록 Disjoint Set을 써야 함을 이미 배웠던 것이다.
그럼에도 불구하고 선뜻 Disjoint Set을 쓰는 것을 망설였던 이유는 해당 자료구조가 불완전하다고 생각했기 때문이다. 어떤 노드가 다른 노드와 연결되어 있다는 것은 압축적으로 표현할 수 있지만 그렇게 되면 대표 노드와 종속 노드와의 차이만 남지, 종속 노드 간의 비교 정보는 손실이 되리라 생각했기 때문이다. 하지만 Disjoint Set로 표현해도 필요한 정보들을 모두 꺼낼 수 있다.
값을 넣고 꺼내는 형식
1번과 2번의 무게 차이를 w12이라고 하고 2번과 3번의 무게 차이를 w23이라고
하자. 이 측정값을 있는 그대로 저장한다고 했을 때 1번과 3번의 무게 차이는
w12 + w23가 된다. Disjoint Set에서는 관점이 다르다. 2번을 기준으로
생각해보면 2번과 1번의 무게 차이는 w21 (-w12와 같다)이 되고, 1번과 3번을
비교 할 때는 w23 - w21로도 계산할 수 있다.
바로 이 대목에서 Disjoint Set을 떠올릴 수 있어야 한다. 집합의 대표 노드 (위의 예시에서는 2번)를 기준으로 종속 노드들의 무게 차이가 얼마나 되는 지를 알면 종속 노드 (1번과 3번) 간에도 무게를 비교할 수 있다는 것이다. 내가 이 문제에서 가장 중요하다고 생각했던 3단 논법 구조를 온전히 따를 필요가 없다는 것이다.
압축해서 저장하기
더이상 3단 논법을 따를 필요가 없어지게 되면서, 탐색 뿐만 아니라 측정값을
저장할 때도 효율적으로 진행할 수가 있다. 1번 부터 4번 까지 연속적으로 측정값이
존재한다고 할 때 (즉 w12, w23, w34가 존재할 때) 4번과 5번을 비교하는
측정값 (w45가 들어왔다고 하자. 모두 연결되어 있는 이 물체들 중에서 대표
노드를 1번으로 한다고 했을 때 각 물체의 상대적 크기는 다음과 같이 압축할 수
있다.
- 3번:
w13=w12+w23(대표 노드: 2번 -> 1번) - 4번:
w14=w13+w34(대표 노드: 3번 -> 1번) - 5번:
w15=w14+w45(대표 노드: 4번 -> 1번)
측정값을 저장할 때부터 대표 노드 기준으로 무게를 저장했다면 그 이후 종속 노드 기준인 어떠한 측정값이 들어오더라도 곧바로 대표 노드 기준으로 변환할 수 있다. 압축적인 탐색 뿐만 아니라 저장도 가능하다는 소리이다.
이렇게 구현해도 되는가?
모범답안의 코드는 Disjoint Set의 구현에서 크게 벗어나지 않는다. find_set과
union_set을 다음과 같이 구현하면 된다.
int parents[MAX_N];
int W[MAX_N];
int find_set(int n) {
if (parent[n] == n) return n;
W[n] += W[parent[n]]; // ???????
return (parent[n] = find_set(parent[n]));
}
void union_set(int a, int b, int w) {
int pa = find_set(a), pb = find_set(b);
if (pa == pb) return;
parent[pb] = pa;
W[pb] = W[a] - W[b] + w; // ???????
}
// ...
if (find_set(a) == find_set(b))
cout << W[b] - W[a] << endl;
물음표 살인마의 등장이다. 기존 Disjoint Set에서 달라진 건 저 두 부분의 물음표이다. 어떻게 저 두 줄이 손실 없이 측정값을 저장할 수 있는지 살펴보자.
재귀적인 += 연산
먼저 이해가 안 되었던 부분은 find_set에 += 연산을 넣었다는 것이다. ‘여러번
find_set을 부르면 어쩌려고’ 하는 걱정이 들었다. 결론부터 말하자면 그런 걱정은
안 해도 된다. 한번 탐색이 이루어지고 나면 set이 바뀌기 전 까지 W[n]의 값은
변할 일이 없다는 것이다. 해당 find_set은 path compression이 구현되어
있으므로 모든 종속 노드의 parent[n]은 모두 대표 노드를 가리키게 된다.
대표노드의 W[n]은 0으로, 여러번 find_set을 호출한다고 해도 W[n]에 0을 더할
뿐, 값의 변화는 일어나지 않는다.
W[pb] 변경 연산
union_set에서 W[pb]의 값이 변하는 것도 묘하다. 언뜻 봐선 저 한 줄의 의미를
간파하기가 어렵다. 다음과 같이 이해해보자. 어떤 트리(pb)를 다른 트리(pa)
아래에 이어 붙인다고 할 때, W[pb]의 값을 두 물건(a, b)의 무게
차이(w)를 활용한다고 하자.
- W[b] - W[a] = w
- =
(W[pb] + W[b])- W[a] = w - = W[pb] =
W[a] - W[b] + w
위와 같은 사실에 의해 W[pb]를 바꿀 수 있게 되고, 다음번 find_set 연산에서
pb 기준으로 표현되었던 W들이 pa 기준으로 변할 것이다.
Rank 활용: union_set에서 추가적으로 Rank Table을 관리한다면 더 효율적인
저장 및 탐색이 가능하다. 본 글에서는 Disjoint Set의 명확한 설명을 위해
생략한다.
결론
자료구조… 자료구조!!!
만약 이 문제를 보자마자 Disjoint Set이 떠올랐다면 이 글을 쓰지도 않았을 것이다. 그리고 Graph 탐색을 DFS만 고집해서 테스트케이스가 통과할 만큼의 성능이 나왔다면 Disjoint Set을 알아야 할 필요도 없었을 것이다. 하지만 DFS와 Disjoint Set의 성능 차이는 패러다임의 전환 급이었다. 앞으로 문제를 풀 때 입력 데이터 형식에 구애받지 말고 효율적인 자료구조를 강구해야겠다.
아는게 다가 아니다
학부 수업에서 Disjoint Set을 배웠으면서도 써먹지 못했다는 점이 가장 뼈아픈 패인이었다. 집합 뿐만 아니라 Graph, 특히 Dynamic Graph 상황에서 유용하게 쓰일 수 있다는 점을 앞으로 명심해야겠다. 16차수 중에 한 차수를 할애하여 괜히 설명해주신게 아니다. 구현이 쉽다고 해서 등한시하지 말고 어떠한 상황에서 어떠한 부분이 높은 성능을 끌어올릴 수 있는지 꼼꼼히 살펴 공부해야 겠다.