크래프톤 정글 week02, day15 - 힙(heap), 알고리즘 문제

힙(heap)

• 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 하는 자료구조
• 특징
  • a가 b의 부모노드면 a의 키값과 b의 키값 사이에는 대소 관계가 성립한다.
  • 최소 힙 : 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙
  • 최대 힙 : 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙

​

힙 자료구조

• 파이썬 힙 모듈은 heapq라는 알고리즘 라이브러리를 제공
  • 내장 모듈이기 때문에 설치할 필요없이 사용가능
• 모든 부모 노드는 자식 노드보다 값이 작거나 큰 이진 트리 구조인데, 내부적으로는 인덱스 0에서 시작해 n번 째 원소가 항상 자식 원소들보다(2n+1, 2n+2)보다 작거나 최소 힙의 형태로 정렬
• 기능
  • heapq.heappush(heap, item) : item을 heap에 추가

import heapq

# -------------힙 넣기------------------
heap = []
heapq.heappush(heap, 50)
heapq.heappush(heap, 10)
heapq.heappush(heap, 20)

print(heap)

# 출처 : https://littlefoxdiary.tistory.com/3

 

• heapq.heapify(x) : 리스트 x를 heap으로 변환한다.

# ------------힙 변환-------------------
heap2 = [50, 10, 20]
heapq.heapify(heap2)

print(heap2)

# 출처 : https://littlefoxdiary.tistory.com/3

 

• heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴. 비어있을 땐 indexError가 호출

# ------------힙 삭제-------------------
result = heapq.heappop(heap)

print(result)
print(heap)

출처 : https://littlefoxdiary.tistory.com/3

 

 

최대 힙 구현

• 파이썬의 heapq 라이브러리에는 최소 힙으로 설정되어 있기 때문에 기능을 사용할 때 값에 -를 붙여줘야 한다.

import heapq

def heapsort(iterable):
    # 힙 정렬 리스트
    h = []
    # pop한 리스트
    result = []

    # 입력된 리스트를 반복해
    for value in iterable:
        # heqppush를 이용해서 h에 값을 넣기
        heapq.heappush(h, -value)

    # h의 길이만큼 반복하며
    for i in range(len(h)):
        # result 리스트에 heappop한 순서대로 넣기
        result.append(-heapq.heappop(h))
    return result

result = heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
print(result)

# 출처 : https://www.youtube.com/watch?v=F-tkqjUiik0

 

---

DFS, BFS

• 노드와 노드의 연결 값을 입력받고 DFS(깊이 우선 트리), BFS(너비 우선 트리)로 출력한다.

from collections import deque
import sys

# 깊이 우선 탐색
def dfs(graph, v, visited):
    # 방문확인을 True로 하고 시작노드인 v 출력
    visited[v] = True
    print(v, end=' ')
    # 시작노드의 연결노드를 확인해서 만약 방문 안한 노드가 있으면
    for i in graph[v]:
        if not visited[i]:
            # 재귀 시작
            dfs(graph, i, visited)

# 너비 우선 탐색
def bfs(graph, start, visited):
    # 데큐를 이용해 시작노드를 큐에 저장
    queue = deque([start])
    # 시작노드의 방문확인을 True로 하고
    visited[start] = True
    # 큐가 없을 때까지 무한 반복을 돌려서 
    while queue:
        # 큐는 맨 앞에 있는 값부터 차례대로 뺴기 떄문에
        # 앞의 걸 뺴는 popleft 데큐 기능 사용
        v = queue.popleft()
        print(v, end=' ')
        # 시작노드의 연결노드를 확인해서 만약 방문 안한 노드가 있으면
        for i in graph[v]:
            if not visited[i]:
                # 큐에 넣고 방문확인을 True로 변경
                queue.append(i)
                visited[i] = True

# 노드 개수(n), 간선 개수(m), 시작 노드(v)
n, m, v = map(int, sys.stdin.readline().split())
# 각 노드별로 연결된 부분을 찾기 위해 빈 2차원배열 생성
graph = [[] for _ in range(n+1)]
# 방문유무를 노드개수+1해서 0번쨰는 사용하지않고 1번째부터 사용
visited = [False] * (n+1)

# 입력된 노드연결을 입력해야해서 간선의 수만큼 반복
for _ in range(m):
    # 시작노드 a, 연결노드 b 받고 양방향 그래프이기 때문에 둘다 값 추가
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

# 노드마다 연결된 노드 리스트를 오름차순으로 정렬
for i in range(n+1):
    graph[i].sort()

# 깊이우선탐색(노드연결리스트, 시작 노드, 방문확인)
dfs(graph, v, visited)
# 너비우선탐색을 위해 방문확인 다시 초기화하고 띄어쓰기 위해 공백출력
visited = [False] * (n+1)
print()
# 너비우선탐색(노드연결리스트, 시작 노드, 방문확인)
bfs(graph, v, visited)

 

연결요소 개수

• 노드와 노드의 연결값을 입력받아 트리를 확인하고 연결 요소가 몇 개인지 확인하기

import sys


def line_connect(n, visited, line):
    # 방문확인을 true값으로 변경
    visited[n] = True

    # 노드배열을 돌며 방문이 false인 곳이 있으면 재귀를 돌려 true로 변경
    for i in line[n]:
        if not visited[i]:
            line_connect(i, visited, line)

# 노드 n, 간선 m, 방문확인 전부 false, 선 연결 배열 빈배열로 만들기line, 요소 개수c
n, m = map(int, sys.stdin.readline().split())
visited = [False] * (n+1)
line = [[] for _ in range(n+1)]
cnt = 0

# 간선의 개수만큼 a, b에 노드 입력, 노드1에 5가 연결이면 5에도 1이 연결되야 하기 때문에 둘다 적용
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    line[a].append(b)
    line[b].append(a)

# 모든 노드를 반복하며 방문이 안된 노드가 있으면 cnt를 1 증가
for i in range(1, n+1):
    if not visited[i]:
        line_connect(i, visited, line)
        cnt += 1

print(cnt)

 

 

학습시간 : 10 ~ 26시