귀납법은 이산 수학 시간에 들어보셨을 증명 방법입니다. 어떻게 쓰는지, 백준에 있는 문제를 풀어보도록 하겠습니다. 최근 USACO 실버에 나온 문제라고 하는데, 실버 같지 않습니다. 문제를 요약하면, 길이가 n인 순열이 주어집니다. 1부터 n까지의 수가 1번 등장합니다. 그리고 m개의 웜홀 정보가 (a, b, c)로 주어지는데, 너비가 c인 웜홀을 열면 a번째 원소와 b번째 원소를 바꿀 수 있다는 의미입니다. 어떻게 잘 배치해서 순열을 오름차순으로 정렬하려고 할 때, 연 웜홀들의 최소 너비를 최대화 시키는 문제입니다. 이걸 보면, 일단 이분 탐색임을 알 수 있는데, 정렬이 되어야 하는 조건이 상당히 어렵습니다. 어떻게 해 볼 것인가. 작은 집합부터 보면서, 큰 집합에서 성립하는지 보아야 겠습니다. 귀납법..
ps 검색 결과
이 글을 읽기 전에 잘못 구현된 다익스트라 글을 보고 오시는 것 추천드립니다. 저는 그 글을 읽으셨고, 그 글에 나온 저격 데이터가 어떠한 원리로 작성되었는지 30% 정도 이해했다는 전제 하에 진행하도록 하겠습니다. 보통 이 알고리즘을 구현하실 때 Priority Queue를 이용하는 경우가 많습니다. 저는 그것을 기준으로 작성하였습니다. min_cost와 where_is_from, visit와 con이 있습니다. 이 중에서 con은 graph를 구축하는데 쓰이는 자료구조 정도로 생각하시면 됩니다. C++의 STL에서 vector con과 같습니다. min_cost를 inf로 초기화 합니다. 그리고, where_is_from을 -1로, visit를 false로 초기화를 합니다. 다음에 pq에 시작점을 넣..
수학적으로 잘 설명된 포스팅은 많으니, 저는 ps 문제를 풀도록 하겠습니다. 백준 1649번 문제를 보겠습니다. 문제를 간단하게 요약하면 다음과 같습니다. 도시가 1000개 있습니다. 일방통행이 되는 도로 M개가 주어집니다. 중간 지점은 k개, C(1), ... , C(k)가 있다고 하겠습니다. A에서 출발해서 중간 지점들을 모두 거쳐서 B로 가고자 할 때, 가능한 경로의 가짓수를 구하는 것이 문제입니다. a에서 b까지 가는 도로는 최대 1개만 존재하고, 어떠한 교차로에서 출발해서, 다시 그 교차로로 돌아올 수 없다는 조건이 주어졌는데, 왜 이런 조건이 주어졌는지는 잘 모르겠습니다. 중간 지점들을 방문하는 순서는 정해진다는 관찰을 하면, 이 문제는 난이도가 상당히 쉬워 집니다. 이 관찰이 유효한 것인지 ..
안녕하세요. 오늘은 USACO에 나왔던 Balanced Cow Subsets 문제를 풀어보도록 하겠습니다. 문제는 간단해요. 문제를 해석하는 연습을 하셨다면, 이 정도는 밑줄을 치셨으리라 생각이 듭니다. 왜 n이 20 이하일까요? 그냥 브루트 포스 해도 되는 거 아닐까요? 라는 생각을 하실 수도 있을 듯 싶어요. 그런데, 이 문제는 무려 옛날 USACO gold에 나온 문제입니다. 단순히 브루트 포스 해도 되었다면, Bronze에나 냈을 거에요. 그런데 Gold도 가끔 브루트 포스 하면 풀리는 게 있으니, 그렇게 해도 되지 않을까요? 그러면 어떻게 브루트 포스를 할 건가요? n = 20이라면 많아봤자, 2^20개의 상태가 있으니까, 이들에 대해서 일일히 check를 해 보는 방법이 있습니다. 그렇게 오래..
오늘은 2019년 마지막 날이니, 마지막 날을 장식할 만한 포스트를 작성하도록 하겠습니다. 아래 수식의 결과 값을 10억 7로 나눈 나머지는 얼마일까요? 단, n은 2이상, 10^6 이하 자연수입니다. n = 10^6이면 대충 O(n)이나, O(128n)에 돌려도 무난할 복잡도입니다. 이것이 생각보다 꽤 큰 힌트 중 하나입니다. 먼저, 최대 공약수에 대한 관점을 비틀어 봅시다. a와 b의 최대 공약수가 g였다고 해 봅시다. 이걸 P라고 합시다. 그러면 위 수식이 성립합니다. 그런데 정말 그럴까요? 위 수식을 Q라고 해 봅시다. 만약에, gcd(a/g,b/g)의 값이 c이고, 이 값이 1이 아니라면, gcd(a,b)의 값은 gc가 됩니다. c가 1이 아니므로, gc의 값은 g가 아닙니다. 즉, not Q이..
최근댓글