백준 algorithm study 16439 1939 10867 bfs 이분탐색 조합 최소힙 큐 set python

파이썬 알고리즘 : 치킨치킨치킨, 중량제한, 중복 빼고 정렬하기

백준 16439 , 백준 1939, 백준 10867

2023년 8월 31일 알고리즘 문제풀이

문제 1 백준 16439

문제 링크

1차 시도

나의 생각

세 종류의 치킨을 고르는 것은 조합(Combination)을 이용했다. 근데 라이브러리를 사용하지 않고 3중 for문으로 구현했다. 라이브러리 쓰는 법도 익혀야지..

어쩄든 한 사람은 세 종류의 치킨 중 선호도가 가장 높은 것으로 점수를 나타내니 최소힙을 이용하되 음수로 바꾼 후 넣은 후 heappop하여 점수를 구했다. 그리고 각 조합 때마다 현재까지 최고 점수랑 비교하며 업데이트 해주었다.

결과

정답

코드

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

import sys
from heapq import heappop, heappush
n, m = map(int, sys.stdin.readline().split())
graph = []
for _ in range(n):
    graph.append(list(map(int, sys.stdin.readline().split())))


def cal():
    max_val = 0
    for i in range(m):
        for j in range(m):
            if j == i:
                continue
            for k in range(m):
                ans = 0
                if k == i or k == j:
                    continue
                for person in range(n):
                    arr = []
                    heappush(arr, -1*graph[person][i])
                    heappush(arr, -1*graph[person][j])
                    heappush(arr, -1*graph[person][k])
                    tmp = heappop(arr)
                    tmp *= -1
                    ans += tmp
                max_val = max(max_val, ans)
    return max_val


answer = cal()
print(cal())

문제 2 백준 1939

문제 링크

1차 시도

나의 생각

간단한 BFS문제라고 생각했다. BFS를 통해 현재까지 지나온 다리들 중 가장 낮은 중량제한을 가진 다리의 것이 옮길 수 있는 중량의 최댓값으로 업데이트하였다. 하지만 메모리초과로 인해 오답처리되었다. 섬의 갯수 범위가 10000이기 때문에 n^2는 너무 컸다.. 어떻게 개선시켜야 할지 모르겠다.

결과

오답(메모리 초과)

코드

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

import sys
from heapq import heappop, heappush

n,m = map(int,sys.stdin.readline().split())
graph = [[0 for _ in range(n+1)] for _ in range(n+1)]
for _ in range(m):
    a,b,c = map(int,sys.stdin.readline().split())
    graph[a][b] = max(graph[a][b],c)
    graph[b][a] = max(graph[b][a],c)
start, arrive = map(int,sys.stdin.readline().split())

def bfs(p,q):
    arr = []
    heappush(arr,(-1e9,p))
    while arr:
        limit,now = heappop(arr)
        limit *= -1
        if now == q:
            return limit
        for i in range(1,n+1):
            if not graph[now][i] or graph[now][i]>limit:
                continue
            tmp = min(limit,graph[now][i])
            heappush(arr,(-1*tmp,i))

ans = bfs(start,arrive)
print(ans)

2차 시도

나의 생각

BFS로 모든 경우를 탐색하여 정답을 도출하는 것은 메모리 문제로 불가능했다. 문제 하단에서 볼 수 있는 알고리즘 분류를 봤더니 이분 탐색이 적혀있었다. 그래서 이분 탐색을 통해 건널 수 있는 중량을 탐색하도록 하였다. BFS는 해당 중량이 가능한지만 판단하고, BFS에 parameter로 넣을 값은 이분탐색을 통해 설정하였더니 정답이 되었다. 이걸 보고 어떻게 이분탐색을 생각해내…

결과

이해

코드

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

import sys
from collections import deque

n,m = map(int,sys.stdin.readline().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a,b,c = map(int,sys.stdin.readline().split())
    graph[a].append([b,c])
    graph[b].append([a,c])
start,arrive = map(int,sys.stdin.readline().split())

def bfs(w):
    visited[start] = 1
    arr = deque()
    arr.append(start)
    while arr:
        now = arr.popleft()
        if now == arrive:
            return True
        for next_now, next_limit in graph[now]:
            if not visited[next_now] and next_limit >= w:
                arr.append(next_now)
                visited[next_now] = True
    return False

left = 1
right = 1e9
while left <= right:
    visited = [False for _ in range(n+1)]
    mid = (left+right)//2
    if bfs(mid):
        left = mid + 1
    else:
        right = mid - 1
print(int(right))

문제 3 백준 10867

문제 링크

1차 시도

나의 생각

입력값을 받은 뒤 set 자료구조로 변환하여 중복을 없애주었다. 다시 리스트로 전환하여 순서대로 정렬해주었다.

결과

정답

코드

1
2
3
4
5
6
7
8

import sys

n = int(sys.stdin.readline())
arr = set(list(map(int, sys.stdin.readline().split())))
arr = list(arr)
arr.sort()
print(*arr)
CATALOG
    algorithm