문제:

민오는 1번부터 N번까지 총 N개의 문제로 되어 있는 문제집을 풀려고 한다. 문제는 난이도 순서로 출제되어 있다. 즉 1번 문제가 가장 쉬운 문제이고 N번 문제가 가장 어려운 문제가 된다.

어떤 문제부터 풀까 고민하면서 문제를 훑어보던 민오는, 몇몇 문제들 사이에는 '먼저 푸는 것이 좋은 문제'가 있다는 것을 알게 되었다. 예를 들어 1번 문제를 풀고 나면 4번 문제가 쉽게 풀린다거나 하는 식이다. 민오는 다음의 세 가지 조건에 따라 문제를 풀 순서를 정하기로 하였다.

  1. N개의 문제는 모두 풀어야 한다.
  2. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다.
  3. 가능하면 쉬운 문제부터 풀어야 한다.

예를 들어서 네 개의 문제가 있다고 하자. 4번 문제는 2번 문제보다 먼저 푸는 것이 좋고, 3번 문제는 1번 문제보다 먼저 푸는 것이 좋다고 하자. 만일 4-3-2-1의 순서로 문제를 풀게 되면 조건 1과 조건 2를 만족한다. 하지만 조건 3을 만족하지 않는다. 4보다 3을 충분히 먼저 풀 수 있기 때문이다. 따라서 조건 3을 만족하는 문제를 풀 순서는 3-1-4-2가 된다.

문제의 개수와 먼저 푸는 것이 좋은 문제에 대한 정보가 주어졌을 때, 주어진 조건을 만족하면서 민오가 풀 문제의 순서를 결정해 주는 프로그램을 작성하시오.

입력:

첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주어진다. 이는 A번 문제는 B번 문제보다 먼저 푸는 것이 좋다는 의미이다.

항상 문제를 모두 풀 수 있는 경우만 입력으로 주어진다.

출력:

첫째 줄에 문제 번호를 나타내는 1 이상 N 이하의 정수들을 민오가 풀어야 하는 순서대로 빈칸을 사이에 두고 출력한다.

풀이방법:

이 문제는 '사이클'이 없으며 '방향'만 존재하는 그래프에서 정점을 나열하는 방법으로 풀 수 있다. 이러한 문제 푸는 방법을 위상 정렬 (Topological Sort)라고 한다.

 또한 시간을 최소화하기 위해서 최소 힙을 사용한 우선순위 큐를 사용하도록 한다. 문제는 다음과 같은 알고리즘 순서로 해결한다.

 

1. 정점과 연결된 그래프와 해당 정점과 연결된 정점의 개수 리스트를 만든다.

2. 연결된 정점 개수 리스트(In_degree)가 없는 정점부터 먼저 최소 힙에 넣어준다.

3. 해당 정점과 연결되어 있는 정점(In_degree)들부터 하나씩 제거해 준다.

4. 연결된 정점 개수가 없는 정점이 생긴다면 최소 힙을 다시 넣어준다. 이후 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 sys
import heapq
 
input = sys.stdin.readline
 
N, M = map(int,input().split())
problems = [[] for i in range(N+1)]
in_degree = [0 for i in range(N+1)]
 
= []
 
for _ in range(M):
    a, b = map(int,input().split())
    problems[a].append(b)
    in_degree[b]+=1
    
for i in range(1, N+1):
    if in_degree[i] == 0:
        heapq.heappush(h, i)
        
answer =[]
while h:
    tmp = heapq.heappop(h)
    answer.append(tmp)
    for j in problems[tmp]:
        in_degree[j] -=1
        if in_degree[j] == 0:
            heapq.heappush(h,j)
            
print(*answer)
cs

문제링크:

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

 

1766번: 문제집

첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주

www.acmicpc.net

 

'Algorithm > Python' 카테고리의 다른 글

[BOJ]2212. 센서  (0) 2022.03.08
[BOJ]17609. 회문  (0) 2022.03.03
[BOJ]1256. 사전  (0) 2022.02.24
[BOJ]10164. 격자상의 경로  (0) 2022.02.22
[BOJ]1916. 최소비용 구하기  (0) 2022.02.18

문제:

N X N 표에 수 N^2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. N=5일 때의 예를 보자.

12 

15 

13 

11 

19 

21 

10 

26 

31 

16 

48 

14 

28 

35 

25 

52 

20 

32 

41 

49 


이러한 표가 주어졌을 때, N번째 큰 수를 찾는 프로그램을 작성하시오. 표에 채워진 수는 모두 다르다.


입력:

