Programming456 백준 #1849 순열(세그먼트 트리) 이번 문제는 N개의 배열에 1부터 N까지 한번씩만 숫자가 써져있는 a[i] 수열이 있을경우, A[i] 란 수열은 원래의 수열에서 i번째 수의 앞에 있는 수 중 i보다 큰 값이 있는 개수가 됩니다. 예를 들어서 원래의 수열이 2 7 3 5 4 1 8 6 이라고 한다면, 1 앞에 있는 숫자 중 1보다 큰 숫자는 5개가 있다, 2 앞에 있는 숫자는 없으므로 0이 됩니다. 그래서 만들어진 A[i] 수열은 5 0 1 2 1 2 0 0 이 됩니다. 문제는 A[i] 수열로부터 원래의 수열을 찾는 것입니다. i 값이 1인 경우는 간단하게 6번째 칸에 1이 존재한다는 것을 알 수 있습니다. 1 다음에는 2의 숫자의 위치입니다. 2의 숫자는 0이므로 가장 앞에 존재하겠죠. 2 1 다음은 3인데, 이 값은 1입니다. 이미 .. 2022. 10. 25. [C/C++] 백준 #1822 차집합(집합) 이번 문제는 집합 자료를 사용하면 쉽게 풀리는 문제입니다. 집합자료는 해시를 사용하는 해시 집합과 이진트리를 이용한 이진트리 집합이 있습니다. 이 문제에 있어서는 어떤 집합 자료 구조를 사용하든지 크게 문제는 없습니다. 제 경우에는 이진트리 집합을 사용했습니다. A 집합을 만든다음에, B에 속하는 원소가 A 집합에 있는 경우 삭제를 했습니다. 그러면 A집합에는 차집합이 남아있게 됩니다. 제가 작성한 소스입니다. 소스는 참고용으로 봐주세요. //------------------------------------------------ // baekjoon #1822 // - by Aubrey Choi // - created at 2019-08-19 //--------------------------------.. 2022. 10. 23. [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. 이전 1 ··· 27 28 29 30 31 32 33 ··· 76 다음 728x90
