김낭만

재밌거나 필요하다고 생각하는 걸 만듭니다.

백준(BOJ) 1725 히스토그램 파이썬(Python)

문제 링크

유명한 히스토그램 문제.
스택을 이용한 풀이와 세그먼트 트리 및 분할정복을 이용한 풀이가 있는데, 스택을 활용했다.
기본적인 아이디어는, 결국 넓이가 최대인 사각형은 최대 n개의 높이를 가지는 사각형들 중 가장 큰 것이라는 점이다.
히스토그램을 순회하면서 스택에 막대를 넣는다.
이때, 막대들은 히스토그램에서의 인덱스로 표현된다(그래야 각 막대의 시작 지점을 알 수 있으므로).
만약 탑보다 더 작은 막대가 들어오면, 그 막대를 높이로 하는 사각형은 더이상 커질 수가 없다.
따라서 팝하여 넓이를 계산해주고, 이를 반복하면 된다.
마지막에 스택에 남은 막대들은 너비가 히스토그램 전체인 경우이므로 따로 계산해주면 된다.

#!python

from sys import stdin
input = stdin.readline


n = int(input())
his = [int(input()) for _ in range(n)]
stack = []
ans = 0

# 히스토그램을 순회함
for i in range(n):
    while 1:
        # 만약 스택이 비었거나 새로운 막대가 더 크다면 스택에 막대를 넣는다
        if not stack or his[stack[-1]] <= his[i]:
            stack.append(i)
            break
        # 그렇지 않은 경우 그렇게 될 때까지 스택에서 막대를 꺼내 넓이를 계산한다
        r = i - 1
        c = stack.pop()
        l = 0 if not stack else stack[-1] + 1
        ans = max((r - l + 1) * his[c], ans)

# 마지막에 스택에 남은 막대의 넓이 계산
for i, e in enumerate(stack):
    r = n - 1
    l = 0 if not i else stack[i - 1] + 1
    ans = max((r - l + 1) * his[e], ans)

print(ans)

2024

맨 위로 이동 ↑

2023

세그먼트 트리

개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...

벨만-포드 알고리즘

개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...

다익스트라 알고리즘

개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...

맨 위로 이동 ↑