class BinaryHeap(object):
def __init__(self):
self.items = [None]
def __len__(self):
return len(self.items) - 1 # 배열의 마지막 인덱스를 가리키게끔 함
def _percolate_up(self): # insert에서 쓰일 내부 함수이므로 앞에 _를 붙임
idx = len(self)
parent = idx // 2
while parent > 0:
if self.items[idx] < self.items[parent]:
self.items[parent], self.items[idx] = self.items[idx], self.items[parent]
idx = parent
parent = idx // 2
def insert(self, k):
self.items.append(k) # 일단 맨 뒤에 붙인 후
self._percolate_up() # 최소 힙을 만족할 때 까지 자식, 부모 값 계속 변경
def _percolate_down(self, idx):
left = idx * 2
right = idx * 2 + 1
smallest = idx
if left <= len(self) and self.items[left] < self.items[smallest]:
smallest = left
if right <= len(self) and self.items[left] < self.items[smallest]:
smallest = right
if smallest != idx:
self.items[idx], self.items[smallest] = self.items[smallest], self.items[idx]
self._percolate_down(smallest)
def extract(self):
extracted = self.items[1]
self.items[1] = self.items[len(self)]
self.items.pop()
self._percolate_down(1)
return extracted
원형으로 앉아있는 사람들 N명끼리 1 ~ N이 써져 있는 카드를 뽑고 버린 후, 뽑은 숫자만큼 공을 오른쪽으로 패스해서, 모든 사람들이 1번씩 공을 패스받았을 때 공이 이동한 순서를 출력하는 문제이다.
N번 카드를 뽑는 것은 공을 맨 처음 가지고 있는 1번 사람만이 가능하다. 1번 사람을 제외한 모든 사람은 공을 받으려면 일단 타인에게 패스를 받아야 하는데, N번 카드를 뽑으면 공이 한 바퀴 돌아서 자신에게 돌아오기 때문에 패스를 2번 받게 되어버리기 때문이다.
첫 번째 사람을 N번 카드를 뽑는다고 고정시키면, 나머지 카드는 1 ~ N-1이 남게 된다. 그런데 N이 홀수라면, 남은 카드의 합 (N(N-1) / 2) - N이 N의 배수가 되어 첫 번째 사람이 패스를 최소 1번 추가로 받게 된다. 따라서 N이 1을 제외한 홀수인 경우 모든 사람이 한 번씩만 패스를 받을 수는 없다.
N이 짝수인 경우 N, 1, N-2, 3, N-4, 5, N-6, 7 ... 순으로 카드를 뽑아서 패스할 경우 모든 사람이 한 번씩만 패스를 받을 수 있다. 다른 경우도 더 존재할 것 같지만 저런 케이스를 출력하여 문제를 해결하였다.
소스 코드
import sys
N = int(sys.stdin.readline())
if N == 1:
print(1)
exit(0)
if N % 2 == 1:
print(-1)
exit(0)
answer = []
left = N
right = 1
while(True):
answer.append(str(left))
left -= 2
if len(answer) == N:
break
answer.append(str(right))
right += 2
if len(answer) == N:
break
print(' '.join(answer))
직사각형 NxM 텃밭에 즈티가 가로 한 줄, 혹은 세로 한 줄을 지정해 임의의 연속한 K개의 딸기를 심고, 레오가 가로 한 줄, 혹은 세로 한 줄을 지정해 임의의 연속한 토마토 K개를 심는다. 씨앗의 종류에 상관 없이 씨앗이 심어진 영역의 좌표가 주어질 때, 딸기와 토마토가 모두 자라는 텃밭 영역의 칸 수와 해당 칸수를 출력하는 문제이다.
텃밭에서 씨앗이 심겨진 칸의 개수를 seed라 하자. 그렇다면 2K - seed의 값이 딸기와 토마토가 같이 심어진 칸의 수임을 쉽게 유추할 수 있을 것이다. 이 경우에 아래의 3가지 경우를 고려할 수 있다.
1. 2K == seed
이 경우에는 딸기와 토마토가 어떠한 영역에도 같이 심어지지 않았을 것이다. 같이 심어졌으려면 seed가 2K보다는 적어야 한다. 그냥 0을 출력해주면 된다.
1.5. K == 1
2K == seed가 아니면서 K == 1이면 board를 살펴보다가 1이 나오는 순간 그 지점의 좌표를 출력해주면 된다.
2. 2K - 1 == seed
딸기와 토마토가 같이 심겨진 영역이 한 칸만 존재하는 경우이다. 딸기를 심는 영역과 토마토를 심는 영역이 가로, 세로 직선이 교차하면서 생기는 경우가 있는데, 그 경우에는 같이 심기는 공간이 1칸만 존재할 수 있고, 2K - 1 == seed일때 이러한 상황이 발생할 수 있다. 따라서 2K - 1일때 모든 칸에 대해 현재 칸에 씨앗이 심겨져 있고, 가로로 왼쪽 혹은 오른쪽에 씨앗이 존재하면서 세로로 위쪽 혹은 아래쪽에 씨앗이 존재하는 경우에는 교차하면서 같이 심기는 경우로 판단하여 한 칸의 좌표만 출력해주었다.
3. 2K - 1 >= seed
seed가 2K - 1보다 작거나, 2K - 1 == seed 인데 가로 세로 직선이 교차하면서 같이 심기는게 아닌 경우가 있다. 이 때는 딸기 영역과 토마토 영역이 가로 직선 - 가로 직선이 겹치거나, 세로 직선 - 세로 직선이 겹쳐서 같이 심기는 영역이 발생하는 경우이다. board를 확인하면서 가로-가로, 세로-세로 겹침중 어느 것인지 판단 후, 겹친 갯수와 겹친 부분을 출력해주면 된다. 겹친 부분은 겹치기 시작한 부분 + seed - K부터 1씩 늘려가면서 2K-S개를 세주면 구할 수 있다. 왜 이렇게 되는지 모르겠다면 코드를 참고하고 그림을 그려가며 생각해보자.
소스 코드
import sys
def one_check(b, N, M):
dx = [1, -1]
dy = [1, -1]
for y in range(N):
for x in range(M):
if board[y][x] == 0:
continue
check_x = False
check_y = False
for i in range(2):
nx = x + dx[i]
if 0 <= nx < M and board[y][nx] == 1:
check_x = True
ny = y + dy[i]
if 0 <= ny < N and board[ny][x] == 1:
check_y = True
if check_x and check_y:
return f'{y+1} {x+1}'
return None
N, M, K = map(int, sys.stdin.readline().split())
board = []
for _ in range(N):
board.append(list(map(int, sys.stdin.readline().split())))
seed = 0
for i in board:
for j in i:
if j == 1:
seed += 1
if 2*K == seed:
print(0)
exit(0)
print(2*K - seed)
if K == 1:
for y in range(N):
for x in range(M):
if board[y][x] == 1:
print(f'{y+1} {x+1}')
exit(0)
if 2*K - 1 == seed:
check = one_check(board, N, M)
if check is not None:
print(check)
exit(0)
start_x, start_y = 2001, 2001
end_x, end_y = -1, -1
for y in range(N):
for x in range(M):
if board[y][x] == 1:
start_x = min(x, start_x)
start_y = min(y, start_y)
end_x = max(x, end_x)
end_y = max(y, end_y)
if start_x == end_x:
for i in range(2*K - seed):
print(f'{start_y + seed - K + i + 1} {start_x + 1}')
exit(0)
if start_y == end_y:
for i in range(2*K - seed):
print(f'{start_y + 1} {start_x + seed - K + i + 1}')
서로 다른 정수 N개의 모든 쌍의 차를 구할 때, 서로 다른 차의 개수의 최대값과 최소값을 구하는 문제이다.
모든 쌍의 개수는 NC2 = N(N-1) / 2 이고 NC2개의 모든 쌍의 차가 전부 다른 값을 가질 때 서로 다른 차의 개수가 최대가 될 것 같다. 이런 경우가 존재하는지 생각해보자.
특정 수의 배수로도 만들어보고, 소수들로만도 한번 해보고... 여러 숫자를 넣어가면서 규칙을 찾다보면 1, 2, 4, 8... 과 같은 등비수열에서 모든 쌍의 차가 다른 값을 가짐을 파악할 수 있다. 마침 문제에서 N도 최대 30으로 주었고, 2^30이 int의 최대값을 넘어가지 않으므로 2배씩 커지는 등비수열을 출력해주면 실례가 된다. 서로 다른 차의 개수의 최대값은 N(N-1) / 2, 실례는 공비를 2로 갖는 등비수열을 출력해주면 된다.
서로 다른 차의 개수가 최소가 되는 경우는 언제인가? 여러가지 수를 넣어보면서 규칙을 찾다 보면 1, 2, 3, 4... 나 2, 4, 6, 8... 과 같은 등차수열에서 서로 다른 차의 개수가 N-1개로 가장 적어보인다. 다른 숫자 쌍을 넣어봐도 N-1개 보다 줄어드는 경우는 나타나지 않는다. 따라서 서로 다른 차의 개수의 최소값은 N-1, 실례는 임의의 공차를 갖는 등차수열을 출력하면 문제가 풀릴 것 같다.
실제로 코드를 작성하니 문제가 해결되었다.
소스 코드
import sys
N = int(sys.stdin.readline())
print(N*(N-1) // 2)
number = 1
for _ in range(N):
print(number, end=' ')
number *= 2
print()
print(N-1)
number = 1
for _ in range(N):
print(number, end=' ')
number += 1
이진 탐색 트리의 특성상 특정 노드의 왼쪽 서브트리에는 자신보다 작은 노드 값을 가진 노드들만이 존재하고, 오른쪽 서브트리에는 큰 노드 값을 가진 노드들만이 존재한다.
자신보다 작으면서 차이는 가장 적은 노드 값을 찾으려면 어느 노드에 방문해야 할까? 왼쪽 자식 노드로 한번 이동해서, (자신보다 작은 노드 값들 중에서) 가능한 오른쪽으로 쭉 이동하면, (그 중에서 가장 큰 노드 값으로 가면) 원하는 노드 값을 찾을 수 있다.
마찬가지로, 자신보다 크면서 차이는 가장 적은 노드 값을 찾으려면 오른쪽 자식 노드로 한번 이동 후. 가능한 왼쪽 자식 노드로 쭉 이동하면 원하는 노드 값을 찾을 수 있다.
트리의 3가지 순회 방법중, 왼쪽 서브트리 -> 루트 -> 오른쪽 서브트리 순으로 방문하는 중위 순회를 이용해 순회하고, 현재 노드를 순회하기 전에 방문했던 노드 값을 저장하고 있는 변수를 두면 모든 노드에서 자신보다 작거나, 크면서 차이가 가장 적은 노드 값과 자신의 노드 값과의 차를 구할 수 있고, 그 중 가장 작은 값을 정답으로 반환해주면 된다.
[10, 5, 15, 3, 7, 11, 17]을 노드 값으로 가지고 있는 이진 탐색 트리의 예시 그림이다. 중위 순회의 방문 순서를 같이 표시하였는데, 특정 노드에서 왼쪽 -> 오른쪽 쭉.... 의 노드와 오른쪽 -> 왼쪽 쭉....의 노드 방문 순서가 1씩 나므로, 현재 노드 값 - 이전 방문 노드 값을 모든 노드에서 구해주면 임의의 두 노드의 차 중 가장 작은 값을 확인할 수 있다.
방학때 알고리즘 특강을 듣고 알고리즘 문제 풀이에 어느정도 자신감이 생겼는데, 학교 홈페이지에서 위와 같은 공고가 보여서 신청해봤다.
학교에서 추천서를 받거나, COS PRO라는 ybm의 자격증이 이미 있으면 예선 시험은 치루지 않고 본선 시험을 바로 볼 수 있었지만, 난 둘 다 해당되지 않아서 8월 26일 금요일에 신촌으로 시험을 보러갔다.
예선은 10문제에 90분, 1문제에 9분만에 문제를 풀어야 하므로, 문제 난이도는 쉬울 것이라고 생각했고 실제로 난이도도 쉬운편이었다. 3시간 시험이었던 것으로 기억하는데 시험 시작 30분만에 나가신 분도 계시더라...
90분만에 10문제를 전부 알고리즘 구현 문제를 내면 시간이 모자라거나, 너무 쉬운 문제를 낼 수 밖에 없어서인지 코드 일부분 수정, 핵심 구현부 몇 줄 추가, 다른 시험에서는 볼 수 없었던 생소한 유형의 문제들이 있었다.
문제의 난이도는 대체로 쉬운 편이긴 했지만 그 중 한 문제는 내가 푼 풀이가 정해인지 확신할수 없었다... 가 아니라 아마 정해가 아니었을 것이다. 문제에서 실행 제한 시간을 주진 않았고, 테스트 케이스에서는 정답을 띄우긴 했지만, 내고 나오면서도 이건 비공개 테스트 케이스에서 시간 효율성 문제로 문제가 생기겠구나... 싶었다.
예선은 통과했다. 문제 난이도가 낮았던 만큼 아마 참가자의 대부분이 본선에 진출하지 않았을까 싶다. 본선에서 좋은 성적을 거둬 시상식에 한번 참석해보고 싶다...
이진 탐색 트리에서 low <= node.val <= high인 노드의 합을 구하는 문제이다.
이진 탐색 트리의 특성상 어떤 노드의 왼쪽 서브 트리에는 더 작은 노드 값을 가지고 있는 노드들만, 오른쪽 서브 트리에는 더 큰 노드 값을 가지고 있는 노드들만 존재한다.
루트 -> 왼쪽 서브 트리 -> 오른쪽 서브 트리 순으로 순회하는 전위 순회 방법으로 문제를 해결하였다.
현재 순회중인 노드 값이 low 보다 낮다면, 이진 탐색 트리의 특성상 왼쪽 서브 트리에 있는 노드들은 low보다 작은 값을 가질 것이므로, 순회할 필요가 없고, 현재 순회중인 노드 값이 high보다 크다면, 오른쪽 서브 트리에 있는 노드들은 high보다 큰 값을 가질 것이므로 마찬가지로 순회할 필요가 없다.
위와 같은 특성을 이용하면 풀이 시간이 줄어들지만, 그냥 모든 노드를 다 탐색해도 시간 초과가 발생하지는 않는 문제였다.
소스 코드
class Solution:
sum = 0
def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
if not root:
return None
if low <= root.val <= high:
self.sum += root.val
self.rangeSumBST(root.left, low, high)
self.rangeSumBST(root.right, low, high)
elif root.val < low:
self.rangeSumBST(root.right, low, high)
elif high < root.val:
self.rangeSumBST(root.left, low, high)
return self.sum
