자료알고 검색 결과

해당 글 130건
귀류법 : 명제가 거짓임을 가정한다.

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

안녕하세요. 백준 chogahui05입니다. RSA 알고리즘을 알기 위해서, 알아야 하는 것이 몇 가지 있는데요. 그 중 하나인 확장 유클리드 알고리즘을 알아보겠습니다. 사실 CRT라던지, 페르마의 소정리도 알아두면 좋기는 합니다. 이게 무엇을 구하는 것인지 알아보겠습니다. a와 b가 매우 큰 수일 때, 이 값은 어떻게 구하는 것이 좋을까요? 일단, gcd(a,b)의 값이 k이고, k값이 1이 아니라고 해 봅시다. 그러면, a = ka', b = kb'으로 다시 쓸 수 있습니다. gcd(a,b)값이 k이므로, a'과 b'도 정수입니다. x와 y가 정수라면 a'x + b'y도 정수입니다. 그러면, 1은 k의 배수여야 합니다. 그렇지 않습니다. 따라서, a와 b의 최대 공약수가 1이 아니라면, ax + by..
자료알고/알고리즘 2020. 4. 9. 23:42
랜덤 접근이 가능한 deque 자료구조를 chunk로 구현하면 어떤 이점이 있을까요?

deque를 공식 레퍼런스 사이트에서 보면, Chunk로도 구현이 된다고 되어 있습니다. 그러면, Chunk로 구현했을 때, 장점이 무엇일까요? 일단, deque가 Random 접근이 되려면, 기본적으로 연속적이여야 합니다. List는 Random access를 지원하지 않습니다. 더 정확히 이야기 하면, base 주소가 있고, 그것을 통해서 i번째 index에 접근할 수 있어야 합니다. 1차 구조의 덱을 생각해 보겠습니다. 원래 4개의 원소가 있었고, 5를 어딘가에 추가한다고 해 보겠습니다. 원래 capacity가 4였다면, 하나를 추가하려는 순간 추가하지 못하게 될 겁니다. 그러므로 확장 연산이 수행이 될 겁니다. 그러면 확장된 후에 기존의 원소가 어떻게 들어가는 것이 좋을까요? 이렇게 들어가는 것이..
자료알고/자료구조 2020. 4. 7. 01:08
세그먼트 트리 구조에서 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