본문 바로가기
반응형

Programming401

[C/C++] 백준 #1812 사탕(수학) 이번 문제는 N명의 학생들이 있는데, 학생들이 원형으로 둘러 앉아있습니다. 각 학생들은 사탕을 가지고 있는데, 우리가 알고 있는 것은 이웃한 두 학생들의 사탕의 합만을 알고 있습니다. 이 때, N명은 홀수라는 것이 중요합니다. 이 문제는 N이 홀수가 아니라면 풀기 어려운 문제가 됩니다. 각 학생들이 가지고 있는 사탕의 개수를 \(c_i\)라고 하자, 그리고 \(c_i + c_{i+1}\)을 \(s_i\)라고 하자. 참고로 \(c_{N+1} = c_1\)로 규정하도록 한다. 그러면 다음과 같은 식을 만들 수 있다. \[ \sum_{i=1}^{N} (-1)^{i+1} s_i = 2c_1 \] 만약 짝수의 학생들이 있었다면, 위식은 0이 된다. 예를 들어서 5명의 학생이 사탕을 2, 3, 1, 4, 3개씩 가.. 2022. 10. 23.
[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.
728x90

티스토리툴바