Algorithm-중량제한

Oct 27, 2020 in Algorithm, Search, Binary Search

백준 1939 : 문제링크

문제유형 :
- 탐색
- 이진탐색
- BFS
설명
- 다리의 개수 M의 최대 100,000, 중량 제한 C는 최대 1,000,000,000
- 이진탐색을 이용하면 시간 복잡도는 O(M * logC)
- DFS로 도착지에 옮길 수 있는 지 확인
- 한 번에 옮길 수 있는 물품의 최대값을 이진탐색으로 찾아낸다.

풀이

from collections import deque

n, m = map(int, input().split())
adj = [[] for _ in range(n + 1)]

def bfs(c):
    queue = deque([start_node])
    visited = [False] * (n + 1)
    visited[start_node] = True
    while queue:
        x = queue.popleft()
        for y, weight in adj[x]:
            if not visited[y] and weight >= c:
                visited[y] = True
                queue.append(y)
    return visited[end_node]

start = 1000000000
end = 1

for _ in range(m):
    x, y, weight = map(int, input().split())
    adj[x].append((y, weight))
    adj[y].append((x, weight))
    start = min(start, weight)
    end = max(end, weight)

start_node, end_node = map(int, input().split())

result = start
while(start <= end):
    mid = (start + end) // 2
    if bfs(mid):
        result = mid
        start = mid + 1
    else:
        end = mid - 1

print(result)

Comment and share

Algorithm-공유기 설치

Oct 27, 2020 in Algorithm, Search, Binary Search

백준 2110 : 문제링크

문제유형 :
- 탐색
- 이진탐색
설명
- 집의 개수 N의 최대는 200,000 이고 집의 좌표 X의 최대 1,000,000,000이다
- 이진탐색을 이용하면 시간 복잡도는 O(N * logX)
- 집 간 거리 Gap에 대해서 이진탐색을 한다.

풀이

n, c = list(map(int, input().split(' ')))`

array = []
for _ in range(n):
    array.append(int(input()))
array = sorted(array)

start = array[1] - array[0]
end = array[-1] - array[0]
result = 0

while(start <= end):    // 시간 복잡도 : O(logX)
    mid = (start + end) // 2
    value = array[0]
    count = 1
    for i in range(1, len(array)): // 시간 복잡도 : O(N)
        if array[i] >= value + mid:
            value = array[i]
            count += 1
    if count >= c:
        start = mid + 1
        result = mid
    else:
        end = mid - 1

print(result)

Comment and share

Algorithm-중량제한

Algorithm-공유기 설치

Yechan Kim