(전공복습) 데이터과학 4. 시각화
차례
백준(BOJ) 1355 구멍난 케이크 자르기 파이썬(Python)
약간의 관찰력과 창의성이 필요한 문제.
케이크와 구멍의 크기를 2배로 스케일한 다음, 구멍을 0, 케이크를 1로 하고 자를 때마다 해당되는 위치를 0으로 바꾸고 연결 요소(Connected Component)를 세는 풀이가 있던데, 사실 훨씬 간단한 풀이가 있다.
우선, 구멍이 있는 케이크는 너무 복잡하니 구멍이 없는 케이크부터 생각해보자.
이 경우 답은 매우 간단하다. 축 별로 자른 횟수에 1을 더한 다음 곱해주면 된다(즉, \((V+1)(H+1)\)).
이제 그 조각 중에서, 온전히 구멍에만 속하는 조각의 개수를 빼주면 정답이 된다.
여기서 온전히 구멍에만 속하는 조각이란, 조각의 모든 변이 구멍 내부에 있는 경우를 이야기한다.
예를 들어, 구멍을 수평, 수직으로 각각 2번 잘랐다면 9개의 조각이 생기는데, 정가운데의 조각이 바로 온전히 구멍에만 속하는 조각이다.
나머지 조각들은 적어도 하나의 변이 구멍의 경계에 맞닿아 있기 때문이다.
이를 구하기 위해서는, 구멍 내부를 지나는 절단면 개수(각각 \(v\), \(h\)라 하자)에서 축 별로 1을 빼주면 되는데, 이게 성립하는 이유는, 온전히 구멍에만 속하는 조각은 결국 축 별로 두 번씩 그어 구멍의 경계 부분을 버리고, 남은 내부를 자른 후의 조각이기 때문이다(즉, \((v-2+1)(h-2+1) = (v-1)(h-1)\)).
즉, 최종적으로 주어진 좌표를 통해 \(v\)와 \(h\)를 구한 이후, \((V+1)(H+1) - (v-1)(h-1)\)을 계산하면 답이 나온다.
이때, 몇 가지 엣지 케이스가 있는데, 한번 살펴보자.
첫째로, 정확히 구멍과 케이크의 경계를 자르는 경우이다. 이 경우는 구멍의 내부를 자른 것과 동일하게 처리해주면 된다.
한번 그려보면 그 이유를 바로 알 수 있는데, 경계를 잘라도 절단면이 구멍에 포함되게 되기 때문이다.
둘째로, \(h\) 또는 \(v\)가 0인 경우, 즉 적어도 하나의 축에 대해 구멍을 안 자른 경우이다. 조금 더 세부적으로 나누어 생각해 보자.
우선, 두 축으로 안 자르는 경우(\(v=h=0\))에, \((v-1)(h-1) = (0-1)(0-1) = 1\)이 된댜. 그러나 이때 실제로 구멍에 속한 조각 수는 하나도 없으므로 답이 0이 되어야 함은 자명하다.
따라서, \(v = h = 0\)인 경우 예외처리가 필요하다.
그 다음, 한 축으로만 자르는 경우인데(예를 들어 \(v=0\), \(h\ne0\)), 이 경우 구멍이 없는 케이크보다 오히려 조각 수가 늘어나는 것을 알 수 있다.
이런 일이 일어나는 이유는 한 축(\(v\))에서 구멍에 속한 절단면이 0개일 때, 다른 축(\(h\))에서 구멍에 속한 절단면의 구간 내부에서 구멍 역시 하나의 절단면으로 기능해서 \(h - 1\)개의 조각이 추가로 생기기 때문이다.
간단한 예시로, 예제 입력 2를 그려 보면 바로 이해할 수 있다.
그런데, 사실 이 경우는 따로 예외처리를 할 필요가 없다. 예를 들어 \(v=0\)이고 \(h=2\)라고 하자.
\((v-1)(h-1) = (0-1)(2-1) = -1 = h-1\)이 된다.
즉, 이 경우 논리적으로 우리가 고려한 경우는 아니지만, 수식 상 같은 값이 나오기 때문에 따로 처리해줄 필요가 없는 것이다.
아무튼, 요약하자면 큰 사각형의 조각 수를 세고, 작은 사각형에만 온전히 속하는 조각 수를 센 다음에, 그 차를 구하면 그게 답이 된다.
#!python
from sys import stdin
input = stdin.readline
lc, lh = map(int, input().split())
# 큰 사각형(구멍이 없는 케이크)이 몇 개로 나뉘는지 계산한 이후
# 그 구멍 중 작은 사각형(구멍)에 속하는 조각만큼 빼주면 된다
# 수평으로 자르는 경우 계산
hc = int(input()) + 1
hh = -1
for h in map(int, input().split()):
if -lh <= h <= lh:
hh += 1
# 수직으로 자르는 경우 계산
vc = int(input()) + 1
vh = -1
for v in map(int, input().split()):
if -lh <= v <= lh:
vh += 1
# 구멍 안에 하나의 선도 없는 경우 0으로 계산
if hh == vh == -1:
hh = 0
# 큰 사각형의 조각 수에서 작은 사각형 내부로 들어간 조각들을 찾아 빼준다
print(hc * vc - hh * vh)
2024
맨 위로 이동 ↑2023
백준(BOJ) 2045 마방진 / 3192 매직 스퀘어 파이썬(Python)
문제 링크 문제 링크
세그먼트 트리
개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...
벨만-포드 알고리즘
개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...
다익스트라 알고리즘
개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...