백준 1766 : 문제링크

• 문제유형

  • 탐색
  • 힙
  • 위상정렬

• 설명

  • 위상정렬
    1. 진입 차수가 0인 정점을 큐에 삽입
    2. 큐에서 원소를 꺼내 해당 원소와 간선을 제거
    3. 제거 이후 진입 차수가 0이 된 정점을 큐에 삽입
    4. 큐가 빌 때까지 2 ~ 3을 반복
  • 위상정렬 사용이유 : 2번 조건 - 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다.)
  • 힙 사용이유 : 3번 조건 - 가능하면 쉬운 문제부터 풀어야 한다

• 풀이

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

  import heapq n, m = map(int, input().split()) array = [[] for i in range(n + 1)] indegree = [0] * (n + 1) heap = [] result = [] for _ in range(m): x, y = map(int, input().split()) array[x].append(y) indegree[y] += 1 for i in range(n+1): if indegree[i] == 0: heapq.heappush(heap, i) result = [] while heap: data = heapq.heappop(heap) result.append(data) for y in array[data]: indegree[y] -= 1 if indegree[y] == 0: heapq.heappuh(heap, y) for i in result: print(i, end = ' ')

Comment and share

백준 1927 : 문제링크

• 문제유형 :

  • 탐색

  • 힙

• 설명

  • 파이썬에서 heapq 라이브러리를 이용하면 힙 구현 가능하다.

• 풀이

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

  import heapq n = int(input()) heap = [] result = [] for _ in range(n): data = int(input()) if data = 0: if heap: result.append(heapq.heappop(heap)) else: result.append(0) else: heapq.heappush(heap, data) for data in result: print(data)

Comment and share