<div id="readability-page-1" class="page"><div><h2 id="최소힙">최소힙</h2>
참고자료: <a href="https://www.inflearn.com/course/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8/lecture/27045?tab=curriculum&amp;speed=2">파이썬 알고리즘 문제풀이</a>
상기 강의 내용을 바탕으로 swift 코드로 바꿔서 요약 정리한 내용입니다.
<ul>
<li>문제</li>
</ul>
최소힙은 완전이진트리로 구현된 자료구조이다. 그 구성은 부모 노드의 값은 왼쪽자식과 오른쪽자식 노드의 값보다 작게 트리를 구성하는 것이다. 그렇게되면 트리의 루트 노드에는 항상 트리의 최소값이 위치한다. (1). 자연수가 입력되면 최소힙에 입력, (2). 0이 입력되면 최소값을 꺼내어 출력(값이 없으면 -1을 출력), (3). -1이 입력되면 프로그램이 종료되도록 프로그램을 작성하시오.
<ul>
<li>입력예제</li>
</ul>
5 
3 
6 
0 
5 
0 
2 
4 
0 
-1
<ul>
<li>출력예제</li>
</ul>
3 
5 
2
<h2 id="내-풀이">내 풀이</h2>
<pre><code>var a = [Int]()
while true {
 let n = Int(readLine()!)!
 if n == -1 { break }
 if n == 0 {
 if a.isEmpty {
 print(-1)
 } else {
 print(a.popLast()!)
 }
 } else {
 a.insert(n, at: 0)
 a.sort(by: &gt;)
 }
}
</code></pre>
swift는 파이썬과 달리 heap을 직접 구현해야하기 때문에 간단하게 sort를 활용하여 풀이를 진행하였다.
<h2 id="강의-풀이">강의 풀이</h2>
파이썬 코드에서는 heap을 import하여 풀이를 진행하였기 때문에 heap의 구현은 추후에 직접 코드를 작성하여 업로드할 예정이다.
<h2 id="파이썬-코드">파이썬 코드</h2>
<pre><code>import heapq as hq
a=[]
while true:
 n=int(input())
 if n==-1:
 break
 if n==0:
 if len(a)==0:
 print(-1)
 else:
 print(hq.heappop(a))
 else:
 hq.heappush(a, n)</code></pre>
파이썬은 없는게 없다...</div></div>

PS & Algorithm

WooSeok Suh

최소힙
참고자료: 파이썬 알고리즘 문제풀이
상기 강의 내용을 바탕으로 swift 코드로 바꿔서 요약 정리한 내용입니다.
문제
최소힙은 완전이진트리로 구현된 자료구조이다. 그 구성은 부모 노드의 값은 왼쪽자식과 오른쪽자식 노드의 값보다 작게 트리를 구성하는 것이다. 그렇게되면 트리의 루트 노드에는 항상 트리의 최소값이 위치한다. (1). 자연수가 입력되면 최소힙에 입력, (2). 0이 입력되면 최소값을 꺼내어 출력(값이 없으면 -1을 출력), (3). -1이 입력되면 프로그램이 종료되도록 프로그램을 작성하시오.
입력예제
5
3
6
0
5
0
2
4
0
-1
출력예제
3
5
2
내 풀이
var a = [Int]()
while true {
    let n = Int(readLine()!)!
    if n == -1 { break }
    if n == 0 {
        if a.isEmpty {
            print(-1)
        } else {
            print(a.popLast()!)
        }
    } else {
        a.insert(n, at: 0)
        a.sort(by: >)
    }
}
swift는 파이썬과 달리 heap을 직접 구현해야하기 때문에 간단하게 sort를 활용하여 풀이를 진행하였다.
강의 풀이
파이썬 코드에서는 heap을 import하여 풀이를 진행하였기 때문에 heap의 구현은 추후에 직접 코드를 작성하여 업로드할 예정이다.
파이썬 코드
import heapq as hq
a=[]
while true:
    n=int(input())
    if n==-1:
        break
    if n==0:
        if len(a)==0:
            print(-1)
        else:
            print(hq.heappop(a))
    else:
        hq.heappush(a, n)
파이썬은 없는게 없다...

자료구조 활용 - 힙(1)

댓글