첫째 줄에 N(1<=N<=1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다.

출력:

첫째 줄에 N번째 큰 수를 출력한다.

풀이 방법:

 처음에는 모든 값을 다 담아서 n번 빼는 방식으로 했더니 메모리초과가 발생했다. N이 최대 1500까지 가능하니 1500^2개가 있으니 그럴만하다. 이 문제에서 원하는 것은 상위 N개를 원하는 것이다. 따라서 상위 N개만 담는 최소 힙을 만들고 모든 표를 다 본 뒤에 가장 작은 값을 찾으면 N번째 큰 수를 얻을 수 있다고 생각했다. heapq를 자세히 알아보니 heappop()으로 가장 작은 값을 빼낼 수 있지만 빼지 않고 arr[0]과 같이 접근 하면 가장 작은 값을 얻을 수 있다고 한다. 따라서 이를 이용해 answer에 가장 작은 값보다 큰 값이 들어오면 작은 값을 빼내고 큰 값을 넣는 방식으로 상위 N개 배열을 유지하였다.
 이 문제는 애초에 pypy3으로 제출해서 python3에서 어떻게 동작할지는 잘 모르겠다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import heapq
answer=[]
heapq.heapify(answer)
n=int(input())
for i in range(n):
    numbers=list(map(int,input().split()))
    if i==0:
        for number in numbers:
            heapq.heappush(answer,number)
        minItem=answer[0]
    else:
        for number in numbers:
            if number > minItem:
                heapq.heappush(answer,number)
                heapq.heappop(answer)
                minItem=answer[0]
print(answer[0])
cs


'Algorithm > Python' 카테고리의 다른 글

[BOJ]10816. 숫자 카드2  (0) 2019.07.25
[BOJ]1920. 수 찾기  (0) 2019.07.24
[BOJ] 11279,1927,11286 최대힙,최소힙,절대값 힙  (0) 2019.07.21
[BOJ]2606. 바이러스  (0) 2019.07.20
[BOJ]1260. DFS와 BFS  (0) 2019.07.19

문제:

널리 잘 알려진 자료구조 중 최대 힙(최소 힙)이라는 것이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 큰(작은) 값을 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

입력:

첫째 줄에 연산의 개수 N(1<=N<=100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 2^31보다 작다.

출력:

입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 큰 값을 출력하라고 한 경우에는 0을 출력하면 된다.

풀이 방법:

 python에는 우선순위큐(힙)을 지원하는 heapq라는 모듈이 있다.python에서는 default로 최소 힙을 지원하기 때문에 최소 힙 문제에서는 모듈의 함수를 그대로 사용하면 되지만 최대 힙이나 절대값 힙과 같은 경우에는 별도의 스킬이 필요하다. 
 이 문제에서 사용하는 heapq의 함수는 heapify(), heappop(),heappush()가 있다. heapify(arr)는 일반 배열을 힙 구조를 가지는 배열로 만드는 함수로써 자동으로 배열 내 원소의 변동(추가, 삭제)가 있을 때마다 새로 힙 구조를 만든다. heappop(arr)는 arr에서 제일 위에 있는(제일 작은) 값을 빼내는 함수이고, heappush(arr,item)은 arr에 item을 넣고 힙 구조를 재배열하는 함수이다.
 최소 힙을 최대힙으로 바꾸기 위해서 값을 넣을 때 그냥 값을 넣는 것이 아니라 (-item,item)과 같은 방식으로 값을 넣는다. 힙 구조를 -item을 기준으로 정렬한다. 단순히 생각하면 "최소 힙으로 정렬한 것을 뒤집었다"라고 생각하면 된다. 따라서 이렇게 값을 넣었으므로 뺀 뒤에 [1]과 같은 방식으로 값을 접근해야 원래의 값을 얻는다.
 최대 힙과 같은 방식으로 절대값 힙도 (abs(item),item)으로 정렬하면 된다.

또한 python3로 제출하면 시간초과가 발생해서 pypy3로 제출해서 시간초과문제를 해결하였습니다.
[2019.07.29 수정] 문제가 재채점 되었더니 시간초과가 발생하였다. 따라서 input() -> sys.stdin.readline().rstrip() 으로 바꾸어서 해결하였다. (import sys 필요) 

최대 힙:

1
2
3
4
5
6
7
8
9
10
11
12
import heapq
h=[]
heapq.heapify(h)
for i in range(int(input())):
    n=int(input())
    if n==0:
        if len(h)==0:
            print(0)
        else:
            print(heapq.heappop(h)[1])
    else:
        heapq.heappush(h,(-n,n))
cs

최소 힙:

1
2
3
4
5
6
7
8
9
10
11
12
import heapq
h=[]
heapq.heapify(h)
for i in range(int(input())):
    n=int(input())
    if n==0:
        if len(h)==0:
            print(0)
        else:
            print(heapq.heappop(h))
    else:
        heapq.heappush(h,n)
cs

절대값 힙:

1
2
3
4
5
6
7
8
9
10
11
12
import heapq
h=[]
heapq.heapify(h)
for i in range(int(input())):
    n=int(input())
    if n==0:
        if len(h)==0:
            print(0)
        else:
            print(heapq.heappop(h)[1])
    else:
        heapq.heappush(h,(abs(n),n))
cs


'Algorithm > Python' 카테고리의 다른 글

[BOJ]1920. 수 찾기  (0) 2019.07.24
[BOJ]2075. N번째 큰 수  (0) 2019.07.23
[BOJ]2606. 바이러스  (0) 2019.07.20
[BOJ]1260. DFS와 BFS  (0) 2019.07.19
[BOJ]2164. 카드2  (0) 2019.07.18

+ Recent posts