유니온파인드 검색 결과

해당 글 3건
수학적 귀납법을 활용하여 문제를 풀어봅시다.

귀납법은 이산 수학 시간에 들어보셨을 증명 방법입니다. 어떻게 쓰는지, 백준에 있는 문제를 풀어보도록 하겠습니다. 최근 USACO 실버에 나온 문제라고 하는데, 실버 같지 않습니다. 문제를 요약하면, 길이가 n인 순열이 주어집니다. 1부터 n까지의 수가 1번 등장합니다. 그리고 m개의 웜홀 정보가 (a, b, c)로 주어지는데, 너비가 c인 웜홀을 열면 a번째 원소와 b번째 원소를 바꿀 수 있다는 의미입니다. 어떻게 잘 배치해서 순열을 오름차순으로 정렬하려고 할 때, 연 웜홀들의 최소 너비를 최대화 시키는 문제입니다. 이걸 보면, 일단 이분 탐색임을 알 수 있는데, 정렬이 되어야 하는 조건이 상당히 어렵습니다. 어떻게 해 볼 것인가. 작은 집합부터 보면서, 큰 집합에서 성립하는지 보아야 겠습니다. 귀납법..
자료알고/알고리즘 2020. 12. 24. 00:01
배열에서 가장 큰 직사각형 구하기 : 관찰을 통해 풀어봅시다.

(2차원) 배열에서 가장 큰 정사각형을 찾는 것은 dp로 해결할 수 있습니다. 문제를 조금 바꿔보겠습니다. 가장 큰 직사각형은 어떻게 구해야 할까요? 문제의 제한이 딱 하나 바뀌었을 뿐인데, 난이도는 4단계 정도 높아졌습니다. 이 문제를 보도록 하겠습니다. 문제를 요약하면 다음과 같습니다. n이 범위는 1이상 2000 이하입니다. 시간 제한이 3초인 것을 감안했을 때, O(n^2)나 O(n^2logn) 정도에 풀어야 한다는 결론을 얻을 수 있습니다. 그런데, 후자는 생각보다 상수 줄이기가 빡빡하기도 하고 제가 시도해 본 방법이 아니므로, 저는 전자로 시도해 보겠습니다. 먼저 간단한 상식 아닌 상식을 통해서 관찰을 하나 해 보도록 하겠습니다. 길이가 3, 4, 2, 6인 높이 1짜리 직사각형이 있습니다. ..
자료알고/알고리즘 2020. 10. 18. 17:40
유니온 파인드 (union find) : 병합 연산과 루트를 찾는 연산만 있다.

안녕하세요. chogahui05입니다. 유니온 파인드 (Union find)는 2가지 연산을 지원하는 자료구조입니다. a와 b를 같은 집합에 넣는 것은 merge 연산으로 합니다. 같은 집합에 있는지 검사하기 위해서, find 함수를 호출합니다. 이 둘을 수행하는 구조인데요. 이 중에서 오늘은 경로 압축에 대해서 알아보겠습니다. 이것만 적용해도 상당히 빠르게 수행할 수 있습니다. 얼마나 빠르게 수행하는지는, 추후에 작성을 하도록 하겠습니다. 먼저 find 함수부터 보겠습니다. 되게 간단해 보이는데요. 여기서, p[x]는 x에서부터 타고 올라갔을 때, Root를 의미합니다. x의 부모가 x라면, 즉 자기 자신이라면, -1입니다. 3번째 줄은, 기저 조건입니다. 만약에 x의 부모가 -1인 경우에 바로 x를 ..
자료알고/자료구조 2020. 3. 14. 01:49