Doby's Lab

https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 직전의 포스팅과 똑같은 문제다. https://draw-code-boy.tistory.com/203 [알고리즘] 백준 1725번: 히스토그램 (C++), 세그먼트 트리의 응용 https://www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의..

https://www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 www.acmicpc.net 이번 문제는 유난히 어려웠다. 처음에 떠올랐던 방법은 히스토그램의 높이 중 제일 작은 것을 골라서 전체 구간의 길이와 곱해준 값을 출력해줬었다. >> 차라리 이럴 거면 입력받을 때 최솟값을 구해서 구간과 곱해주는 건데 세그먼트 트리 문제라는 이유로 세그먼트 트리를 구한 게 멍청했다. 하지만, 이 방법이 안 되는 이유는 두 가지에서 떠올랐다. 어떤 높이가 0인 경우 >>..

이번 문제도 분할 정복이다. 다만 이번 문제는 2차원 배열을 사용하지 못한다. 32769 x 32769 사이즈의 배열을 선언해야 했어서 이는 엄청 크기 때문에 선언하지 못한다. 그래서 배열 없이 접근했다. '0행의 0열 0부터 시작' 같은 키워드는 이번 문제에서 유독 헷갈렸었기 때문에 행과 열은 1부터 시작하고 1부터 시작하게 하여 마지막 결과 값에 -1을 해주었다. 분할 정복 함수에서 각 사분면에 해당하는 조건들을 달고, 함수의 재귀를 거치면서 입력한 행렬과 함수의 도출 행렬이 같다면 함수를 종료하고, 해당하는 결과 값에 -1을 해준 뒤에 출력하고 함수를 종료시켰다. #include #include #include using namespace std; // 배열 사이즈가 너무 커진다. >> 꼭 배열을 ..

이번 문제는 첫 공식적인(?) 분할 정복 문제다. 의외로 간단하게 풀었었다. '다만 생각을 조금만 더 해볼 걸'이라는 아쉬움이 있었다. '설마 하나하나 다 검사하겠어'라는 생각에 한 번이라도 구현했으면 시간 아꼈을 텐데 포인트 이번 분할 정복의 포인트는 문제에서 얻을 수 있었다. n이 2의 제곱수로 주어지고, 색종이들 또한 2의 제곱수 형태로 존재하기 때문에 N / 2로 분할해나가면서 리커시브 콜을 하면 됐었다. 맨 위에서 말한 '설마 하나하나 다 검사하겠어'라는 생각을 구현하면 된다. 소스 코드 #include #include using namespace std; int n; int map[129][129] = { 0, }; int white = 0; // 0 int blue = 0; // 1 void..

이번 문제는 당연하게 나머지 정리(MOD의 연산)를 이용해 풀 수 있을 거라 생각했다. 왜냐하면 거듭제곱을 할수록 수는 기하급수적으로 엄청 커질 것이기 때문에 즉각적으로 이를 처리할 수 있는 나머지 정리를 사용하는 것이 필수적이라 생각했다. 하지만, 거듭제곱의 연산 또한 2,147,483,647 이하의 수가 주어지기 때문에 시간 초과를 발생시킬 것이라 확신했다. 어떠한 솔루션이 떠오르지 않았고, 이 문제는 '분할 정복을 이용한 거듭제곱' 이란 키워드로 분류되어있었기 때문에 분할 정복에 대해 알아보기로 했다. 이번 문제에서 사용된 나머지 정리 연산 규칙성 (A * B) mod N = (A mod N * B mod N) mod N 가정: 어떠한 값을 A라 두고, 나누는 수가 N이라고 했을 때 A mod N은..