본문 바로가기

Programming/BOJ277

[C/C++] 백준 #1789 수열의 합(수학) 서로 다른 수들로 이루어진 수열의 합을 원하는 값으로 맞추는 방법은 아주 다양하게 있을겁니다. 그런데, 참여하는 수의 갯수를 최대한으로 하기 위해서는 참여하는 수가 작을 수록 좋겠죠. 이 문제를 풀기 위해서는 바로 이 방법을 사용했습니다. \[ N(N+1)/2 \le S \] 위의 식을 만족하는 최대의 N을 구하면 되겠죠. 근의 공식을 이용하면 쉽게 N의 범위를 구할 수 있습니다. \[ N \le \frac{1 + \sqrt{1+8S}}{2} \] 오른쪽항은 정수일수도 아닐 수도 있지만, N은 정수여야 하므로, 오른쪽항의 값의 정수값을 구하면 됩니다. 다음은 제가 작성한 소스입니다. 소스는 참고용으로 봐주세요. //--------------------------------------------------.. 2022. 10. 22.
[C/C++] 백준 #1788 피보나치 수의 확장(수열) 피보나치 수열은 보통 0 이상의 항에 대해서 다루고 있습니다. \[ F(0) = 0, F(1) = 1 \] \[ F(n) = F(n-1) + F(n-2) \] 형태의 점화식을 사용합니다. 음수항의 경우에도 그대로 적용될 수 있습니다. \(F(-1)\) 값은 \(F(-1) + F(0) = F(1)\)을 만족해야 하기 때문에 1의 값을 가집니다. 마찬가지로 \(F(-2)\) 값은 -1의 값을 가집니다. 0 이상의 항이 0 이상의 값을 항상 가지는데 비해, 음수항들은 음수값을 가지는 경우가 발생합니다. 사실 피보나치 수의 경우 일반적으로 푸는 방식은 차례대로 풀어나가는 것입니다. 최대항의 절대값이 백만정도이므로, 순차적으로 계산해도 크게 문제가 되지 않습니다. 알고리즘 효율은 \(O(N)\)이기 때문이죠. 그.. 2022. 10. 21.
[C/C++] 백준 #1786 찾기(KMP) 이번 문제는 주어진 문자열에서 패턴 문자열을 모두 찾는 알고리즘을 작성하는 것입니다. 워드 프로세스 뿐 아니라, 이런 문제는 아주 다양한 곳에서 사용되고 있습니다. 서버에서도 기본적으로 문자열을 찾기 위해서 사용할 수 있는 것이라서, 해당 알고리즘을 알고 있으면 좋습니다. 전 이 물제를 풀기 위해서 KMP 알고리즘을 사용했습니다. KMP 알고리즘이 구현하기 쉬워서 적용한 것은 아니고, 현재 사용할 수 있는 알고리즘 중에는 뛰어난 성능을 보여주는 알고리즘 중 하나이기 때문입니다. KMP 알고리즘은 크게 두 부분으로 나누어집니다. 하나는 문자열 매칭에 실패했을 경우 건너띄는 pi 배열을 만드는 것이고, 다른 하나는 이 pi 배열을 이용해서 문자열에서 해당 패턴을 찾는 부분입니다. pi 배열을 만드는 방법과 .. 2022. 10. 21.
[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.
728x90

티스토리툴바