문제:

성경이는 트럭을 정글 속에서 운전하다가 트럭의 연료탱크에 갑자기 구멍이 나서 1km를 가는데 1L의 연료가 새 나가게 되었다. 이것을 고치기 위해서는 가장 가까운 마을에 가야 한다. 그런데 그냥 가다가는 중간에 연료가 다 빠질 수가 있다. 다행스럽게도 정글 곳곳에 연료를 채울 수 있는 주유소가 N개 있다. 그런데 정글 속에서 중간에 차를 멈추는 행위는 매우 위험한 행위이므로 주유소에서 멈추는 횟수를 최소화 하려 한다.

그리고 다행이도 성경이의 트럭은 매우 좋아서 연료 탱크에는 연료의 제한이 없이 많이 충분히 많이 넣을 수 있다고 한다. 각각의 주유소의 위치와, 각 주유소에서 얻을 수 있는 연료의 양이 주어져 있을 때, 주유소에서 멈추는 횟수를 구하는 프로그램을 작성하시오.

정글은 일직선이고, 성경이의 트럭과 주유소도 모두 일직선 위에 있다. 주유소는 모두 성경이의 트럭을 기준으로 오른쪽에 있다.

입력:

첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경이의 시작 위치에서 주유소 까지의 거리, 그리고 b(1 ≤ b ≤ 100)는 그 주유소에서 채울 수 있는 연료의 양을 의미한다. 그리고 N+2번째 줄에는 두 정수 L과 P가 주어지는데 L(1 ≤ L ≤ 1,000,000)은 성경이의 위치에서 마을까지의 거리, (1 ≤ P ≤ 1,000,000)는 트럭에 원래 있던 연료의 양을 의미한다.

출력:

첫째 줄에 주유소에서 멈추는 횟수를 출력한다. 만약 마을에 도착하지 못할경우 -1을 출력한다.

풀이방법:

1. 우선순위 큐를 사용해서 연료 내에서 움직일 수 있는 주유소에서 주유하도록 한다.

2. 데이터를 전처리할 때, 거리는 작은 순으로 주어지지 않는다. 정렬이 필요하다

3. 마을에 도착하지 못하는 경우는 while에 있지만 더 이상 움직이지 못할 때를 의미한다. (candidates가 비어있는 경우)

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
31
32
33
34
35
36
import heapq
def solution(move, dist, fuels, town):
    candidates = []
    cnt = 0
    location = 0
    while move < town:
        for i in range(location, len(dist)):
            if dist[i] <= move:
                f = fuels[i]
                heapq.heappush(candidates, (-f, f))
                location = i+1
            else:
                break
        if not len(candidates):
            cnt = -1
            break
        cnt += 1
        move += heapq.heappop(candidates)[1]
    return cnt
 
dist_ = []
fuel_ = []
temp= []
n = int(input())
for _ in range(n):
    dist, fuel = map(int,input().split())
    temp.append((dist,fuel))
    
temp.sort()
for i in range(len(temp)):
    dist_.append(temp[i][0])
    fuel_.append(temp[i][1])
    
len_, start = map(int,input().split())
answer = solution(start,dist_,fuel_,len_)
print(answer)
 cs

문제링크:

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

 

1826번: 연료 채우기

첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경

www.acmicpc.net

 

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

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

[BOJ]2302. 극장 좌석  (0) 2021.06.03
[BOJ]1024. 수열의 합  (0) 2021.06.01
[BOJ]1422. 숫자의 신  (0) 2021.05.25
[BOJ]15686. 치킨 배달  (0) 2021.05.20
[BOJ]2583. 영역 구하기  (0) 2021.05.18

문제:

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 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

문제:

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 *2)

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

풀이 방법:

단순하게 scoville 배열을 정렬한 뒤에 첫 번째 인덱스값이 K보다 커지는 순간까지 섞는 과정을 반복하면 된다고 생각했다.
따라서 다음과 같이 코드를 작성할 수 있었다. 중간에 elif 조건으로 scoville 배열이 1인지 확인을 하였는데 이 경우에 더 이상 섞지 못하는 경우이기 때문에 -1을 반환하는 경우인 것이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def solution(scoville,K):
    count=0
    while(True):
        scoville.sort()
        if scoville[0]>K:
            break
        elif len(scoville)==1:
            return -1
        else:
            count+=1
            a=scoville.pop(0)
            b=scoville.pop(0)
            scoville.append(a+2*b)
    return count
cs

 하지만 이 방법은 효율성 테스트에서 시간초과로 통과하지 못한다. 이 문제의 태그가 힙(heap)이므로 힙을 사용하도록 코드를 수정하였다.

힙이란 최댓값과 최솟값을 빠르게 찾아내기 위해 고안된 자료 구조로 완전이진트리로 구성되어 있다. 힙에는 최대 힙과 최소 힙 두 가지가 있다. 힙은 부모노드와 자식 노드와만 대소 관계가 존재하는데 부모 노드가 큰 경우가 최대 힙, 자식 노드가 큰 경우가 최소 힙이다.


 파이썬에서는 힙 구조를 구현할 수 있도록 모듈을 제공한다. import heapq 로 불러와서 사용을 한다. heapq는 부모 노드가 자식 노드보다 항상 작거나 같은 최소 힙을 제공한다. 따라서 가장 작은 요소가 0 인덱스를 가지며 pop을 했을 경우에 가장 작은 값이 나온다.


이번 문제를 해결하기 위해 heapq.heappush(heap,item)과 heapq.heappop(heap)을 사용했다.

heapq.heappush(heap,item)은 힙의 구조를 유지하면서 heap에 item을 넣는 것이고 heapq.heappop(heap)은 가장 작은 값을 반환하며 이 역시 힙의 구조를 유지한다. 따라서 위의 코드를 heap 구조를 유지하면서 해결하도록 수정하였다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import heapq
def solution(scoville,K):
    count=0
    h=[]
    for i in scoville:
        heapq.heappush(h,i)
    while(True):
        if h[0]>=K:
            return count
        elif len(h)==1:
            return -1
        else:
            a=heapq.heappop(h)
            b=heapq.heappop(h)
            heapq.heappush(h,a+b*2)
            count+=1
cs


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

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

[Programmers]Lv2. 큰 수 만들기  (0) 2019.02.12
[Programmers]Lv 1. K번째수  (0) 2019.02.11
[Programmers]Lv 1.같은 숫자는 싫어  (0) 2019.02.09
[Programmers]Lv 2.조이스틱  (2) 2019.02.08
[Programmers]Lv 1.문자열 내 마음대로 정렬하기  (0) 2019.02.07

+ Recent posts

티스토리툴바