이 영역을 누르면 첫 페이지로 이동
포렌식 & 개발 이야기 - Forensics & Development 블로그의 첫 페이지로 이동

포렌식 & 개발 이야기 - Forensics & Development

페이지 맨 위로 올라가기

포렌식 & 개발 이야기 - Forensics & Development

Pental - Forensics / iOS / Windows / Android / Kakaotalk / Telegram / Etc

[골드 2] 백준 1655 - 가운데를 말해요 (파이썬)

  • 2025.04.26 12:20
  • Programming/백준
글 작성자: pental

https://www.acmicpc.net/problem/1655

풀이

  • 매번 새로운 수를 입력받으면, 지금까지의 수 중에서 중간값을 출력해야 한다.
  • 수의 개수가 홀수이면, 정렬했을 때 가운데 수가 중간값이고
  • 수의 개수가 짝수이면, 가운데 두 수 중에서 작은 수가 중간값이다.
  • 왼쪽 힙 (left): 최대 힙. 중간값보다 작거나 같은 값 저장 (최댓값이 top)
  • 오른쪽 힙 (right): 최소 힙. 중간값보다 큰 값 저장 (최솟값이 top)

중간값 위치

  • 항상 left가 right보다 같거나 1개 많도록 유지하면,
  • 중간값은 left의 루트에 위치함 (-left[0])
heapq.heappush(left, -X)

우선 left (최대 힙)에 넣음 (-부호로 최대 힙을 구성)

if right and -left[0] > right[0]:
    heapq.heappush(right, -heapq.heappop(left))

조건 1 → left의 최대값 > right의 최솟값 일때 위치를 변경한다.

if len(left) < len(right):
    heapq.heappush(left, -heapq.heappop(right))
elif len(left) > len(right) + 1:
    heapq.heappush(right, -heapq.heappop(left))

조건 2 → 힙 크기 불균형을 조정한다

힙이 뭔가요?

<aside> ✅

완전 이진트리 기반의 특수한 자료구조

</aside>

항상 부모 노드가 자식 노드보다 크거나 작다는 규칙을 가지고 있음

타입 의미 예시 구조

최소 힙 (Min Heap) 부모 ≤ 자식 → 루트가 최솟값 heapq 기본
최대 힙 (Max Heap) 부모 ≥ 자식 → 루트가 최댓값 heapq에서는 음수로 구현

그럼 왜 쓰나요?

정렬된 상태가 필요 없고, 가장 큰 값/작은 값만 빠르게 꺼내고 싶을 때 사용한다.

최대힙은 어떻게 구현하나요?

heapq.heappush(max_heap, -x)
heapq.heappop(max_heap) * -1

Python의 heapq는 최소 힙만 지원하기 때문에, 음수를 이용해서 최대 힙을 흉내낸다.

예시는 다음과 같다.

입력 순서: 5, 2, 8, 1

heapq 상태: [1, 2, 8, 5]
→ 힙 구조로 보면:

       1
     /   \\
    2     8
   /
  5

항상 루트(1)가 가장 작음

코드

# 백준 1655 - 가운데를 말해요
# 분류 : 우선순위 큐
# 문제집 : 단기간 성장 - 2번

import sys
import heapq

input = sys.stdin.readline

left = []
right = []

N = int(input())
for i in range(N) :
    X = int(input())
    heapq.heappush(left, -X)

    if right and -left[0] > right[0] :
        heapq.heappush(right, -heapq.heappop(left))
    
    if len(left) < len(right) :
        heapq.heappush(left, -heapq.heappop(right))
    elif len(left) > len(right) + 1 :
        heapq.heappush(right, -heapq.heappop(left))

    print(-left[0])
저작자표시 비영리 (새창열림)

'Programming > 백준' 카테고리의 다른 글

[실버 2] 백준 11060 - 점프 점프 (파이썬)  (0) 2025.04.27
[실버 3] 백준 9657 - 돌 게임 3 (파이썬)  (0) 2025.04.27
[플레티넘 5] 백준 3197 - 백조의 호수 (파이썬)  (0) 2025.04.26
[골드 5] 백준 12919 - A와 B 2 (파이썬)  (0) 2025.04.26
[골드 2] 백준 2381 - 최대 거리 (파이썬)  (0) 2025.04.25

댓글

이 글 공유하기

  • 구독하기

    구독하기

  • 카카오톡

    카카오톡

  • 라인

    라인

  • 트위터

    트위터

  • Facebook

    Facebook

  • 카카오스토리

    카카오스토리

  • 밴드

    밴드

  • 네이버 블로그

    네이버 블로그

  • Pocket

    Pocket

  • Evernote

    Evernote

다른 글

  • [실버 2] 백준 11060 - 점프 점프 (파이썬)

    [실버 2] 백준 11060 - 점프 점프 (파이썬)

    2025.04.27
  • [실버 3] 백준 9657 - 돌 게임 3 (파이썬)

    [실버 3] 백준 9657 - 돌 게임 3 (파이썬)

    2025.04.27
  • [플레티넘 5] 백준 3197 - 백조의 호수 (파이썬)

    [플레티넘 5] 백준 3197 - 백조의 호수 (파이썬)

    2025.04.26
  • [골드 5] 백준 12919 - A와 B 2 (파이썬)

    [골드 5] 백준 12919 - A와 B 2 (파이썬)

    2025.04.26
다른 글 더 둘러보기

정보

포렌식 & 개발 이야기 - Forensics & Development 블로그의 첫 페이지로 이동

포렌식 & 개발 이야기 - Forensics & Development

  • 포렌식 & 개발 이야기 - Forensics & Development의 첫 페이지로 이동

검색

메뉴

  • 홈
  • 태그
  • 미디어로그
  • 위치로그
  • 방명록

카테고리

  • Category (452) N
    • Forensics (105)
      • Magnet AXIOM (28)
      • Digital Forensics Informati.. (9)
      • Iphone Forensics (24)
      • DFC (7)
      • 디지털포렌식전문가2급 자격증 (10)
      • FTK ACE 자격증 (7)
    • 이것저것 (7)
      • Ubuntu (6)
      • 디스코드 봇 (4)
      • Volatility GUI (2)
    • CTF (32)
      • NEWSECU (14)
      • CTF-d (5)
      • Puzzel - Network Forensics (2)
      • Security Traps (2)
      • system32.kr (5)
      • HMCTF (4)
    • Programming (260) N
      • C (10)
      • Python (11)
      • 백준 (206) N
      • 프로그래머스 (32)
    • 그냥 개발 및 잡담 (16)
      • Docker (2)
      • Google Cloud (3)
      • OS 개발 (3)
    • Best of Best (20)

최근 글

인기 글

댓글

공지사항

아카이브

태그

  • axiom
  • Forensics
  • 프로그래머스
  • 백준
  • 디지털포렌식
  • 포렌식
  • pental
  • 파이썬
  • 전체 보기…

정보

pental의 포렌식 & 개발 이야기 - Forensics & Development

포렌식 & 개발 이야기 - Forensics & Development

pental

블로그 구독하기

  • 구독하기
  • RSS 피드

방문자

  • 전체 방문자
  • 오늘
  • 어제

티스토리

  • 티스토리 홈
  • 이 블로그 관리하기
  • 글쓰기
Powered by Tistory / Kakao. Copyright © pental.

티스토리툴바