(전공복습) 데이터과학 4. 시각화
차례
백준(BOJ) 1332 풀자 파이썬(Python)
간단한 이중 for문 문제.
사실 왜 이게 골드 3씩이나 되는지 모르겠다.
입력 크기가 매우 작아서 정말 나이브하게, 그냥 순회하면서 조건에 만족하는 경우를 구하면 된다.
다만, 한번만 순회하면서 거리의 최소값을 구하려고 하면 부딪힐 수 있는 문제가 있는데, 한 칸씩 움직이느냐 두 칸씩 움직이느냐에 따라서 이동 횟수에 약간의 차이가 생길 수 있다는 점이다.
즉, 짝수 번째 문제와 홀수 번째 문제 사이의 거리 처리가 조금 애매할 수가 있다.
따라서, 그냥 문제 전체를 이중 for문으로 순회해서 가능한 모든 경우의 거리를 구하면 된다.
크게 어려울 건 없는 문제.
#!python
n, v = map(int, input().split())
nums = list(map(int, input().split()))
ans = n
# 이중 반복
for i in range(n):
for j in range(i):
# 차가 v 이상이면 시작점에서 j까지의 거리 + j에서 i까지의 거리를 계산한 후 더한다
if abs(nums[i] - nums[j]) >= v:
dist_j = (j + 1) // 2
dist_i = (i - j + 1) // 2
ans = min(ans, dist_i + dist_j + 1)
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) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...