(전공복습) 데이터과학 4. 시각화
차례
백준(BOJ) 1377 버블 소트 파이썬(Python)
약간 창의적인 발상이 필요한 문제.
버블 소트에서 바깥 이터레이션이 몇 번 일어나는지 알아내는 문제인데, 버블 소트는 \(O(N^2)\)이고 입력은 최대 \(500000\)이므로 정직하게 시뮬레이션하면 시간 초과가 된다.
아이디어는, 버블 소트의 바깥 이터레이션 한 번에, 자리가 적어도 하나라도 바뀌었다고 가정한다면(즉 changed==True라고 가정한다면), 적어도 하나의 원소는 앞으로 한 칸 이동했으며, 각 원소는 이터레이션 한 번당 앞으로는 한 칸씩만 이동한다는 점이다.
즉, 원래 인덱스에서 정렬된 후의 인덱스를 뺀 값의 최댓값이 바깥 이터레이션이 일어난 횟수이다.
이때, 이걸 일일히 리스트나 배열로 기록하면 최대 길이 \(1000000\)짜리 배열이 생기므로 효율적인 처리를 위해서는 딕셔너리와 같은 해시 테이블에 매핑하는 것이 좋을… 거라고 생각했는데, 실제로 벤치마크 해보니 이 정도 크기에선 시간이든 메모리든 리스트가 나은 것 같다. 뭘 써도 상관 없을 듯.
처음엔 같은 값이 리스트에 있을 수 있으므로 거기에 대한 처리를 하고 제출했는데, 다른 사람들의 코드를 보니 그런 부분이 없길래 곰곰히 생각해보니 불필요하더라.
정렬된 리스트의 인덱스를 매핑했다고 했을 때, 마지막에 남게 되는 인덱스는 같은 값 중 정렬 후 맨 뒤에 오는 인덱스일 것이다.
버블 소트는 Stable Sort이므로, 정렬 후 맨 뒤에 왔다면 정렬 전에도 같은 원소 중 맨 뒤에 위치했을 것이다.
따라서, 같은 원소 중 마지막 원소의 이동 거리는 제대로 구해졌다.
한편, 같은 원소 중 마지막 원소가 아닌 원소들은, 최대로 움직여도 마지막 원소보다 더 많이 움직일 수는 없다.
왜냐하면, 같은 원소 중 앞쪽에 있는 \(A\)와 뒤쪽에 있는 \(B\)에 대해, \(A\)가 \(X\)번 앞으로 움직였다면, \(A\) 앞에 적어도 \(X\)개의 \(A\)보다 큰 값이 있는 건데, 이 값들은 당연히 \(B\)보다도 크고(\(A = B\)이므로), \(B\)보다 앞에 등장하기 때문에(\(A\)보다 \(B\)가 뒤에 있으므로), \(B\) 역시 최소한 \(X\)번은 앞으로 움직이는 것이 보장되기 때문이다.
정답을 구하기 위해서는 앞으로 움직인 거리의 최댓값을 구해야 하므로, \(A\)의 이동 정보가 유실되는 것은 상관 없다.
아무튼, 구현은 간단한데 머리를 쓸 부분이 꽤 많은 문제였다.
듣기로는 10090번 문제가 사실상 같은 문제라던데, 한번 풀어봐야겠다.
#!python
from sys import stdin
input = stdin.readline
n = int(input())
A = [int(input()) for _ in range(n)]
A_sorted = list(sorted(A))
# idx[e]는 정렬된 리스트에서 원소 e의 인덱스
# 같은 수가 여러 개인 경우 가장 뒤쪽 인덱스
# 같은 수가 여러 개면 항상 뒤쪽에 있는 숫자가 더 많거나 같게 움직일 것이기 때문이다
idx = [0] * 1000001
for i, e in enumerate(A_sorted):
idx[e] = i
# 원래 인덱스 - 정렬된 후의 인덱스가 가장 큰 값인 것에 1을 더한다
# 정렬이 완료된 후 그 다음 반복의 i를 반환해야 하기 때문
print(max((i - idx[A[i]] for i in range(n))) + 1)
2024
맨 위로 이동 ↑2023
백준(BOJ) 2045 마방진 / 3192 매직 스퀘어 파이썬(Python)
문제 링크 문제 링크
세그먼트 트리
개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...
벨만-포드 알고리즘
개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...
다익스트라 알고리즘
개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...