[C/C++] 백준 #1725 히스토그램(분할 정복)
히스토그램 문제는, 히스토그램 그래프에서 x축의 빈도의 너비와, y축의 값의 높이 단위 크기가 같을때, 히스토그램 그래프 안에 직사각형의 넓이가 최대가 되는 것을 구하는 문제입니다. 분할정복 문제의 전형적인 경우입니다. 예를 들어서 히스토그램의 값이 [ 3, 2, 3, 4, 2, 3, 4, 1 ]의 값을 가진다고 하면, 이를 히스토그램으로 표현하면 아래와 같습니다. 사람이 본다면 인지적으로 높이 2인 직사각형이 가장 넓을 것이라 할 수 있습니다. 하지만, 히스토그램의 x축 개수가 매우 많다면 사람이 인지적으로 판단하는 것도 힘듭니다. 컴퓨터가 푼다면, 높이 1인 것부터 차례로 찾아볼 수도 있습니다. 히스토그램의 1보다 큰 수가 얼마나 연속되었는지 찾으면 됩니다. 이것이 \(O(N)\) 알고리즘이니, 높이..
2022. 10. 5.
[C/C++] 백준 #1722 순열의 순서(수학)
이번 문제는 순열의 순서를 아는 것입니다. 순열 경우의 수는 N이 주어지면, \(N!\)로 아주 큰 수가 됩니다. 순열의 경우의 수가 팩토리얼이라는 것은 아주 중요합니다. 우리가 10진수를 생각한다면, N자리의 숫자는 \(10^N\)개의 경우의 수를 가집니다. 이를 이용하면, 우리가 주어진 수가 몇번째 10진수인지 아주 쉽게 구할 수 있습니다. 팩토리얼로 이루어진 수도 마찬가지라고 생각하면 됩니다. N이 4라면 만들 수 있는 순열 수는 24가지가 됩니다. 1234, 1243, 1324, 1342, 1423, 1432, 2134, 2143, 2314, 2341, 2413, 2431, 3124, 3142, 3214, 3241, 3412, 3421, 4123, 4132, 4213, 4231, 4312, 432..
2022. 10. 4.
