SWEA 5177 이진 힙
문제출처 SW Expert Academy
문제의 저작권은 SW Expert Academy에 있습니다.
문제소개
- N개의 서로 다른 자연수가 주어지면 입력 순서대로 이진 최소힙에 추가함
- 힙은 최소 또는 최대값을 루트로 설정하여 빠르게 연산하도록 고안된 트리구조
- 부모노드 < 자식노드 조건이 만족하도록 계속 부모 노드의 값을 바꿔줌
- 힙에 마지막 노드의 조상 노드에 저장된 정수의 합을 구하는 프로그램 작성
입력:
1
6 (N개의 숫자 입력)
7 2 5 3 4 6 (입력 순서대로 최소힙에 저장)
출력:
#1 7 (마지막 노드인 6의 조상 노드값인 5와 2가 더해짐)
풀이접근
- 리스트를 이용해 1~N 의 트리를 만듦
- 제일 왼쪽부터 규칙에 맞게 값을 넣어줌
코드
def min_heap(node):
up_node = node//2
if up_node < 0: # 루트노드에 도달하면 리턴
return # return 안하면 maxdepth exceed 나옴
else:
# 부모노드가 더 크면 위치 바꿔줌
if tree[up_node] > tree[node]:
tree[node], tree[up_node] = tree[up_node], tree[node]
min_heap(up_node) # 함수에 부모노드 대입해서 반복
for tc in range(1, int(input()) + 1):
N = int(input()) # 노드갯수
tree = [0]
node_num = 1
for num in map(int, input().split()):
tree.append(num)
min_heap(node_num)
node_num += 1
sum_value = 0
while N: # N(마지막)노드의 조상노드 값들 더함
N //= 2
sum_value += tree[N]
print(f'#{tc} {sum_value}')
1
6
7 2 5 3 4 6
#1 7
정의된 변수 값 확인
tree
[0, 2, 3, 5, 7, 4, 6]
node_num
7
Author And Source
이 문제에 관하여(SWEA 5177 이진 힙), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@wltn39/SWEA-5177-이진-힙저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)