반응형 백준144 [C/C++] 백준 #1806 부분합(두 포인터) 이번 문제는 두개의 포인터를 운용해서 푸는 방법입니다. 부분합인데 연속된 수열의 부분합이란 점이 문제를 푸는데 있어서 중요합니다. 예를 들어서 1 3 2 4 7 8 3 6 이란 수열이 있다고 하죠. 여기서 부분합이 20이상일 때 최소의 N을 구하도록 하면요. 처음부터 누적하여 부분합이 20이 넘는 곳을 찾습니다. 1 3 2 4 7 8 3 6 1 4 6 10 17 25 그러면 8에서 멈추게 되는데, 이 때부터는 앞에서부터 하나씩 제거해서 20 미만이 되는 시점을 찾습니다. 그러면 4의 숫자에서 멈추게 됩니다. 여기서 다시 오른쪽 숫자를 포함하면서 20 이상이 되는 지점을 찾습니다. 왜 앞에서부터 다시 안 찾는가하면, 이미 바로 앞의 숫자를 포함하고 뒤의 숫자를 포함하는 것은 의미가 없기 때문입니다. 최소의.. 2022. 10. 22. [C/C++] 백준 #1790 수 이어쓰기 2(수학) 수를 그냥 있는 그대로 이어쓰기를 하면 자릿수가 늘어나면서 수 하나당 2개, 3개씩 숫자가 쓰여질겁니다. 이것만 체계적으로 잘 정리하면 풀 수 있는 문제입니다. 한자리 숫자의 개수는 9개, 두자리 숫자의 개수는 90개, 세자리 숫자의 개수는 900개로 k개의 자릿수의 숫자는 \(9 \times 10^{k-1}\)로 표현할 수 있습니다. 이것만 알면 손쉽게 문제를 풀 수 있습니다. 제가 작성한 소스입니다. 소스는 참고용으로 봐주세요. //------------------------------------------------------ // baekjoon #1790 - Making number with serial numbers 2 // - by Aubrey Choi // - created at 2019-.. 2022. 10. 22. [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. 이전 1 2 3 4 5 6 7 8 ··· 24 다음 728x90
