SWEA 5177バイナリ臀部
問題のソースソフトウェアExpert Academy
問題の著作権は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
Reference
この問題について(SWEA 5177バイナリ臀部), 我々は、より多くの情報をここで見つけました https://velog.io/@wltn39/SWEA-5177-이진-힙テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol