(전공복습) 데이터과학 4. 시각화
차례
백준(BOJ) 1826 연료 채우기 파이썬(Python)
그리디(Greedy)하게 접근하면 되는 문제.
\(N\le10000\)이고 \(B\le100\)이라는 작은 입력을 가졌다는 점을 특기할 만하다.
우선, 한 가지 생각해보면 좋은 점은 거리가 \(L\)인 마을에 도착하기 위해서는 멈추든 안 멈추든 모든 주유소를 거쳐야 한다는 점이다.
다시 말해, 도착하지 못하는 주유소가 있다면, 마을에도 도착할 수 없다.
그래서 먼저 모든 주유소(\(N\))에 도착할 수 있는지를 고려할 것이다.
앞쪽에 있는 주유소부터 확인하기 위해 입력을 거리순으로 정렬한다.
이후, 현재 연료량을 나타내는 변수 oil을 초기화하고, 이전까지 있었던 주유소를 최소 몇 개를 들려야 지금 주유소에 도착할 수 있는지 확인한다.
기본적으로, 주유소를 연료량 순으로 정렬한 후, 현재 주유소보다 가까운 것들만 더해가면서 확인하면 답이 나오겠지만, 그리고 그러한 풀이는 \(O(N^2)\)이므로 시간도 충분하지만, 조금 더 효율적으로 풀기 위해 has_oil이라는 리스트를 만들어주었다.
has_oil[i]는 연료량이 i인 주유소가 지금까지 몇번 등장했는지를 의미한다.
즉, has_oil을 뒤에서부터 순회하면서 연료량이 맞춰지면 순회를 탈출하는 방식으로 구현하면 된다.
이 경우 \(O(NB)\)로 시간을 줄일 수 있다.
(후술하겠지만, 우선순위 큐를 사용하면 더 빠르게 할 수도 있다.)
만약 이 과정에서, 도달하지 못하는 주유소가 생기는 경우 그냥 -1을 출력하고 끝내면 된다.
마지막 주유소, 나아가 마을까지 도착하는 데에 성공했다면 지금까지 들린 주유소 개수를 출력하면 된다.
가질 수 있는 의문에는, 임의의 주유소에 도착하는 데에 사용한 최적의 방법이, 그 다음 주유소나 마을에 도착하는 데에 사용하는 최적의 방법의 부분집합이냐는 것이다.
이를테면, 10번 주유소에 도달하기 위해, 1번, 3번 주유소에 들렸다고 가정한다면, 11번 주유소에 도달하기 위해 1번과 3번 주유소를 들려야 하냐는 점이다.
11번 주유소가 도달 불가능하지 않는 한 이는 반드시 참인데, 귀류법으로 손쉽게 증명 가능하다.
만약, 11번 주유소에 도착하는 최적의 방법에 1번 또는 3번 주유소가 없다고 가정하자.
그렇다면 11번 주유소에 도착하는 더 최적인 다른 방법이 있을 것이다.
그런데, 11번 주유소는 10번 주유소보다 멀리 있으므로 11번 주유소에 최적으로 갈 수 있는 방법(또는 그 부분집합)은 10번 주유소도 최적으로 갈 수 있다.
그렇다면 10번 주유소에 가는 최적의 방법이 1번, 3번 주유소를 들리는 것이라는 전제가 거짓이 된다.
따라서, 어떤 주유소까지 가는 데에 사용한 최적의 방법은, 무조건 그 후로 나타나는 주유소에 가는 데에 필요한 최적의 방법의 부분집합이다.
추가로, 같은 연료량을 가진 주유소가 여러 개일 수도 있다는 점에 유의해야 한다.
이를테면, 아래 예제를 생각해보자.
2
1 5
2 5
12 2
has_oil을 단순히 부울로 저장하면 이런 예제를 틀리게 되므로 주의하자.
한편, 나는 떠올리지 못했지만 전술한 것처럼 길이 100짜리 배열(리스트)을 사용하는 것보다 더 빠른 방법은 우선순위 큐(Priority Queue)를 사용하는 것이다.
힙으로 구현한 우선순위 큐는 삽입, 삭제에 \(O(\log N)\)이 걸리고, 모든 주유소가 한 번 삽입되고 최대 한 번 삭제되므로 \(O(N \log N)\) 시간에 해결하게 되어, \(O(NB)\)인 풀이보다 더 빠르게 해결할 수 있다.
#!python
from sys import stdin
input = stdin.readline
# 주유소를 거리순으로 정렬하고, 마을을 연료가 0인 주유소로 취급
n = int(input())
stations = sorted(list(map(int, input().split())) for _ in range(n))
l, p = map(int, input().split())
stations.append([l, 0])
# has_oil[i]: 지금까지 만난 i만큼의 연료를 채우는 주유소의 개수
# oil: 현재 연료량
# ans: 주유소를 들린 횟수(정답)
has_oil = [0 for _ in range(101)]
oil, ans = p, 0
# 주유소는 정렬되어 있으므로 가까운 주유소부터 도착 가능한지 확인함
for a, b in stations:
# 지금까지 마주친 주유소 중 연료가 많은 것부터
for i in range(100, -1, -1):
# 지금 채워진 연료로 갈 수 있으면 break
if a <= oil:
break
if not has_oil[i]:
continue
# 같은 양의 연료를 가진 주유소가 여러 개일 수 있으므로
times = min(has_oil[i], -(-(a - oil) // i))
oil += i * times
ans += times
has_oil[i] -= times
else:
# 만약 break를 하지 않으면 못 가는 곳이므로 -1 출력
print(-1)
break
# 마지막에 마주친 주유소 추가
has_oil[b] += 1
else:
# -1을 출력한 적이 없으면 ans 출력
print(ans)
2024
맨 위로 이동 ↑2023
백준(BOJ) 2045 마방진 / 3192 매직 스퀘어 파이썬(Python)
문제 링크 문제 링크
세그먼트 트리
개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...
벨만-포드 알고리즘
개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...
다익스트라 알고리즘
개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...