문제:

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다.

매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 20) = 120 번의 비교가 필요하므로 덜 효율적인 방법이다.

N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000) 이어서 N개의 줄에 걸쳐 숫자 카드 묶음의 각각의 크기가 주어진다. 숫자 카드 묶음의 크기는 1,000보다 작거나 같은 양의 정수이다.

출력:

첫째 줄에 최소 비교 횟수를 출력한다.

풀이방법:

최소한의 비교를 하기 위해서는 계속해서 가장 작은 두 수를 골라서 비교를 하는 것이 이득이다. 따라서 python의 heapq를 사용해 최소힙을 구성한다.

heappop을 사용해서 가장 작은 두 값을 뽑아내고, 이 둘을 합친 값을 다시 heap에 넣는다. 이를 heap에 하나의 원소가 남을 때까지 반복하면 최소 비교 횟수를 얻을 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import heapq
h = []
n = int(input())
for _ in range(n):
    heapq.heappush(h,int(input()))
 
answer = 0
while len(h)>=2:
    one = heapq.heappop(h)
    two = heapq.heappop(h)
    temp = one+two
    answer+=temp
    heapq.heappush(h,temp)
 
print(answer)
 cs

문제링크:

www.acmicpc.net/problem/1715

 

1715번: 카드 정렬하기

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장

www.acmicpc.net

 

저작자표시 비영리 동일조건

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

[BOJ]2061. 좋은 암호  (0) 2021.02.04
[BOJ]1251. 단어 나누기  (0) 2021.02.02
[BOJ]2529. 부등호  (0) 2021.01.26
[BOJ]2003. 수들의 합 2  (0) 2021.01.19
[BOJ]2661. 좋은 수열  (0) 2021.01.14

문제:

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

12 

7 

9 

15 

5 

13 

8 

11 

19 

6 

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

티스토리툴바