자료알고 검색 결과

해당 글 130건
유니온 파인드 (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
플로이드 알고리즘 : 어떻게 최단거리가 갱신되는가?

안녕하세요. 백준 chogahui05입니다. 플로이드 알고리즘은, 알고리즘 수업 시간에 많이 배우실 거에요. 음의 사이클이 없는 경우에, 이 알고리즘이 어떻게 동작하는지 알아보도록 하겠습니다. 이 코드는 몇 줄 안 되니 외우시는 분들도 많으실 거라 생각이 듭니다만. 그래도 보도록 하겠습니다. 9번째 줄의 for loop를 보면 n번 loop를 돌린다는 것을 알 수 있어요. 다음에 11번째 줄에 있는 for loop, 13번째 줄에 있는 for loop, 15번째 줄에 있는 if문 안을 보시면, 조건이 맞으면 dist[i][j]를 업데이트 한다는 것을 알 수 있어요. 음의 사이클이 없다면, a에서 a로 오는 비용은 0보다 크거나 같습니다. 따라서, 같은 장소를 2번 이상 방문하는 것은 손해라는 것을 알 수..
자료알고/알고리즘 2020. 3. 3. 05:20
누적된 변환과 lazy propagation 알고리즘

안녕하세요. 2 ~ 3편에 걸쳐서, 레이지 프로퍼게이션을 적용한 세그먼트 트리를 쓰도록 하겠습니다. 세그먼트 트리에 쓰이는 lazy 기법을 1줄로 요약하면 아래와 같습니다. 네. 앞으로 쓸 2 ~ 3편 글에 대한 핵심입니다. 이것만 정확하게 이해하시면 됩니다. 정말 중요한 키워드는 굵게 강조 표시까지 했는데요. 변환, 흡수, 전파. 이 셋입니다. 변환, 흡수, 전파? 이게 대체 무엇을 의미할까요? 이번 시간에는 이 중에 첫 번째 키워드와 두 번째 키워드인 변환과 흡수에 대해 알아보도록 하겠습니다. 왜 자식에 전파하는지는 다음 포스트에서 이야기 해 보도록 하겠습니다. 1번 변환을 생각해 봅시다. 이 변환을 함수 f(v)로 표현해 봅시다. 그러면, f(v) = v + a가 됩니다. 다음에, 2번 변환을 생각..
자료알고/자료구조 2020. 2. 29. 22:37
백준 화성지도 : 구간에 장벽을 세운다.

백준 화성지도라는 문제는, 저를 골치 아프게 하던 문제 중 하나였습니다. 저는 이 문제를, 어떠한 상황으로 바꿔서 풀었습니다. 그 방법으로 접근해 보도록 하겠습니다. 세그 트리라는 말은 이 블로그에서는 언급하지 않았으니, '구간을 관리하는 자료 구조' 정도로 생각합시다. 그러면 조금 더 편하지 않을까 싶어요. 문제를 보셨고, sweeping에 대한 개념이 어느 정도 쌓여 있다면, 다음과 같은 쿼리를 처리해야 한다는 것을 알 수 있습니다. 문제의 특성상, 전체 구간을 보았을 때, 어떠한 특정 구간의 값이 0 미만으로 떨어질 일 또한 없다는 것을 알 수 있습니다. 구간 [a,b] 에 1이나 -1을 더하는 건 lazy 기법을 이용하면 쉽게 할 수 있을 듯 싶은데, 3번 쿼리가 문제입니다. 이 문제를 해결하기 ..
자료알고/알고리즘 2020. 2. 24. 00:00
좌표 압축 알고리즘 : 범위가 클 때 어떻게 공간을 줄일까요?

ps를 하시다 보면, 좌표 압축이라는 이야기를 심심치 않게 들으실 수 있습니다. 간단하게 말해서, 데이터를 정렬해서, 다시 순서를 부여하는 것을 말합니다. 특히 쿼리 문제에서 많이 보이는데요. 구간이 10^10개, 10^18개가 있는데, 쿼리가 단지 10만개라면, 10^18개를 다 들고 있지 않고, 중요한 구간이나 숫자만 들고 있는 기법입니다. 그러면 압축이 될 거에요. 이런 문제를 생각해 봅시다. 자. 여기서, Lv랑 Rv, 그리고 k는 [0, 10^10]에 속하는 정수라고 해 봅시다. 그리고 n과 Q가, 구간 [1, 10^5]에 속하는 정수라고 해 봅시다. 그러면, k와 Lv, Rv가 [0, 10^10] 범위에 속하는데, 어떻게 하면 좋을까요? 오프라인 처리가 가능하다면, 그냥 k값하고, Lv, Rv..
자료알고/알고리즘 2020. 2. 22. 03:40