자료알고/알고리즘 검색 결과

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

수학적으로 잘 설명된 포스팅은 많으니, 저는 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
백준 공유기 설치 : 왜 이분탐색이 가능한가?

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

안녕하세요. 백준 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
백준 화성지도 : 구간에 장벽을 세운다.

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