'Algorithm/Python' 카테고리의 글 목록 (33 Page)

728x90

문제:

N개의 마을로 이루어진 나라가 있습니다. 이 나라의 각 마을에는 1부터 N까지의 번호가 각각 하나씩 부여되어 있습니다. 각 마을은 양방향으로 통행할 수 있는 도로로 연결되어 있는데, 서로 다른 마을간에 이동할 때는 이 도로를 지나야 합니다. 도로를 지날 때 걸리는 시간은 도로별로 다릅니다. 현재 1번 마을에 있는 음식점에서 각 마을로 음식 배달을 하려고 합니다. 각 마을로부터 음식 주문을 받으려고 하는데, N개의 마을 중에서 K 시간 이하로 배달이 가능한 마을에서만 주문을 받으려고 합니다. 다음은 N=5, K=3인 경우의 예시입니다.

1번 마을에 있는 음식점은 [1,2,4,5]번 마을까지는 3이하의 시간에 배달할 수 있습니다. 그러나 3번 마을까지는 3시간 이내로 배달할 수 있는 경로가 없으므로 3번 마을에서는 주문을 받지 않습니다. 따라서 1번 마을에 있는 음식점이 배달 주문을 받을 수 있는 마을은 4개가 됩니다.

마을의 개수 N, 각 마을을 연결하는 도로의 정보 road, 음식 배달이 가능한 시간 K가 매개변수로 주어질 때, 음식 주문을 받을 수 있는 마을의 개수를 return 하도록 solution 함수를 완성해주세요.

풀이 방법:

DFS 방법을 사용해서 배달 거리가 K를 넘지 않을 때까지 stack 배열에 쌓으면서 계속해서 들어간다. 들어가는 과정에서 방문하는 마을은 모두 K시간 내 방문할 수 있는 곳이므로 count set에 담도록 한다.(set이므로 중복된 것을 넣어도 자동으로 사라진다.) stack 배열을 사용하는 이유는 사이클을 피하기 위해서이므로 깊은 노드를 방문하고 다시 나올 때는 stack에서 pop 하도록해서 다른 노드를 방문할 시간을 주도록 한다.

하지만 재귀 과정에서 문제가 발생해서 시간초과가 발생하는 것 같은데 무엇이 문제인지는 정확히 모르겠다. (정렬도 해봤지만 차이가 없었다.)

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

def delivery(stack,dist,now,roads,K):
    for r in roads[now]:
        temp=dist+r[1]
        if not r[0] in stack and temp <=K:
            stack.append(r[0])
            count.add(r[0])
            delivery(stack,temp,r[0],roads,K)
            stack.pop()
    
def solution(N,road,K):
    roads=[[]for i in range(N+1)]
    for i in range(len(road)):
        if not road[i][0] in roads[road[i][1]]:
            roads[road[i][1]].append((road[i][0],road[i][2]))
        if not road[i][1] in roads[road[i][0]]:
            roads[road[i][0]].append((road[i][1],road[i][2]))
    stack=[1]
    dist=0
    global count
    count=set(stack)
    for r in roads[1]:
        temp=dist+r[1]
        if not r[0] in stack and temp <=K:
            stack.append(r[0])
            count.add(r[0])
            delivery(stack,temp,r[0],roads,K)
            stack.pop()
    return len(count)
Colored by Color Scripter

cs

<2021.07.11 수정>

DFS와 같이 재귀적인 방법을 사용하는 것이 시간을 많이 소요할 것 같아 일반적으로 그래프에서 최소 거리를 구하는 방법으로 많이 사용되는 다익스트라 방법을 사용했다. 1에서 부터의 거리를 측정하기 때문에, 1에서 다익스트라로 거리를 구한 뒤에 K보다 작은 것의 갯수를 세서 반환하도록 한다.

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

import heapq
 
def dijkstra(start,dp,edge):
    dp[start] = 0
    heapq.heappush(heap,(0,start))
    
    while heap:
        weight, move = heapq.heappop(heap)
        
        if dp[move] < weight:
            continue
        for w, node in edge[move]:
            if w+weight< dp[node]:
                dp[node] = w+weight
                heapq.heappush(heap,(dp[node],node))
    return dp
 
def solution(N,road,K):
    edge = [[] for _ in range(N+1)]
    heap = []
    for i in road:
        a,b,c = i
        edge[a].append((c,b))
        edge[b].append((c,a))
    dp = [float('inf')]*(N+1)
    
    dp = dijkstra(1,dp,edge)
    answer = 0
    for i in range(1,V+1):
        if dp[i] <= K:
            answer +=1
    return answer
Colored by Color Scripter

cs

문제 링크:

https://programmers.co.kr/learn/courses/30/lessons/12978

