알고리즘 검색 결과

해당 글 51건
event driven : ps 문제에서 간단하게 활용해 봅시다.

이벤트를 넣어두고 그것을 활용한다. 작년에 스터디를 하면서 처음 들어본 말이였습니다. 사실, Java에서 mouse event listener와 같은 것이나 call back 패턴에서만 쓰이는 줄 알았기 때문입니다. 그런데, 특정 문제에서 이것을 잘 활용하면 생각보다 간단하게 풀 수 있습니다. Egg라는 문제를 보도록 하겠습니다. 이 문제를 간단하게 설명하면 아래와 같습니다. 생각보다 쉽지 않습니다. 그런데, 점들이 삭제되거나, 생성되는 이벤트가 주어지지 않으므로, 다음의 발상을 생각해 볼 수 있습니다. 사실, 이것만 계산을 하면, 문제에서 요구하는 쿼리도 해결할 수 있습니다. 이것을 어떻게 해결하면 좋을까요? 보라색 영역에 점이 있다고 해 보겠습니다. 우리는 x좌표가 A 이하이고, y 좌표가 B 이하인..
자료알고/알고리즘 2020. 5. 1. 17:58
귀류법 : 명제가 거짓임을 가정한다.

수학적으로 잘 설명된 포스팅은 많으니, 저는 ps 문제를 풀도록 하겠습니다. 백준 1649번 문제를 보겠습니다. 문제를 간단하게 요약하면 다음과 같습니다. 도시가 1000개 있습니다. 일방통행이 되는 도로 M개가 주어집니다. 중간 지점은 k개, C(1), ... , C(k)가 있다고 하겠습니다. A에서 출발해서 중간 지점들을 모두 거쳐서 B로 가고자 할 때, 가능한 경로의 가짓수를 구하는 것이 문제입니다. a에서 b까지 가는 도로는 최대 1개만 존재하고, 어떠한 교차로에서 출발해서, 다시 그 교차로로 돌아올 수 없다는 조건이 주어졌는데, 왜 이런 조건이 주어졌는지는 잘 모르겠습니다. 중간 지점들을 방문하는 순서는 정해진다는 관찰을 하면, 이 문제는 난이도가 상당히 쉬워 집니다. 이 관찰이 유효한 것인지 ..
자료알고/알고리즘 2020. 4. 27. 21:16
세그먼트 트리 구조에서 lazy propagation을 적용하는 코드를 뜯어봅시다.

안녕하세요. 백준에서 활동하고 있는 chogahui05입니다. 저번 lazy propagation 시간에는 변환을 합성한다는 관점에서 접근했습니다. 이번에는, 그것을 알고 있다는 전제 하에서, 어떻게 코드를 이해하셔야 할 지 설명을 해 보도록 하겠습니다. 이 글에 있는 코드는 설명을 위해 중요 부분만 간략화 한 것임을 참고해 주시면 감사하겠습니다. 먼저, lazy는 누적된 변환이라는 것이 핵심이라고 했습니다. 그러면, 누적된 변환이라는 개념이 왜 나왔는지부터 생각해 봅시다. 그 전에, 연속된 k개의 구간을 어떻게 처리할 것인지부터 고민해 봅시다. 보통의 segment Tree에서 연속된 k개의 구간을 업데이트 하는 연산은 klogn번만큼 수행이 됩니다. 문제는, 이런 쿼리가 50만개 들어왔다고 생각해 봅..
자료알고/자료구조 2020. 3. 31. 00:34
백준 공유기 설치 : 왜 이분탐색이 가능한가?

안녕하세요. 백준에서 chogahui05로 활동하고 있는 조경완입니다. 백준의 공유기 설치 문제는 많이 풀어보셨을 겁니다. 정확히 말하면, N개의 point가 있고, 그 중, C개를 설치하려고 할 때, 가장 인접해 있는 두 공유기 사이의 거리를 최대화 하라는 문제입니다. 어렵네요. 이를, 먼저 결정 문제로 바꾸어 봅시다. 그러면, 먼저 f(x)의 값을 어떻게 구해야 할 지 생각해 봅시다. N개의 집을 x 좌표 오름차순으로 정렬했다고 해 봅시다. 그러면 첫 공유기는 어디에 설치해야 할까요? 1번째 집에 설치해야 합니다. 왜 그럴까요? 문제 조건에 따르면, 같은 x좌표를 가지는 집은 없다고 했습니다. 그렇기 때문에, 집이 n개가 있고, i번째 집의 위치를 x[i]라고 하면, 아래의 식이 성립합니다. 이는 집..
자료알고/알고리즘 2020. 3. 27. 01:52
좌표 압축 알고리즘 : 범위가 클 때 어떻게 공간을 줄일까요?

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