0. 목차
1. 분할 정복 정리
2. 곱셈
3. 히스토그램에서 가장 큰 직사각형
4. 행렬 제곱
5. 가장 가까운 두 점
1. 분할 정복 정리
분할 정복 알고리즘은 그 자체로 해결할 수 없는 문제를 작은 문제로 쪼개서 해결하는 방법이다. 예시로는 정렬 알고리즘 중에서 퀵 정렬이나병합 정렬(merge sort), 이진 탐색 등이 있다. 방식은 아래와 같다.
1. Divide
주어진 문제를 잘 쪼개서 비슷한 유형의 더 작은 하위 문제로 분할이 가능할 때까지 나눈다.
2. Conquer
각 하위 문제를 재귀적으로 해결한다. 이때, 하위 문제를 더 이상 나눌 수 없는 상황이 되면 종료 조건을 설정하고 해결.
3. Combine
Conquer한 문제를 통합해서 원래 문제의 답을 구한다.
대략 재귀랑 비슷한 방식인데, 뭐랄까..머릿속으로는 어찌어찌 생각해내도 손으로 적는 게 정말 쉽지 않다. 분할 정복은 연습을 많이 해야 할듯.
2. 곱셈 문제
곱셈 문제는 mod를 어떻게 쓸지 고민을 너무 많이 해서 정작 간단하게 풀 수 있는데도 논리 흐름을 놓쳤다. 어줍짢게 알면 오히려 고생한다..
이 문제는 mod 연산자의 성질을 이용하면 쉽게 풀 수 있다.
먼저 mod 연산에 대해 이해해보자. mod는 파이썬에서 나머지를 구하는 것과 똑같은 연산이다.
A mod B == A % B == A를 B로 나눈 나머지
mod 연산이 재밌는 점은 합동에서 나오는데, 이 합동에 너무 신경쓴 나머지 문제를 제대로 못 풀었다...하지만 재밌는 개념이니 소개해본다.두 수 A, B가 각각 C로 나눈 나머지가 같다면, 이 둘을 합동이라고 한다. 예컨대 7과 3 모두 2로 나눈 나머지가 1로 같으므로 7≡2 (mod 3)이다.
근데 이 문제를 풀 때는 아래 공식만 이해하면 된다. 특히 (AXB)를 M으로 나눈 나머지는 (A%M) X (B%M) 을 M으로 나눈 나머지와 같다는 사실!
왜냐? A = Qa * C + Ra , B = Qb * C + Rb (Q는 몫, R은 나머지)라고 하자.
AXB = C(QaQb + QaRb + QbRa) + RaRb이다.
Ra = A % M, Rb = B % M이므로
(AXB)% M == (A%M) * (B%M)) % M이 성립한다. mod 연산에 대한 보다 자세한 설명은 여기.
이를 이용해 A**n 을 A**(n//2)로, n//4로, ...이렇게 계속해서 분할하여 재귀를 돌리면 답을 구할 수 있다. 풀이 코드는 아래와 같다. 이에 대해 정글 선배님께서 풀이를 올려둔 게 있는데 여기를 참고해도 좋다.
from sys import stdin
a, b, c = map(int, stdin.readline().split())
def mod(n, k):
if k == 1:
return n % c
else:
tmp = mod(n, k//2)
if k % 2 == 0:
return (tmp * tmp) % c
else:
return (tmp * tmp * n) % c
print(mod(a, b))
3. 히스토그램에서 가장 큰 직사각형
아..이건 진짜 어려웠는데..히스토그램 문제는 크게 1) 스택을 이용한 풀이와 2) 분할정복을 이용한 풀이가 있다. 이번 공부에서는 시간 관계상 분할 정복을 이용한 풀이만 공부했는데 풀이 난이도는 1) 스택이 훨씬 쉽다고 하니 스택 공부도 해놓을 필요가 있겠다. 분할 정복은..좀 복잡하긴 하다.
본 글에서는 분할 정복를 이용한 풀이만 소개한다. 보다 자세한 내용은 아래 링크를 참조할 것.
링크 2: 유튜브(스택, 분할 정복 1, 분할 정복 2 풀이 - 코드는 X)
분할 정복으로 문제를 풀 경우, 풀이는 이렇다.절반을 기준으로 사각형 영역을 반으로 나눈다. (아래 코드에서 d = len(a) // 2가 여기에 해당) 이때 d가 분할선에 해당하는데, 이 분할선을 기준으로 총 세 가지를 비교해주면 된다.
- 1. 분할선을 기준으로 왼쪽 히스토그램 영역에서 가장 큰 직사각형
- 2. 분할선을 기준으로 오른쪽 히스토그램에서 가장 큰 직사각형
- 3. 분할선을 포함하는 직사각형 중 가장 큰 직사각형
이렇게 세 영역 중 최댓값을 찾는 방식인데, 분할선 d를 기준으로 양쪽으로 한칸씩 늘려가며 너비 중 더 큰 값을 저장한다. 이때 높이를 신경써야 한다! for 문을 계속해서 돌리면서 최댓값을 찾는다.
from sys import stdin
def his_sqr(a):
if len(a) == 1:
return a[0]
if len(a) % 2 == 1:
a = [0] + a
d = len(a) // 2
x = a[:d]
y = a[d:]
cnt = 2
tmpmax = min(a[d - 1], a[d])
tmparea = tmpmax * cnt
i = 0
j = 0
for _ in range(0, len(a) - 2):
if d - 1 - i == 0:
j += 1
elif d + j == len(a) - 1:
i += 1
else:
if a[d - 2 - i] >= a[d + 1 + j]:
i += 1
else:
j += 1
tmpmax = min(tmpmax, a[d - 1 - i], a[d + j])
cnt += 1
tmparea = max(tmparea, tmpmax * cnt)
z = tmparea
return max(his_sqr(x), his_sqr(y), z)
while True:
n, *histogram = list(map(int, stdin.readline().split()))
if n == 0:
break
maxarea = his_sqr(histogram)
print(maxarea)근데 다시 코드를 리뷰해보니까 역시 아무래도 스택을 공부하는 게 나을 듯한데..이렇게 푸는 건 좀 비효율적인 감이 없잖아 있는듯. 분할 정복은 앞으로도 꾸준히 연습할테지만 더 쉽고 빠르게 풀 수 있는 방법을 고민할 필요가 있겠다.
4. 행렬 제곱
이 문제 풀이를 적을까 고민하다가 아래 5번은 그냥 날려 먹은 문제라 이거라도 정리할 필요가 있겠다 싶어 정리.
당당히 분할 정복 문제라 분할 정복으로 접근하려 하기에는 행렬 보자마자 넘파이부터 생각이 났다. numpy 불러와서 푸니까 엄청 빨리 풀었지만 당연히 문제에서 요구하는 방식은 이런 게 아니니..ㅠ + (애초에 백준에서 numpy 제공도 안함)그래도 이런 방법도 있다!라는 거 알려주는 정도로 코드는 공유.
# 1. 넘파이 이용 풀이
from sys import stdin
import numpy as np
n, b = map(int, stdin.readline().split())
A = [list(map(int, stdin.readline().split())) for _ in range(n)]
A = np.array(A)
def sqr(a, n):
m = a
# a는 행렬, n은 제곱수
for _ in range(n-1):
m = np.dot(a, m)
return m
print(sqr(A, b) % 1000)근데 다시 보니 시간 초과 뜰 것 같기도 하고..넘파이 계산이 엄청 빠른 것으로 알고 있어서 np.dot으로 행렬 계산하니 괜찮지 않을까 싶다만서도..그렇지만 for문을 돌리니 기본적으로 시간복잡도가 O(N)이긴 하다.
이를 분할 정복으로 바꾸면 계산 횟수가 눈에 띄게 줄어든다. 행렬 계산은 내장 라이브러리에서는 제공하지 않는 것으로 알고 있어서 행렬곱 메소드부터 짜보자.
# 2. 분할 정복
from sys import stdin, setrecursionlimit
setrecursionlimit(10**6)
n, b = map(int, stdin.readline().split()) # n: 행렬의 크기 b: 제곱수
A = [list(map(int, stdin.readline().split())) for _ in range(n)]
def matrix_mul(a, b):
result = [([0] * n) for _ in range(n)]
for i in range(n):
for j in range(n):
for k in range(n):
result[i][j] += a[i][k]*b[k][j] % 1000
return result
삼중 for문을 돌려야 하는데 (아니 이게 np 쓰는 것보다 복잡한 거 아님?!) 여기서 각 값을 1000으로 나눈 나머지를 행렬곱 결과에 저장한다. 여기서도 나누고 뒤에 제곱 계산한 것에 대해서도 1000으로 나눠야 하는데, 그 이유는 아래 이미지를 다시 보면 알 수 있다. 계속 나눈 나머지에 대한 계산값의 나머지를 구해야 하기 때문이다.
이 뒤부터는 위의 곱셈 문제와 방식이 똑같다. 행렬 곱셈이니 뭔가 mod 연산이 안되지 않나..?라는 생각이 있었는데 한 번 시험삼아 계산해보니 되더라. 사실 행렬곱이라고 한들 결국 곱셈 + 덧셈의 조합이니 위의 방식으로 쪼개기가 가능하다. M으로 나눈 나머지만 계산마다 해주기만 하면 된다. 이에 대해 참고하기 좋은 사이트에서 보면
b = mod(a,m)는 a를 m로 나눈 후 나머지를 반환합니다.
여기서 a는 피제수이고 m는 제수입니다.
이 함수는 흔히 모듈로 연산이라고도 하며
b = a - m.*floor(a./m)으로 표현할 수 있습니다.
mod 함수는 mod(a,0)일 경우 a를 반환한다는 규칙을 따릅니다.
a는 피제수로, 스칼라, 벡터, 행렬, 다차원 배열 중 하나로 지정됩니다. (b는 a를 m으로 나눈 나머지이니 a가 행렬이면 b도 당연히 행렬이겠지)
-mathworks
무튼 그래서 행렬 곱셈 역시 mod를 기반으로 분할 정복을 시도하면 된다.
전체 코드는 여기.
# 2. 분할 정복
from sys import stdin, setrecursionlimit
setrecursionlimit(10**6)
n, b = map(int, stdin.readline().split()) # n: 행렬의 크기 b: 제곱수
A = [list(map(int, stdin.readline().split())) for _ in range(n)]
def matrix_mul(a, b):
result = [([0] * n) for _ in range(n)]
for i in range(n):
for j in range(n):
for k in range(n):
result[i][j] += a[i][k]*b[k][j] % 1000
return result
def divide(mat, sqr): #A: 행렬, b: 제곱수
if sqr == 1:
return mat
if sqr == 2:
return matrix_mul(mat, mat)
else:
tmp = divide(mat, sqr//2)
if sqr % 2 == 0:
return matrix_mul(tmp, tmp)
else:
return matrix_mul(matrix_mul(tmp, tmp), mat)
ans = divide(A, b)
for i in range(n):
li = []
for j in range(n):
print(ans[i][j] % 1000, end=" ")
print()
5. 가장 가까운 두 점
하..진짜 나는 재귀와 분할 정복에 너무너무너무 취약한듯..오늘 분할정복 문제는 30분 시간 제한을 두고 문제를 풀려고 하니 하나도 풀리는 문제가 없었다. 심지어 해설 보는 것도 30분이 넘어가는 마당에..
이 가장 가까운 두 점 문제는 오늘 내 자존감에 바닥을 제대로 찍게 해준 아주 고마운(?) 녀석이다. 풀이를 보니 논리는 알겠는데 코드 구현이 에바다..
풀이 출처는 여기!
보다 자세한 내용을 적고 싶지만..좀 더 공부해서 이해한 뒤 다시 적도록 하겠다..ㅠ
코드는 아래.
import sys, random
input = sys.stdin.readline
n = int(input())
pl = [list(map(int, input().split())) for i in range(n)]
# x축 기준 정렬
pl.sort()
# 두 점 사이의 거리 계산 함수
def getDist(p1, p2):
return (p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2
def dac(start, end):
# 점 하나의 거리는 없으니 최대값 리턴
if start == end:
return float('inf')
# 점이 두 개 남으면 사이의 거리 리턴
if end - start == 1:
return getDist(pl[start], pl[end])
# 분할정복 실행
mid = (start + end) // 2
minDist = min(dac(start, mid), dac(mid, end))
# x축 기준으로 후보 점들을 찾는다.
target_pl = []
for i in range(start, end + 1):
if (pl[mid][0] - pl[i][0]) ** 2 < minDist:
target_pl.append(pl[i])
# y축 기준 정렬
target_pl.sort(key=lambda x: x[1])
# y축 기준으로 후보 점들 사이의 거리 비교
t = len(target_pl)
for i in range(t - 1):
for j in range(i + 1, t):
if (target_pl[i][1] - target_pl[j][1]) ** 2 < minDist:
minDist = min(minDist, getDist(target_pl[i], target_pl[j]))
else:
break
# 현재 후보 점이 다음 점과 최소 거리보다 멀다면 더 볼 필요가 없음.
# 위 처리가 없으면 시간 초과 발생
return minDist
print(dac(0, n - 1))
'정글사관학교 개발일지 > 자료구조&알고리즘' 카테고리의 다른 글
| 정글사관학교 17일차 TIL: 사냥꾼(#8993), 철로(#13334), 파이썬 sort 조건 설정 관련 팁 (0) | 2021.11.18 |
|---|---|
| 정글사관학교 16일차 TIL: 힙 자료구조, heapq 모듈, 가운데를 말해요 (0) | 2021.11.17 |
| 정글사관학교 14일차 TIL: 컴퓨터 시스템 1장 - A Tour of Computer Systems (1-1 ~ 1-4) (0) | 2021.11.15 |
| 정글사관학교 13일차 TIL: 이분 탐색 - 두 용액(투포인터 알고리즘), 가장 긴 증가하는 부분 수열 (1) | 2021.11.14 |
| 정글사관학교 12일차 TIL: 이진 탐색(Binary Search), 파라메트릭 서치 (0) | 2021.11.13 |