728x90

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

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

[BOJ]15649. N과M(1),(2) (0)	2019.08.02
[BOJ]1009. 분산처리 (0)	2019.08.01
[Programmers]Lv 3. 순위 (0)	2019.07.30
[Programmers]Lv3. 가장 먼 노드 (0)	2019.07.29
[Programmers]Lv 4. 3xn 타일링 (2)	2019.07.28

728x90

문제:

n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정화하게 순위를 매길 수 없습니다.

선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요.

풀이 방법:

각 선수가 이긴 선수와 진 선수의 정보를 hash방식으로 정리하고 한 선수의 win정보의 길이와 lose정보 길이를 합쳤을 때 n-1과 같아지면 그 선수의 순위를 알 수 있게 된다. 또한 실력의 차이가 극명해서 실력이 낮은 사람이 높은 사람을 이길 수 없다고 한다. 따라서 정보를 가지고 있지 않지만 이 조건을 통해서 정보를 다시 얻을 수 있게 된다.

입출력 예시를 통해서 살펴 보면 2번선수의 경우에는 모든 경기기록이 있어서 순위를 알 수 있지만 5번 선수는 2번 선수와의 기록이 있지만 순위를 유추할 수 있다. 왜냐하면 2번이 1,3,4번 선수한테 졌는데 5번이 2번한테 졌으므로 5번은 당연히 1,3,4번 선수한테 진다는 것을 알 수 있다.(1,3,4 > 2 > 5) 또한 2번이 5번을 이겼기 때문에 5번이 이긴 사람도 당연히 이길 수 있다. (이 문제에서는 이러한 케이스가 없긴 하다.)

처음에는 리스트로 했더니 시간초과가 발생해서 이를 set으로 바꿔서 했더니 시간초과가 발생하지 않았다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def solution(n, results):
    answer=0
    win={}
    lose={}
    for i in range(1,n+1):
        win[i]=set()
        lose[i]=set()
    results.sort()
    for i in range(1,n+1):
        for re in results:
            if re[0]==i:
                win[i].add(re[1])
            if re[1]==i:
                lose[i].add(re[0])
        for j in win[i]:
            lose[j].update(lose[i])
        for j in lose[i]:
            win[j].update(win[i])
    for i in range(1,n+1):
        if len(win[i])+len(lose[i])==n-1:
            answer+=1
    return answer
cs

문제 링크:

https://programmers.co.kr/learn/courses/30/lessons/49191

728x90

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

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

[BOJ]1009. 분산처리 (0)	2019.08.01
[Programmers]Lv 3.배달 (3)	2019.07.31
[Programmers]Lv3. 가장 먼 노드 (0)	2019.07.29
[Programmers]Lv 4. 3xn 타일링 (2)	2019.07.28
[BOJ]2805. 나무 자르기 (0)	2019.07.27

728x90

문제:

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선의 대한 정보가 담신 2차우너 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

풀이 방법:

노드들의 최소경로 값을 나타내는 answer를 만든 뒤에 BFS 방식으로 노드들을 검사한다. 노드를 방문할 때마다 해당 node의 answer 값이 0이면 count로 초기화 해주고, count는 한 층을 더 들어갈 때 마다 1씩 증가하도록 했다. 이렇게 모든 answer가 0이 아닌 값으로 변하면(all) answer의 max값을 찾아서 max로 count를 해 답을 얻을 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def solution(n, edge):
    answer = [0]*(n+1)
    newedge=[[] for i in range(len(edge)+1)]
    for i in range(len(edge)):
        if not edge[i][1] in newedge[edge[i][0]]:
            newedge[edge[i][0]].append(edge[i][1])
            newedge[edge[i][0]].sort()
        if not edge[i][0] in newedge[edge[i][1]]:
            newedge[edge[i][1]].append(edge[i][0])
            newedge[edge[i][1]].sort()
    answer[0],answer[1]= -1,-1
    queue=[1]
    count=1
    while not all(answer):
        temp=[]
        for start in queue:
            for i in newedge[start]:
                if answer[i] ==0:
                    answer[i]+=count
                    temp.append(i)
        queue=temp
        count+=1
    ans=answer.count(max(answer))
    return ans
Colored by Color Scripter
cs

문제 링크:

https://programmers.co.kr/learn/courses/30/lessons/49189

728x90

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

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

[Programmers]Lv 3.배달 (3)	2019.07.31
[Programmers]Lv 3. 순위 (0)	2019.07.30
[Programmers]Lv 4. 3xn 타일링 (2)	2019.07.28
[BOJ]2805. 나무 자르기 (0)	2019.07.27
[BOJ]1654.랜선 자르기 (0)	2019.07.26

728x90

문제:

