오늘은 유윤선 코치님과 함께 커피챗을 했습니다. 정말 다양한 정보와 진로에 관한 상담을 해주셨고, 많은 도움이 되었습니다. 오늘도 어김없이 8983 사냥꾼, 2630 색종이만들기, 1629 곱셈 백준 문제를 풀어보았습니다.
6번 (8983) 사냥꾼
https://www.acmicpc.net/problem/8983
원래는 어려워보여서 다른문제를 풀다 다시왔다. 근데 생긴 코드와 달리 해석을 해보니 간단한 문제였다.
import sys
# 1. 입력 받기
data = sys.stdin.read().split()
M, N, L = map(int, data[:3]) # 사대 개수, 동물 개수, 사정거리 (인덱스 0~2까지)
shooters = sorted(map(int, data[3:M+3])) # 사대 위치 재정렬(3부터 사대 수+2까지)
animals = list(zip(map(int, data[M+3::2]), map(int, data[M+4::2]))) # 동물 좌표(x,y)
# 2. 이진 탐색 함수 (가장 가까운 사대 찾기)
def can_hunt(x, y):
left, right = 0, M - 1 # 0부터 시작이므로 실제 M값은 M-1까지이다.
while left <= right: # while 종료 조건문
mid = (left + right) // 2 # 중앙값 (가까운 사대를 찾기 위한 이진 탐색)
shooter = shooters[mid] # 중앙값을 쓰기 편하게 변환
# 사냥 조건 |x - a| + b ≤ L 확인
# |x - a|는 사대와 동물의 가로 거리이다.
# b는 동물의 세로 거리이다.
# 합이 L(사정거리) 이하면 사냥 가능하다.
# 이게 난 피타고라스로 풀어야하는줄 알았는데 좌표로 나타내므로 가로세로의 합으로 사정거리 적합도를 판단해도된다.
if abs(shooter - x) + y <= L:
return True # 사정거리 이하이므로 사냥 가능
elif shooter < x: # x가 사냥꾼보다 크면
left = mid + 1 # 더 오른쪽 탐색(동물이 오른쪽에 있으므로)
else: # 그외경우 x가 사냥꾼보다 작으면같은...
right = mid - 1 # 더 왼쪽 탐색(동물이 왼쪽에 있으므로)
return False # 사냥 불가능(둘다 안되는 경우)
# 3. 동물 탐색 및 사냥 개수 계산
count = sum(1 for x, y in animals if can_hunt(x, y))
# 사냥되는 동물 좌표에 대해 can_hunt(x, y) = True이면 1을 부여
# 4. 결과 출력
print(count)앞서말한것처럼 생각보다 쉬운 문제였다. 나는 어렵게 피타고라스의 정의써서 대각선을 구해야하는줄 알았는데, 팀원분께 여쭤보니, 좌표라서 그럴 필요가 없었다. 어디든 사정거리 값으로 비교하면된다.
7번 (2630) 색종이 만들기
https://www.acmicpc.net/problem/2630
문제는 분할 정복을 통해 색종이가 파란색과 흰색인 부분의 갯수를 찾는 것이 목표이다. 일일이 세는 것은 굉장히 오래걸리기 때문에 분할정복과 재귀를 사용한다. 주 핵심은 전체적인 검사를 통해 같은 색이 아니라면 4등분을 합니다. 그후 다시 재귀호출합니다. 나눠진 상태에서 같은 색인지 확인하고 아니라면 4등분을 다시하고 재귀호출합니다. 나눠진 상태에서 색이 같다면 해당 색을 +1 합니다. 나눌수 없는 범위까지 나누면 색이 완벽히 나눠질 것이다. 해당 상태에서 최종적인 흰색과 파란색의 갯수를 출력한다.
import sys
# 인풋받기
N = int(sys.stdin.readline())
paper = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] # 색종이 만들기
# 결과 담을 리스트
result = []
def solution(row, col, N) :
color = paper[row][col] # 첫번째 칸의 색상 저장(기준)
for i in range(row, row+N): # i는 x부터 x+N(끝까지) 검사
for j in range(col, col+N): # j는 y부터 y+N(끝까지) 검사
if color != paper[i][j]: # 기준값과 현재 검사중인 좌표값이 다를때 분할 시행
solution(row, col, N//2) ### 왼쪽위 2사분면 분할
solution(row, col+N//2,N//2) ### 오른쪽위 1사분면 분할
solution(row+N//2, col, N//2) ### 왼쪽 아래 3사분면 분할
solution(row+N//2, col+N//2, N//2) ### 오른쪽 아래 4사분면 분할
return
# 모든 칸이 같은 색이면 각각의 색상 카운트를 증가
if color == 0:
result.append(0)
else:
result.append(1)
solution(0,0,N) # 0,0 지점부터 재귀 호출 시작
print(result.count(0)) # 각 색깔별로 갯수 출력
print(result.count(1))이론은 어느정도 이해가 간다. 분할된 곳이 같은 색만 나올때까지 재귀 분할 하는 논리이다. 그런데 코드에 나누는 식이 이해가 잘 되지는 않는다. 대강 어떤 느낌인지는 알겠는데... 일단 넘어가고 복습시 다시 보는 걸로 하겠다.
8번 (1629) 곱셈
https://www.acmicpc.net/problem/1629
팀원분의 힌트로 규칙을 찾았습니다. A를 B번 곱했을 때 C나누기의 나머지는 항상 같습니다. 또한 모듈러 연산이라고 (axb)%c = (a%c)*(a%c)%c 는 성립합니다. 첫번째 시도로 그냥 제곱한 수로 나누어 봤더니 overflow가 나와서 실패했다. 두번째 시도는 제곱을 반으로 나누어서 다시 제곱하는 것으로 바꾸어보았다. 세번째 시도는 GPT의 도움을 받아 수정하였다. pow를 사용힌 제곱 연산은 실수 연산으로 큰 수에서 오버플로우가 발생할 수 있다고한다. 그러므로 분할 정복을 사용한 (log B) 겁듭제곱 알고리즘을 사용해야한다고 한다. 큰 흐름은 제곱되는 수를 2로 나눈다. 어차피 결과는 같으니까. 근데, 홀수로 곱하면 2, 3, 5의 경우 답이 4로 틀린답이 나와버린다. 반례를 막기위해 B가 홀수면 A를 한번더 곱한다. 또다른 반례를 막기 위해 모듈러 연산을 사용한 나머지를 최종적으로 출력한다.
import sys
# import math
A, B, C = map(int,sys.stdin.readline().split()) # 인풋 받기
# A: 제곱할 수 B: 제곱횟수 C: 나눌 값
# def power(A, B):
# if B == 1:
# return A
# return power(A, B-1) * A
# print(int((power(A,B))%C))
# 위에는 제가 세웠던 식입니다.
# 분할 정복을 사용한 거틉 제곱 재귀함수
def power(A, B, C):
if B == 1: # 제곱수가 1이라면(Base case)
return A % C # A를 C로 나눈 나머지를 내보낸다.
half = power(A, B // 2, C) # 기본적으로 B를 2로 나눈값을 A에 제곱한다.
half = (half * half) % C # 모듈러 연산에 따라 다음 식이 성립합니다.
if B % 2 == 0: # B가 짝수라면 그대로 반환한다.
return half
else: # B가 홀수라면 A를 한 번 더 곱하고 %C를 적용한다.
return (half * A) % C
print(power(A, B, C)) # 계산 완료된 값이 출력된다.해당문제는 팀원분께서 알려주신 모듈러연산을 활용하여 풀 수 있었습니다. A,B,C에 들어가는 값이 크다 보니 직접 돌려보면 overflow가 일어났고 그것을 해결하기 위해 위와 같이 분할 정복과 반례를 방지한 방법을 사용했습니다. 그러나 예상치 못한 반례 방지와 전체적인 코드 구현은 GPT의 도움을 받았기 때문에 다음에 다시 복습하겠습니다.
추가적으로 스택과 큐에 대해서 학습했는데, 그에 관한 내용은 따로 포스팅하겠습니다.
