목록2024/05/08 (2)
알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/1725 세그먼트 트리를 이용해 풀었습니다. N개의 직사각형의 높이가 주어졌을 때, 히스토그램에서 가장 넓이가 큰 직사각형을 구하는 문제입니다. 직사각형의 높이가 다를수 있기에, 붙어있는 직사각형들의 가장 높은 높이는 가장 직사각형의 높이가 될 것입니다.따라서, 이를 이용해 세그먼트 트리로 풀었습니다. 먼저, 트리에 가장 작은 높이의 위치를 저장해줬습니다.예를 들어, 자식 노드가 (2, 1)이라면, 1이 작은 높이이니 해당 노드는 높이가 1인 위치가 저장될 것입니다. 이렇게 트리에 작은 높이들의 위치가 저장이 되었다면, (0 ~ N-1) 범위에서 가장 넓이가 넓은 직사각형을 찾습니다.방법은 주어진 범위에서 가장 낮은 높이의 위치..

문제 링크입니다. https://www.acmicpc.net/problem/6549 세그먼트 트리를 이용해 푸는 문제입니다. N개의 직사각형의 높이가 주어졌을 때, 히스토그램에서 가장 넓이가 큰 직사각형을 구하는 문제입니다. 직사각형의 높이가 다를수 있기에, 붙어있는 직사각형들의 가장 높은 높이는 가장 직사각형의 높이가 될 것입니다.따라서, 이를 이용해 세그먼트 트리로 풀었습니다. 먼저, 트리에 가장 작은 높이의 위치를 저장해줬습니다.예를 들어, 자식 노드가 (2, 1)이라면, 1이 작은 높이이니 해당 노드는 높이가 1인 위치가 저장될 것입니다. 이렇게 트리에 작은 높이들의 위치가 저장이 되었다면, (0 ~ N-1) 범위에서 가장 넓이가 넓은 직사각형을 찾습니다.방법은 주어진 범위에서 가장 낮은 높이의..