가로 길이가 2이고 세로의 길이가 1인 직사각형 모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 3이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다.

*타일을 가로로 배치하는 경우

*타일을 세로로 배치하는 경우

직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.

풀이 방법:

이전 단계인 2xn 타일링과 같이 동적계획법을 사용해서 풀어야 하는 문제이다. n이 증가할 때마다 어떠한 규칙에 따라서 증가하는지 파악할 수 있다면 쉽게 문제를 풀 수 있다. n이 6~8까지 그려보면 대충 규칙을 찾아낼수 있다. 우선 n이 홀수 일 때는 타일링을 할 수 없다. 따라서 이 경우에는 항상 0이다.

그리고 타일로 만들 수 있는 모양이 한정적이라서 그 모양들을 여러 개 붙인 모양으로 반복이 된다. 규칙이 있는 타일은 다음과 같다.

이 타일들의 조합으로 반복이 되며 n=4일 때부터는 추가적인 몇개의 조합이 더 생기게 된다. 이는 이전 n(짝수만 생각했을 때)과 연관이 있기 때문에 다음과 같이 코드를 짤 수 있다.

1
2
3
4
5
6
7
8
9
def solution(n):
    dp=[0]*(n+1)
    dp[0]=1
    special=0
    for i in range(2,n+1,2):
        dp[i]=dp[i-2]*3+special*2
        special+=dp[i-2]
    answer = dp[n]%1000000007
    return answer
cs

문제 링크:

https://programmers.co.kr/learn/courses/30/lessons/12902

728x90

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

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

[Programmers]Lv 3. 순위 (0)	2019.07.30
[Programmers]Lv3. 가장 먼 노드 (0)	2019.07.29
[BOJ]2805. 나무 자르기 (0)	2019.07.27
[BOJ]1654.랜선 자르기 (0)	2019.07.26
[BOJ]10816. 숫자 카드2 (0)	2019.07.25

728x90

문제:

상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할 것이다.

목재절단기를 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높이가 20,15,10,17이라고 하자. 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15,15,10,15가 될 것이고, 상근이는 길이가 5인 나무와 2인 나무를 들고 집에 갈 것이다. (총 7미터를 집에 들고 간다.)

상근이는 환경에 매우 관심이 많기 때문에, 나무를 필요한 만큼만 집으로 가져가려고 한다. 이 때, 적어도 M미터의 나무를 집에 가져가지 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1<=N<=1,000,000, 1<=M<=2,000,000,000)

둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M을 넘기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다. 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.

출력:

적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

풀이 방법:

이 문제도 이분탐색(파라메트릭서치)를 사용해서 풀어야 하는 문제다. left를 1, right를 max(trees)로 잡고 나서 그 사이의 값을 찍어가면서 M보다 커질 때마다 mid을 비교해 최대값을 찾도록 한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
k,n=map(int,input().split())
trees=list(map(int,input().split()))
left=1
right=max(trees)
answer=0
while left <= right:
    count=0
    mid=(left+right)//2
    for tree in trees:
        if tree-mid > 0:
            count+=tree-mid
    if count==n:
        if answer < mid:
            answer=mid
        left=mid+1
    elif count < n:
        right=mid-1
    else:
        if answer < mid:
            answer=mid
        left=mid+1
print(answer)
cs

문제 링크:

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

728x90

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

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

[Programmers]Lv3. 가장 먼 노드 (0)	2019.07.29
[Programmers]Lv 4. 3xn 타일링 (2)	2019.07.28
[BOJ]1654.랜선 자르기 (0)	2019.07.26
[BOJ]10816. 숫자 카드2 (0)	2019.07.25
[BOJ]1920. 수 찾기 (0)	2019.07.24

728x90

문제:

집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다.

이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm은 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)

편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K<=N이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위로 정수로 입력된다. 랜선의 길이는 2^31보다 작거나 같은 자연수이다.

출력:

첫째 줄에 N개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력한다.

풀이 방법:

이분 탐색을 사용해서 풀어야 하는 문제이다. 바이너리서치가 아닌 파라메트릭 서치를 사용하는 것이다, 이 문제의 핵심은 잘 찍어내는 것으로 최솟값과 최대값을 고르면 그 사이를 탐색하면서 잘 찍은 값을 반환하는 것이다. 이 잘 찍는 과정은 이분 탐색을 근거로 하게 된다.

이 문제도 left를 1로(0으로 하면 런타임 에러(0으로 나눈 에러)가 발생한다.) right는 내가 가지고 있는 선 중 가장 큰 값으로 사용했다. 이 left값과 right값을 통해서 mid값을 구했고, 이를 lines를 순회하며 count를 계산했고 n과 같아지는 순간에 mid값 중 가장 큰 값을 고르도록 하였다.하지만 이렇게 했을 때 계속 문제를 틀렸다고 결과를 받았다.

