ksjb2897   1년 전

코드는 그냥 혹시나 해서 올렸고, 코드가 좀 복잡하니 코드는 안읽으셔도 됩니다..!

일단 제가 이 문제를 보면서 들었던 사고과정부터 말씀드리겠습니다. 일단 C언어 기준입니다!

이 문제를 풀면서 결국 집합들의 union 연산을 한번 할 때 작은 집합에서 큰 집합으로 옮겨야 한다는 것을 깨달았습니다. 그래서 union연산을 하려했는데, 원소들의 정보를 전부 유지하면서 옮겨야 되는 것도 깨달아서, 작은 집합의 모든 원소들을 보면서, 그 원소들이 큰 집합에 있는지 탐색하고 싶었습니다. 근데 이걸 각각의 원소마다 logN안에 해야되므로, 이분탐색이 필요하다는 것도 깨달았습니다. 근데 여기서 더하여, 이분탐색을 통해 위치를 찾고, 그 위치에 추가되는 원소를 넣어야 된다고 생각했습니다. 결국, 이분탐색과 삽입이 동시에 필요하다고 결론 지었습니다. 그런데,

1. 배열을 통해 집합을 구현 : 이분탐색 가능. 하지만 원소 삽입이 최대 O(N) 걸림.

2. 연결리스트를 통해 집합을 구현 : 원소 삽입은 O(1)이지만, 이분탐색이 불가능하고 차례대로 탐색밖에 못함(O(N))

그래서 우리 gpt 형님에게 물어봤습니다... 이분탐색 + 삽입 동시에 가능한게 뭐있냐?? 라고..

그러더니 treap를 추천해줘서 인터넷에서 공부한다음 직접 구현해서 풀었습니다.

여기서 더하여 원소가 최대 10^9이므로 매칭을 할 수가 없어서 해싱을 통해 random 값을 저장해 둔다음 풀었습니다.

이렇게 어렵게 풀었는데 고작(?) 골드1문제라니 ㅠㅠ 그래서 다른 풀이가 뭐가 있나 궁금합니다..

여기까지는 제 한탄 + 배경이고 그래서 질문이 뭐냐면,

1. 이 문제가 삽입/탐색이 둘다 logN으로 할 수 있는 자료구조를 사용해야하는 것이 맞나요?

2. 다른 언어들은 집합을 어떻게 다루나요..? c++ 코드를 보니까 정말 간결하고 짧던데, 삽입/탐색이 둘다 logN으로 가능한 내장 자료구조가 있는건가요 아니면 다른 방식으로 푼건가요? c++은 공부안해서 볼 줄 몰라서요 ㅠ

3. treap가 쉽다고 해서 구현해봤는데 생각보다 어렵더라구요. 삽입/탐색이 둘다 logN인 다른 자료구조들은 뭐가 있을까요? 저 말고 c언어로 푼 사람 한 명 있던데 보니까 ll, rr로 회전을 시키더라구요. 이건 무슨 자료구조일까요..? 저는 split으로 해서 treap 를 구현했거든요.

4. 계속 소신껏 c언어로 헤쳐나가는 중인데, 이런문제들을 보면 시간도 많이 잡아먹고 c언어가 불리하다는 생각이 들어요. c++로 바꿔야할까요? 아니면 고수분들 중에서 계속 c언어로 밀고 가는사람들도 있나요..?

ksjb2897   1년 전

아 그리고 이게 왜 유니온 파인드인지도 모르겠어요..

siyamaki   1년 전

대충 설명하자면 자기 자신만을 가지는 N개의 집합을 만들고 1이 들어오면 union, 이 때 두 집합의 크기를 비교해 작은 집합을 큰 집합으로 옮기고 비움, 최악의 경우여도 한번 연산할 때마다 연산 횟수가 1/2씩 줄어듦.(N / 2 -> N / 4 -> N / 8 ... -> 1)

ksjb2897   1년 전

근데 일단 핵심 질문이 작은집합을 큰 집합으로 옮기는 것을 어떻게 짧은 시간안에 하냐? 가 궁금합니다.. 저는 treap으로 구현했는데 너무 어렵고 복잡한 것 같아서 다른 방법이 있나 싶어서요.

kangjijoon   1년 전

저도 Union find는 아닌것 같은데..

Union find하면 공간복잡도가 O(N(max(sij)-min(sij))일텐데 sij의 범위가 1< sij <109라서 메모리 초과 나지 않나요?

이 문제 알고리즘 분류도 Union find는 아니던데.. 

ksjb2897   1년 전

제 느낌상 트리의 색깔과 쿼리를 풀라고 앞에 넣어둔 것 같기도 해요.

djm03178   1년 전

C로 작성하면 상당히 복잡할 수밖에 없는 문제입니다. C++로는 1~10^9의 모든 원소를 다 가지지 않아도 처음 그 인덱스에 접근할 때 자리를 생성해주는 편리한 자료구조가 있기 때문에 문제를 쉽게 풀 수 있다고 생각하시면 좋을 것 같아요.

질문자님께서 보신 회전하는 자로구조는 아마 RB tree 내지는 AVL tree를 직접 구현한 걸 텐데, 바로 이런 자료구조가 C++에는 라이브러리로 내장이 되어 있습니다.

여기에 "작은 집합에서 큰 집합으로 합치는 테크닉"을 적용한 union find를 사용하면 문제를 간단히 해결할 수 있습니다.

ksjb2897   1년 전

감사합니다..! 언어 바꿀 고민을 좀 해봐야겠네요..!

djm03178   1년 전

정확히는 union find는 아니고 비슷한 느낌으로 집합만 관리하면 됩니다.

댓글을 작성하려면 로그인해야 합니다.