분할 정복3 [백준] 1725: 히스토그램 - JAVA https://www.acmicpc.net/problem/1725 풀이각 칸들의 높이가 주어지고, 내부에 가장 큰 직사각형을 구하는 문제이다. 아랫변을 구간으로 나눠 그 구간으로 이룰 수 있는 직사각형의 넓이를 비교해주었다. 세그먼트트리에는 구간별로 최소 높이를 갖는 인덱스를 저장해주었다. 구간으로 탐색할 때 인덱스를 기준으로 나누기 위함이다. (1, N)구간에서 넓이를 구하면 밑변은 (N - 1 + 1)이 되고, 높이는 해당 구간의 최소 높이를 세그먼트트리에서 찾아주면 된다. 이렇게 구한것이 해당 구간에서 만들수있는 직사각형의 최대이다. 위에서 찾은 최소 높이의 인덱스를 idx라고 하면 (1, idx - 1), (idx + 1, N)으로 나누어 계속 진행한다. 메모리: 39272KB시간: 356ms언.. 2024. 5. 14. [백준] 11582: 치킨 TOP N - JAVA https://www.acmicpc.net/problem/11582 풀이구간을 나눠 정렬해주면 되는 간단한 문제였다. N/k 길이 씩 구간을 정해 그 구간을 정렬하여 출력한다. 임시로 배열이나 리스트를 만들고 구간의 값을 넣은 뒤 정렬해주었다. 임시로 저장할 공간을 만들 때 세가지 경우를 실험해 보았다. 1. 배열을 매번 새로 선언. 2. 리스트를 전역으로 선언하고 매번 list를 clear. 3. 리스트를 매번 새로 선언. 배열을 매번 선언하는 것이 메모리, 시간이 모두 적게 나왔다. 리스트의 clear를 이용하는 것보다 매번 선언하는 것이 시간이 적게 걸렸다. 리스트의 clear함수는 리스트를 돌면서 null로 채우는 방식인데 list의 사이즈가 클 때는 clear보다 새로 선언하는 것이 더 빠르다... 2024. 5. 11. [백준] 4256: 트리 - JAVA https://www.acmicpc.net/problem/4256 풀이트리구조의 개념과 재귀를 물어보는 문제였다. 트리의 전위순회, 중위순회한 결과를 알려주고 후위순회한 결과를 찾아야한다. 전위순회: root -> left -> right 중위순회: left -> root -> right 후위순회: left -> right -> root 전위순회에서 맨 앞의 값이 후위순회에서의 맨 마지막 값이 된다. 전위순회의 맨 앞의 값을 중위순회에서 찾아 left그룹과 right그룹으로 나눠 재귀 탐색을 한다. 메모리: 157856KB시간: 644ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main.. 2024. 5. 11. 이전 1 다음