무엇이 문제인지 알아보니 만약 K개의 랜선으로 N개 이상을 만들어도 N개를 사용하고 나머지는 버려서 사용할 수 있기 때문에 count > n일 때도 mid 값을 answer에 업데이트 해야한다고 한다. 따라서 이에 맞게 수정을 했더니 통과를 했다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
k,n=map(int,input().split())
lines=[]
for i in range(k):
    lines.append(int(input()))
left=1
right=max(lines)
answer=0
while left <= right:
    count=0
    mid=(left+right)//2
    for line in lines:
        count+=line//mid
    if count==n:
        if answer < mid:
            answer=mid
        left=mid+1
    elif count < n:
        right=mid-1
    else:
        if answer < mid:
            answer=mid
        left=mid+1
print(answer)
cs

문제 링크:

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

728x90

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

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

[Programmers]Lv 4. 3xn 타일링 (2)	2019.07.28
[BOJ]2805. 나무 자르기 (0)	2019.07.27
[BOJ]10816. 숫자 카드2 (0)	2019.07.25
[BOJ]1920. 수 찾기 (0)	2019.07.24
[BOJ]2075. N번째 큰 수 (0)	2019.07.23

728x90

문제:

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 (1<=N<=500,000)가 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

셋째 줄에는 M(1<=M<=500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지면, 이 수는 공백으로 구분되어져 있다. 이수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

출력:

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

풀이 방법:

이진 탐색을 사용하면 쉽게 구할 수 있다. 만약 10의 개수가 궁금하다고 가정하자 그러면 10의 bisect_left의 인덱스와 11의 bisect_left를 구하면 10의 개수를 쉽게 얻을 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
import bisect
n=int(input())
arr = list(map(int,input().split()))
arr.sort()
m=int(input())
check=list(map(int,input().split()))
for i in range(m):
    idx1=bisect.bisect_left(arr,check[i])
    if idx1 <len(arr) and arr[idx1]==check[i]:
        idx2=bisect.bisect_left(arr,check[i]+1)
        print(idx2-idx1,end=' ')
    else:
        print(0,end=' ')
cs

728x90

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

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

[BOJ]2805. 나무 자르기 (0)	2019.07.27
[BOJ]1654.랜선 자르기 (0)	2019.07.26
[BOJ]1920. 수 찾기 (0)	2019.07.24
[BOJ]2075. N번째 큰 수 (0)	2019.07.23
[BOJ] 11279,1927,11286 최대힙,최소힙,절대값 힙 (0)	2019.07.21

728x90

문제:

N개의 정수 A[1], A[2], ... , A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력:

첫째 줄에 자연수 N(1<=N<=100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], ... , A[N]이 주어진다. 다음줄에는 M(1<=M<=100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수들의 범위는 int로 한다.

출력:

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

풀이 방법:

binary_search를 사용하는 문제이다. python에 이진탐색을 지원하는 bisect라는 모듈이 있다. 따라서 이를 사용하면 쉽게 문제를 풀 수 있다. bisect의 모듈은 binary search를 직접적으로 지원을 하지 않기 때문에 따로 만들어줘야 한다. bisect에 bisect_left(arr,x)와 bisect_right(arr,x)가 있는데, 각각 arr에 x를 넣어야 할 때 어느 인덱스에 넣어야 할지 알려주는 함수이다.(left는 왼쪽에, right는 오른쪽에) 따라서 bisect_left를 사용하면 binary_search를 구현할 수 있다. 만약 기존 arr에 있는 값을 찾는다고 하면(넣으려고 한다면) 왼쪽 인덱스를 반환해주므로 원래의 위치를 return 해준다. 따라서 그 인덱스에 해당하는 배열 값과 x가 같으면 존재하고, 같지 않다면 존재하지 않다고 할 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import bisect
def binary_search(arr,x):
    i = bisect.bisect_left(arr,x)
    return i < len(arr) and arr[i]==x
n=int(input())
arr = list(map(int,input().split()))
arr.sort()
m=int(input())
check=list(map(int,input().split()))
for i in range(m):
    if binary_search(arr,check[i]):
        print(1)
    else:
        print(0)
cs

728x90

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

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

[BOJ]1654.랜선 자르기 (0)	2019.07.26
[BOJ]10816. 숫자 카드2 (0)	2019.07.25
[BOJ]2075. N번째 큰 수 (0)	2019.07.23
[BOJ] 11279,1927,11286 최대힙,최소힙,절대값 힙 (0)	2019.07.21
[BOJ]2606. 바이러스 (0)	2019.07.20

728x90

문제:

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

728x90

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

'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

728x90

문제:

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

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

728x90

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

'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