본문 바로가기
반응형

Programming401

[C/C++] 백준 #1780 종이의 개수(분할정복) 이번 문제는 무조건 분할을 한 후에, 그 결과를 토대로 결정을 하게 하는 문제입니다. 결국 분할 정복 문제입니다. 9개로 나누어 그 결과가 모두 같으면, 숫자의 종이를 합치는 것이죠. 원래의 문제는 하나의 종이에 모두 같은 숫자가 있다면 분할하지 않는 것이지만, 이렇게 하면, 상당히 많이 숫자를 세어야 합니다. 종이에 써져있는 숫자의 갯수가 최대 4백만개가 되므로, 숫자가 같은지 검사하는 것은 매우 비효율적입니다. 제가 사용한 방식은 무조건 분할한 다음, 9개가 모두 같은지 검사하여 같으면 종이를 합치는 것이죠. 시간 효율을 따져본다면, 다음과 같이 점화식을 낼 수 있습니다. \[ T(1) = 1 \] \[ T(n) = 9T(n/3) + 1 \] 형태가 되어서 \(O(n^2)\) 으로 볼 수가 있습니다... 2022. 10. 20.
[C/C++] 백준 #1769 3의 배수(구현) 이번 문제는 특별한 알고리즘이 있는 것은 아니고, 그냥 지시한대로 구현을 하면 되는 문제입니다. 제가 다른 사람들한테 자주 물어본 수학 문제는 이런것이었습니다. 1000! (천 팩토리얼)을 계산하면 아주 큰 수가 나올거야. 그 수의 모든 자릿수를 다 더하면, 하나의 수가 되겠지. 이것을 계속 반복하면 결국 한자리 수가 나올텐데, 그 답은? 답은 당연하겠지만 9입니다. 3차리 수라고 하면, \(100a + 10b + c\)로 표현할 수 있습니다. 이것을 다시 분해하면, \(99a + 9b + a + b + c\)로 표현할 수 있죠. \(10^k - 1 \)은 9의 배수이므로, 주어진 3자리수가 9의 배수이면, \(a + b + c\)도 9의 배수가 됩니다. 팩토리얼은 6! 부터 9의 배수가 됩니다. 결국 .. 2022. 10. 15.
[C/C++] 백준 #1766 문제집(위상정렬) 이번 문제는 일을 처리하는데 있어서 우선순위가 주어진 경우 그것을 해결하는 방법입니다. 1. N개의 문제는 반드시 풀어야 한다. 2. 먼저 푸는 것이 좋은 문제가 있는 경우에는 더 쉬운 문제를 먼저 풀어야 한다. 3. 쉬운 문제가 있다면, 쉬운 문제를 먼저 풀어야 한다. 1번 조건과 2번 조건만을 보면 위상 정렬입니다. 3번 조건은 위상정렬을 할 때, 인입간선이 없는 것들중에 문제 번호가 적은 것을 우선 선택할 수 있도록, 문제 번호대로 우선순위 큐를 작성하면 됩니다. 그래서 위상정렬을 근간으로 우선순위 큐를 사용하면 됩니다. 저는 조금 다르게 작성하기는 했지만, 기본적인 취지는 비슷합니다. 아마 지금 작성했다면, 위에 설명한대로 작성했을 것 같네요. 제가 작성한 소스입니다. 소스는 참고용으로 봐주세요... 2022. 10. 15.
[C/C++] 백준 #1764 듣보잡(집합자료) 이번 문제는 집합 자료를 사용하면 쉽게 풀리는 문제입니다. 문제는 들어본 적이 없는 사람들의 리스트와 본적 없는 사람들의 리스트가 주어졌을 때, 듣보잡(들어보지도, 본적도 없는) 리스트를 구하는 것입니다. 그런데, 최종 리스트는 사전순으로 배열해야 합니다. 가장 간단한 방법을 두 집합을 만들고, 그 집합의 교집합을 구하는 방법이겠죠. 정렬된 리스트를 만들고 교집합을 만들면 알고리즘 효율은 \(O(N \log N + M \log M)\)이 됩니다. 정렬하는데 필요한 부분입니다. 정렬한 두개의 리스트에서 교집합 내용을 찾는 것은 \(O(N+M)\)이 되겠죠. 저는 두개의 집합을 이용했습니다. 첫번째는 해시집합이고, 두번째는 정렬집합입니다. 해시집합은 정렬되지는 않았지만, 삽입, 검색이 모두 \(O(1)\)인.. 2022. 10. 15.
[C/C++] 백준 #1761 정점들의 거리(최소 공통 조상) 트리에서 두 노드간 최소 거리를 구하는 방법은 여러가지가 있습니다. 가장 간단하게 생각할 수 있는 것은 깊이 우선 탐색(DFS) 이용하는 방법이 있겠죠. 하지만, 노드의 수가 많다면, 꽤 오랜 시간이 걸리겠지만, 크게 문제가 되지 않습니다. 노드의 개수가 N개라면, \(O(N)\) 알고리증으로 풀 수 있으니까요. 물론 재귀 호출의 깊이가 깊어지기 때문에 너비 우선 탐색(BFS)를 이용할 수도 있습니다. 하지만, 이번 문제는 단순하게 두 노드간의 거리를 한번 구하는 것이 아니고 M번 구하는 것입니다. 그러면, 알고리즘 효율이 \(O(NM)\)이 됩니다. 그렇기 때문에 보다 효율적인 알고리즘을 찾아야 합니다. 최소 공통 조상 알고리즘은 기본적으로 많은 질의(query)가 있는 경우 사용할 수 있습니다. 모든.. 2022. 10. 11.
[C/C++] 백준 #1759 암호 만들기(조합) 이번 문제는 조합을 이용하는 것입니다. 단지 조건이 좀 들어가 있습니다. 적어도 1개의 모음과 2개의 자음이 들어가야 합니다. 사실, 조합을 구한 다음에 모음의 개수를 세면, 그 외는 모두 자음이기때문에 손쉽게 풀 수 있습니다. 저는 재귀함수를 이용해서 풀었습니다. 모음의 개수를 따로 세어서 마지막에 검사를 했습니다. 재귀 함수를 사용하여 조합을 만들 수 있다면, 어렵지 않게 풀 수 있는 문제입니다. 암호의 길이가 길다면, 모음을 검사하는 비용이 클 수가 있기 때문에 주의가 필요하겠죠. 제가 작성한 소스입니다. 소스는 참고용으로 봐주세요. //------------------------------------------------------- // baekjoon #1759 - Making password.. 2022. 10. 11.
728x90

티스토리툴바