내가 그때 이걸 알았더라면

1. 문제

https://www.acmicpc.net/problem/1012

문제에서는 밭의 가로, 세로 크기와 심어진 배추의 개수, 각 배추의 위치가 주어진다.

이때 배추들을 건강하게 키우기 위한 최소 배추흰지렁이 개수를 구하면 되는 문제이다.

2. 해결 아이디어

dfs, bfs 등을 이용하여 쉽게 해결할 수 있는 문제이다.

다만 이번 문제를 해결하면서 작은 문제를 마주쳐 그것에 대해 기록하려고 글을 쓴다...

3. 개선할 점

코드에서 전역으로 밭(field), visited 배열을 만들고, 문제에서 설정된 최대 밭 크기가 50*50이라 SIZE를 50으로 설정했는데, 계속 오류가 났다.

https://www.acmicpc.net/board/view/99434

그래서 질문글과 반례를 계속 찾아보던 중, 해당 글에서 배열의 크기를 51로 해서 통과되었다는 내용을 보고, 따라했더니 성공했다...

아니 이건 근데 억까가 아닌가...

앞으로 배열의 크기가 한정적인 경우(골드 이상에서)가 아니라면, 배열의 크기를 조금 널널하게 잡자.

그리고 아무 이유 없이 오류가 난다면

알고리즘 로직 체크 -> 변수 위치/이름 실수 -> 타입, 반복문 범위, 배열 인덱스 실수 ->.. -> 배열 크기나 변수 크기 늘려보기

순으로 시도해보자.

4. 코드

1.  문제

https://www.acmicpc.net/problem/6549

https://www.acmicpc.net/problem/1725

히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다.

히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오.

2. 아이디어

다음 블로그의 내용을 참조하였다.

https://cocoon1787.tistory.com/314

전반적인 알고리즘 아이디어는 다음과 같다.

1. 다음 사진과 같이 히스토그램 그림이 있을 경우, 세그먼트 트리를 이용해 전체 구간에서 가장 작은 높이의 인덱스를 구한다.

2. 구간의 길이(ed - st + 1) * 가장 작은 히스토그램의 높이 값(heights[minIdx - 1])을 구해 현재까지의 가장 큰 넓이(maxSize)와 비교해 만약 그 넓이보다 크다면 maxSize를 갱신한다.

3. 가장 작은 높이의 인덱스(minIdx)를 기준으로, 히스토그램을 두 구간으로 나누고, 재귀함수로 각 구간별로 2. 의 과정을 반복한다.

4. 만약 구간을 쪼갰을 때 넓이를 구할 수가 없다면 (st > ed로 1인 히스토그램에서 쪼개지는 경우) return한다.

알고리즘이 매우 단순해 처음에는 이걸로 해결할 수 있을지 모르겠지만, 재귀를 반복하다 보면, 결국 그림에서 3, 4번째 히스토그램과 같이 큰 히스토그램만 있는 구간에서 3번째 히스토그램이 가장 작은 높이(4)이므로 4 * 2 = 8로 이를 이용해 구간에서의 넓이를 구하게 된다.

또한, 엄청 높은 히스토그램 하나가 있는 경우에도, 그 막대의 높이 * 구간의 길이(1) = 그 막대의 높이 와 같이 그 막대의 높이를 그대로 사용하므로, 문제를 해결할 수 있다.

3. 개선할 점 및 배운점

특정 구간에서의 특정 값이 필요한 경우 -> 세그먼트 트리 자료구조 사용

부분 문제의 해를 재귀적으로 구하는 것이 전체 문제의 해와 관련이 있는 경우 -> 분할정복 알고리즘 사용

4. 코드