# 가장 인상적이었던 문제
약 10개월 전, 이 문제와 관련해서 떠올리고 구현할 수 있는 접근 방식이 '2차원 배열로 좌표평면 나타내기'뿐이던 그때, 괜히 도전했다가 왠지 모를 무력감을 느끼곤 했다. 2차원 배열로 10만 범위의 x축, 10억 범위의 y축을 구현하고, 완전 탐색으로 최대 넓이를 찾는 작업을 하려면, 1초는 고사하고 1주의 시간으로도 모자라기 때문에 어나더레벨이라 판단하고 일단 돌아설 수밖에 없었다.
약 1개월 전, 세그먼트 트리를 처음 접했다. 사흘 전, 희소 테이블이 탐색 작업을 효율적으로 만들어주는 것과 비슷한 맥락에서, 이 문제에서의 탐색 작업을 최적화하는 데 세그먼트 트리가 사용될 수 있으리라 판단하고 도전해 볼 수 있었다. 고등학교 때 수학 선생님이 "이진수는 알면 알수록 정말 놀라운 거다"라는 말씀을 하셨던 게 떠올랐다. 그 말씀이 대뇌의 전두엽으로 와 닿는 경험이었다.
지금 내 능력으로 가능성을 판단하는 것은, 말 그대로 예단일 뿐이라는 것을 다시금 확인한다.
삽질 과정
더보기
"""
[Sol1]
아.. 이렇게 풀면 시간 초과가 확실하다.
heights = [1, 2, 3, 4, 5, ... , 10만]
이같은 케이스가 주어지면 시간 복잡도가 O(N^2)이 된다.
1. 최솟값, 최댓값 세그먼트 트리를 만들어 놓자.
2. 1번 노드부터 층별 순회를 하면서 해당 구간을 포함하고 해당 최솟값을 높이로 하는 직사각형의 너비를 계산한다.
3. 직사각형의 너비 계산 작업 (NEXT NODE: 형제 또는 친척 노드)
1) if 해당 최솟값 > NEXT NODE의 최댓값
해당 NEXT NODE에서 탐색을 멈춘다
2) while 해당 최솟값 <= NEXT NODE의 최솟값
해당 NEXT NODE를 너비에 포함시키고 다음 NEXT NODE를 탐색한다
3) else (해당 최솟값 > NEXT NODE의 최솟값)
NEXT NODE의 단측(왼쪽/오른쪽) 하부 노드를 단말 노드까지 탐색하면서
(해당 최솟값 <= 탐색 노드의 최솟값)이 될 때 그 노드를 포함시키고 탐색을 중단한다
4. 중복 탐색 방지를 위한 작업
1) 직사각형의 너비에 포함되는 노드를 visit 처리한다.
2) visit 처리- dict {최솟값: set(노드 번호)}
3) 방문하는 모든 노드에 대해 그 노드 번호가 0이 될 때까지 비트시프트 연산 >> 1 을 했을 때
dict[최솟값]의 집합에 포함되는 번호가 하나라도 나온다면 중복 탐색이므로 제외한다.
"""
"""
[Sol2]]
이렇게 풀면 시간 복잡도가 O(NlogN)이 된다.
1. 최솟값, 최댓값 세그먼트 트리를 만들어 놓자.
2. 모든 단말 노드[FIRST_LEAF:FIRST_LEAF+n]에 대해, 해당 최솟값을 높이로 하는 직사각형의 너비를 계산한다.
1) 해당 높이 이상의 최솟값을 갖는 최상위 세그먼트 segMid를 찾는다.
2) segMid의 양측 세그먼트 각각의 서브트리 중 해당 높이 이상의 최솟값을 갖는 최상위 누적 세그먼트 segLeft, segRight를 찾는다.
(1) 재귀적으로 찾는다: 최상위 세그먼트가 발견되면 그 너비를 추산한다
+ 단측 세그먼트의 하위 세그먼트 중 해당 높이 이상의 최솟값을 갖는 최상위 누적 세그먼트를 찾는다.
(2) 이때 양측 및 단측 세그먼트의 최댓값이 높이보다 작을 경우 탐색을 중단한다.
3) 직사각형의 너비 = segLeft + segMid + segRight
4) 이때 양측 세그먼트를 찾을 때 양쪽 끝 노드를 방문하는 경우를 따로 고려해야 한다.
"""
import sys
from math import ceil, log2
from typing import List
sys.setrecursionlimit(int(1e5))
def input():
return sys.stdin.readline().rstrip()
def main():
def make_seg_tree(seg_tree: List[int], is_min_seg: bool):
seg_tree.extend([0] * TREE_SIZE)
for idx, height in enumerate(heights, start=FIRST_LEAF):
seg_tree[idx] = height
if is_min_seg:
for idx in range(n - 1, 0, -1):
seg_tree[idx] = min(seg_tree[2*idx], seg_tree[2*idx+1])
else:
for idx in range(n - 1, 0, -1):
seg_tree[idx] = max(seg_tree[2*idx], seg_tree[2*idx+1])
def get_len(idx: int) -> int:
return 1 << (LOG - len(bin(idx)) + 2)
def get_left(idx: int, height: int) -> int:
if idx & (idx - 1) == 0 or max_seg[idx - 1] < height:
return 0
idx -= 1
while idx < TREE_SIZE and min_seg[idx] < height:
idx <<= 1
idx = idx >> 1 if idx >= TREE_SIZE else idx
return get_left(idx, height) + get_len(idx)
def get_right(idx: int, height: int) -> int:
if idx & (idx + 1) == 0 or max_seg[idx + 1] < height:
return 0
idx += 1
while idx < TREE_SIZE and min_seg[idx] < height:
idx <<= 1
idx = idx >> 1 if idx >= TREE_SIZE else idx
return get_len(idx) + get_right(idx, height)
def get_width(idx: int, height: int) -> int:
while (idx >> 1) >= 1 and min_seg[idx >> 1] >= height:
idx >>= 1
return get_left(idx, height) + get_len(idx) + get_right(idx, height)
def get_large_area() -> int:
return max([height * get_width(idx, height) for idx, height in enumerate(heights, start=FIRST_LEAF)])
while True:
n, *heights = map(int, input().split())
if n == 0:
return
LOG = ceil(log2(n)) + 1
TREE_SIZE = 1 << LOG
FIRST_LEAF = TREE_SIZE >> 1
min_seg, max_seg = [], []
make_seg_tree(min_seg, True)
make_seg_tree(max_seg, False)
print(get_large_area())
if __name__ == '__main__':
main()
완성 풀이
더보기
"""
[Sol3]
이번엔 정말 확실하게 O(NlogN)이다.
1. 최솟값 세그먼트 트리를 만들어 놓자.
2. 모든 단말 노드[FIRST_LEAF:FIRST_LEAF+n]에 대해, 해당 최솟값을 높이로 하는 직사각형의 너비를 계산한다.
1) 단말 노드를 기준으로 직사각형의 왼쪽 끝점과 오른쪽 끝점을 찾는다.
(1) 왼쪽은 (idx-1), 오른쪽은 (idx+1) 부터 탐색 시작.
(2) 양측 탐색 모두 각각 min_seg[idx] < height이 될 때까지,
좌측 탐색은 idx -= 1, idx >>= 1
우측 탐색은 idx += 1, idx >>= 1
(3) 좌측 탐색에서는 오른쪽 자식부터 min_seg[idx] >= height 여부를 확인하며,
min_seg[idx] < height인 노드에 대해 같은 작업을 재귀적으로 한다. (반복문으로 구현하자)
(4) 우측 탐색에서는 왼쪽 자식부터 min_seg[idx] >= height 여부를 확인하며,
min_seg[idx] < height인 노드에 대해 같은 작업을 재귀적으로 한다. (반복문으로 구현하자)
(5) 작업 (3),(4)에서 단말 노드에 도착할 경우 그 idx값을 반환한다.
2) 이때 양쪽 끝점을 찾을 때 각 층의 양쪽 끝 노드를 방문하는 경우를 따로 처리해야 한다.
3) 직사각형의 너비 = right_idx - left_idx + 1
"""
import sys
from math import ceil, log2
def input():
return sys.stdin.readline().rstrip()
def main():
def make_min_seg_tree():
for idx, height in enumerate(heights, start=FIRST_LEAF):
min_seg[idx] = height
for idx in range(FIRST_LEAF - 1, 0, -1):
min_seg[idx] = min(min_seg[idx << 1], min_seg[(idx << 1) + 1])
def get_leftbound(idx: int, height: int) -> int:
if idx & (idx - 1) == 0 or min_seg[idx-1] < height:
return idx
last_idx = idx
idx -= 1
while idx >= 1:
last_idx = idx
if min_seg[idx] < height or idx & (idx - 1) == 0:
break
idx -= 1
idx >>= 1
idx = (last_idx << 1) + 1
while idx < TREE_SIZE:
if min_seg[idx] >= height:
idx -= 1
idx = (idx << 1) + 1
idx >>= 1
return idx if min_seg[idx] >= height else idx + 1
def get_rightbound(idx: int, height: int) -> int:
if idx & (idx + 1) == 0 or min_seg[idx+1] < height:
return idx
last_idx = idx
idx += 1
while idx >= 1:
last_idx = idx
if min_seg[idx] < height or idx & (idx + 1) == 0:
break
idx += 1
idx >>= 1
idx = last_idx << 1
while idx < TREE_SIZE:
if min_seg[idx] >= height:
idx += 1
idx = idx << 1
idx >>= 1
return idx if min_seg[idx] >= height else idx - 1
def get_width(idx: int, height: int) -> int:
return get_rightbound(idx, height) - get_leftbound(idx, height) + 1
def get_large_area() -> int:
return max([height * get_width(idx, height) for idx, height in enumerate(heights, start=FIRST_LEAF)])
while True:
n, *heights = map(int, input().split())
if n == 0:
return
LOG = ceil(log2(n)) + 1
TREE_SIZE = 1 << LOG
FIRST_LEAF = TREE_SIZE >> 1
min_seg = [0] * TREE_SIZE
make_min_seg_tree()
print(get_large_area())
if __name__ == '__main__':
main()'내가 가는 여정을 담는 그릇' 카테고리의 다른 글
| 백준 다이아까지 3걸음 (0) | 2022.06.23 |
|---|---|
| 2022 Kakao Tech Internship 1차 코딩 테스트 후기 (0) | 2022.05.07 |
| 2022년 LG전자 VS연구소 SW R&D 신입사원 채용 - 코딩 테스트 후기 (0) | 2022.04.09 |
| [나의 작은 프로그래밍] TodoTracker (v.1.2.2) (0) | 2022.04.04 |
| 드.디.어! (0) | 2022.03.29 |