분할 정복은 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합치며 답을 얻는 알고리즘이다. 바로 해결할 수 없는 큰 문제를 작은 문제로 나누어 작은 문제를 해결하여 다시 큰 문제를 해결하는 것이다. 대부분 재귀 함수를 통해 구현하며 메모리 제한이 없다면 비교적 빠르게 문제를 해결할 수 있다. 이는 재귀 함수를 통해 전체를 거의 절반으로 분리하기 때문에 가능하다. 분할 정복의 기본 형태를 슈도 코드로 나타내면 다음과 같다.
function F(x) :
if F(x)의 문제가 간단 then :
return F(x)을 직접 계산한 값
else :
x를 y1, y2로 분할
F(y1)과 F(y2)를 호출
return F(y1), F(y2)로부터 F(x)를 구한 값
큰 문제를 2개 이상의 작은 문제 즉 y1과 y2로 나누고 만약 y1 또는 y2가 바로 계산할 수 있다면 계산한 값을 반환함으로써 큰 문제를 해결할 수 있다. 분할 정복을 이용하는 대표적인 문제로를 병합 정렬이 있다.
1. 2630번 색종이 만들기
문제 아래 <그림 1>과 같이 여러개의 정사각형 칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다.
전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수)이라면 종이를 자르는 규칙은 다음과 같다. 전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 <그림 2>의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색 종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의 네 개의 색종이로 나눈다. 이와 같은 과정을 잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다. 위와 같은 규칙에 따라 잘랐을 때 <그림 3>은 <그림 1>의 종이를 처음 나눈 후의 상태를, <그림 4>는 두 번째 나눈 후의 상태를, <그림 5>는 최종적으로 만들어진 다양한 크기의 9장의 하얀색 색종이와 7장의 파란색 색종이를 보여주고 있다. 입력으로 주어진 종이의 한 변의 길이 N과 각 정사각형칸의 색(하얀색 또는 파란색)이 주어질 때 잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하는 프로그램을 작성하시오.
분할 정복 문제를 푸는데 기본은 큰 문제를 어떻게 나눌 것이냐부터 시작한다. 친절하게도 1번 문제에서는 색종이를 4개의 정사각형으로 4 등분하라고 알려주고 있다. 다음으로는 어떤 조건에 분할할지 안 할지를 결정해야 한다. 색종이를 자르는 것에 대한 목표는 정사각형의 파란색 색종이 혹은 하얀색 색종이를 만드는 것이다. 즉 나누고 난 후에 색종이의 총합을 구하면 나누어진 색종이가 파란색 색종이인지, 하얀색 색종이인지 또는 한번 더 분할이 필요한지 결정할 수 있다.
#2630번 색종이 만들기
n = int(input())
color_paper = [[0]*n for i in range(n)]
for i in range(n) :
color_paper[i] = list(map(int,input().split()))
white_count = 0 #흰 색종이 세기
blue_count = 0 # 파란 색종이 세기
def make_color_paper(num,paper) :
global white_count
global blue_count
check = 0 # 색종이가 만들어지는 여부 확인
for i in range(num) :
check += sum(paper[i]) #종이 전체가 섹종이가 되는지 확인하기 위해 총 합을 더함
if check == 0 : # check가 0이라면 흰색종이
white_count += 1
elif check == num*num : # check가 num*num라면 파란 색종이
blue_count += 1
else : # 색종이가 만들어지지 않을 경우
temp = [paper[i][0:num//2] for i in range(0,num//2)] # 4개로 나눠서 위 과정을 반복
make_color_paper(num//2,temp)
temp = [paper[i][0:num//2] for i in range(num//2,num)]
make_color_paper(num//2,temp)
temp = [paper[i][num//2:num] for i in range(0,num//2)]
make_color_paper(num//2,temp)
temp = [paper[i][num//2:num] for i in range(num//2,num)]
make_color_paper(num//2,temp)
make_color_paper(n,color_paper)
print(white_count)
print(blue_count)
2. 1992번 쿼드 트리
문제 흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다. 주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다 위 그림에서 왼쪽의 영상은 오른쪽의 배열과 같이 숫자로 주어지며, 이 영상을 쿼드 트리 구조를 이용하여 압축하면 "(0(0011)(0(0111)01)1)"로 표현된다. N ×N 크기의 영상이 주어질 때, 이 영상을 압축한 결과를 출력하는 프로그램을 작성하시오.
2번 문제도 영상을 정사각형 모양으로 4등분하면 될 것 같다. 나누어진 데이터에 대해서 데이터의 모든 합이 0이라면 0으로 압축 가능하며, 데이터의 모든 합이 데이터의 크기와 같다면 1로 압축 가능하다. 둘 다 아니라면 한번 더 분할을 수행하는데 이때 분할 앞뒤로 '('와 ')'를 출력하면 쿼드 트리 구조에 따라 압축을 표현할 수 있다.
#1992번 쿼드트리
n = int(input())
quadtree = [[0]*n for i in range(n)]
for i in range(n) :
quadtree[i] = list(map(int,list(input())))
def video_compression(num, tree) :
check = 0 # 압축 가능한지 불가능한지 여부 확인
for i in range(num) :
check += sum(tree[i]) # 동영상의 모든 수의 합
if check == 0 :
print(0,end='') # 0으로 압축 가능하면 0출력
elif check == num*num :
print(1,end='') #1로 압축 가능하면 1 출력
else: # 압축이 불가능하다면 4개로 나눔
print('(',end='') # ( 출력
temp = [tree[i][0:num//2] for i in range(0,num//2)] # 4개로 나눠서 순서대로 앞 과정 반복
video_compression(num//2,temp)
temp = [tree[i][num//2:num] for i in range(0,num//2)]
video_compression(num//2,temp)
temp = [tree[i][0:num//2] for i in range(num//2,num)]
video_compression(num//2,temp)
temp = [tree[i][num//2:num] for i in range(num//2,num)]
video_compression(num//2,temp)
print(')',end='') # ) 출력
video_compression(n,quadtree)
3. 1780번 종이의 개수
문제 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. (1). 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다. (2). (1)이 아닌 경우에는 종이를 같은 크기의 9개의 종이로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다. 이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.
분할은 종이를 9등분 하는 것이다. 다음으로 분할하지 안 할지 여부를 check함수를 통해서 구현했다. 분할하지 않는 경우는 종이에 모두 같은 숫자인 경우이다. 잘라진 종이에 모든 숫자를 확인하여 하나라도 다른 게 나오면 바로 False를 반환한다. True를 반환할 경우 각 숫자마다 카운팅 해준다.
#1780번 종이의 개수
n = int(input())
num_paper = [[0]*n for i in range(n)]
for i in range(n) :
num_paper[i] = list(map(int,input().split()))
result = [0,0,0]
def check(x,y,size) : # 정사각형 종이로 사용 가능한지 여부 확인
global num_paper
num = num_paper[x][y] # 가장 처음 숫자
for i in range(x,x+size) : # 정사각형의 모든 숫자에 대해서
for j in range(y,y+size) :
if num_paper[i][j] != num : # 하나라도 다르면
return False # 불가능
return True
def split(x,y,size) : # 종이를 9개로 나누는 함수
global num_paper
global result
if check(x,y,size) : # 정사각형 종이로 사용 가능하면
result[num_paper[x][y]+1] += 1 # result 0,1,2에 각각 -1 0 1의 개수 저장
else :
next_size = size//3 # 새로운 정사각형의 크기
for i in range(3) :
for j in range(3) :
split(x+next_size*i,y+next_size*j,next_size) # 9개의 정사각형으로 나눈 후 위 과정 반복
split(0,0,n)
print(result[0])
print(result[1])
print(result[2])
4. 1629번 곱셈
문제 자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.
A를 B만큼 제곱해주는 데 실제로 B만큼 제곱을 수행하면 시간 초과를 피할 수 없다. 분할 정복의 핵심은 분할할 때 큰 문제를 최대한 절반에 가깝게 나누는 것이다. B가 짝수라면 A^B = A^(B/2)*A^(B/2)이고, B가 홀수라면 A^B = A*A^(B/2)*A^(B/2)라는 공식을 통해 B제곱을 절반으로 분할하여 문제를 해결한다. 이렇게 제곱을 분할하여 문제를 푸는 방식은 분할 정복에서 자주 나오는 유형이다.
문제 자연수 N과 정수 K가 주어졌을 때 이항 계수 NCK를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.
이 문제를 분할 정복을 통해 풀기 위해서는 먼저 페르마의 소정리에 대해서 알아야 한다. 페르마의 소정리란 p가 소수이고 a가 정수일 때 a^p(mod p) = a(mod p)를 만족한다는 것이다. 페르마의 소정리에 의해 a^(p-1)(mod p) = 1(mod p)도 성립되는데 이를 통해 이항 계수 N C K를 다음과 같이 정리할 수 있다.
여기서 이제 팩토리얼과 제곱을 구해야 하는데 팩토리얼의 경우 팩토리얼 자체를 구하는 게 아닌 팩토리얼을 구하고 p로 나눈 나머지를 구하는 것이기 때문에 하나씩 곱할 때마다 p로 나눠서 메모리 제한을 회피할 수 있다. 다음으로 (p-2) 제곱을 구해야 하는데 이는 앞선 3번 문제와 마찬가지로 제곱에서의 분할 정복을 통해 해결할 수 있다.
#11401번 이항 계수
n,k = map(int,input().split())
mod = 1000000007
def fac(num) :
temp = 1
for i in range(1,num+1) :
temp *= i
if temp > mod :
temp %= mod
return temp
def pow(num, square) :#분할정복, 제곱을 빠르게
if square == 0 :
return 1
elif square %2 == 0 :
return (pow(num,square//2)**2) %mod
else :
return (pow(num,square//2)**2 * num) %mod
a = fac(n)%mod # 페르마의 소정리
b = pow(fac(k)%mod,mod-2)
c = pow(fac(n-k)%mod,mod-2)
result = a*b*c%mod
print(result)
6. 2740번 행렬 곱셈
문제 N*M크기의 행렬 A와 M*K크기의 행렬 B가 주어졌을 때, 두 행렬을 곱하는 프로그램을 작성하시오.
두 개의 행렬을 입력받고 각 행렬의 원소들에 일일이 접근하여 곱하고 새로운 행렬을 만드는 방법으로도 문제를 해결할 수 있다. 하지만 이러한 방법을 분할 정복 알고리즘이라고 할 수 없다.
#2740번 행렬 곱셈
n,m = map(int,input().split())
A = [[0]*m for i in range(n)]
for i in range(n) :
A[i] = list(map(int,input().split()))
m, k = map(int,input().split())
B = [[0]*k for i in range(m)]
for i in range(m) :
B[i] = list(map(int,input().split()))
C = [[0]*k for i in range(n)]
def multi(i,j) :
temp = 0
for l in range(m) :
temp += A[i][l]*B[l][j]
return temp
for i in range(n) :
for j in range(k) :
C[i][j] = multi(i,j)
print(C[i][j],end=' ')
print()
행렬 곱셈 문제를 분할 정복으로 해결하기 위해서는 먼저 슈트 라센 알고리즘에 대해서 알아야 한다. 슈트라센 알고리즘이란 행렬 곱셈을 일일이 계산하여 구할 경우 O(n^3) 걸리지만 각 행렬들은 4개의 행렬로 분할하여 어떠한 공식을 통해 O(n^2.807)의 시간이 걸리도록 해주는 알고리즘이다. 입력받은 행렬을 각각 4사분면으로 4개의 행렬로 나눈 뒤 슈트라센 알고리즘의 공식에 따라 계산하면 행렬 곱셈을 구할 수 있다. 공식 자체가 길어서 코드도 길어 보이지만 그렇게 어려운 문제는 아니다.
#2740번 행렬 곱셈_슈트라센 알고리즘
def squard_2(num1,num2,num3) :
num = max(num1,num2,num3)
squard = 0
while num > 2**squard :
squard += 1
return 2**squard
n,m = map(int,input().split())
A = [[0]*m for i in range(n)]
for i in range(n) :
A[i] = list(map(int,input().split()))
m, k = map(int,input().split())
B = [[0]*k for i in range(m)]
for i in range(m) :
B[i] = list(map(int,input().split()))
size = squard_2(n,m,k)
for i in range(size) :
if i < n :
for j in range(size-m) :
A[i].append(0)
else :
A.append([0]*size)
for i in range(size) :
if i < m :
for j in range(size-k) :
B[i].append(0)
else :
B.append([0]*size)
def plus(mat1, mat2) :
size = len(mat1)
result = [[0]*size for i in range(size)]
for i in range(size) :
for j in range(size) :
result[i][j] = mat1[i][j] + mat2[i][j]
return result
def minus(mat1, mat2) :
size = len(mat1)
result = [[0]*size for i in range(size)]
for i in range(size) :
for j in range(size) :
result[i][j] = mat1[i][j] - mat2[i][j]
return result
def strassen(A,B,size) :
C = [[0]*size for i in range(size)]
if size == 1 :
C[0][0] = A[0][0]*B[0][0]
return C
size_ = size//2
A11 = [[0]*size_ for i in range(size_)]
A12 = [[0]*size_ for i in range(size_)]
A21 = [[0]*size_ for i in range(size_)]
A22 = [[0]*size_ for i in range(size_)]
B11 = [[0]*size_ for i in range(size_)]
B12 = [[0]*size_ for i in range(size_)]
B21 = [[0]*size_ for i in range(size_)]
B22 = [[0]*size_ for i in range(size_)]
C11 = [[0]*size_ for i in range(size_)]
C12 = [[0]*size_ for i in range(size_)]
C21 = [[0]*size_ for i in range(size_)]
C22 = [[0]*size_ for i in range(size_)]
for i in range(size_) :
for j in range(size_) :
A11[i][j] = A[i][j]
A12[i][j] = A[i][j+size_]
A21[i][j] = A[i+size_][j]
A22[i][j] = A[i+size_][j+size_]
B11[i][j] = B[i][j]
B12[i][j] = B[i][j+size_]
B21[i][j] = B[i+size_][j]
B22[i][j] = B[i+size_][j+size_]
M1 = strassen(plus(A11,A22),plus(B11,B22),size_)
M2 = strassen(plus(A21,A22),B11,size_)
M3 = strassen(A11,minus(B12,B22),size_)
M4 = strassen(A22,minus(B21,B11),size_)
M5 = strassen(plus(A11,A12),B22,size_)
M6 = strassen(minus(A21,A11),plus(B11,B12),size_)
M7 = strassen(minus(A12,A22),plus(B21,B22),size_)
C11 = plus(minus(plus(M1,M4),M5),M7)
C12 = plus(M3,M5)
C21 = plus(M2,M4)
C22 = plus(plus(minus(M1,M2),M3),M6)
for i in range(size_) :
for j in range(size_) :
C[i][j] = C11[i][j]
C[i][j+size_] = C12[i][j]
C[i+size_][j] = C21[i][j]
C[i+size_][j+size_] = C22[i][j]
return C
C = strassen(A,B,size)
for i in range(n) :
for j in range(k) :
print(C[i][j],end=' ')
print()
7. 10830번 행렬 제곱
문제 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.
행렬의 곱셈과 제곱이 합쳐져서 뭔가 느낌적으로 '제곱도 분할 정복으로 풀고, 행렬 곱셈도 분할 정복(슈트 라센 알고리즘)으로 풀어야 하나?' 생각이 든다. 다행히도(?) 행렬 곱셈은 O(n^3)으로 풀어도 해결되는 문제이다. 먼저 두 행렬을 곱하는 함수 multi를 선언한다. 다음 제곱하는 과정을 분할 정복을 통해서 해결한다.
#10830번 행렬 제곱
n,b = map(int,input().split()) # n*n행렬을 b제곱 해준다
A = [[0]*n for i in range(n)]
for i in range(n) :
A[i] = list(map(int,input().split()))
C = [[0]*n for i in range(n)]
def multi(mat1,mat2,size) : # mat1 행렬과 mat2 행렬의 곱
mat3 = [[0]*size for i in range(size)]
for i in range(size) :
for j in range(size) :
for l in range(size) :
mat3[i][j] += mat1[i][l]*mat2[l][j]%1000
return mat3
def square(mat, n) : #제곱을 빠르게
size = len(mat)
if n == 1 :
return mat
elif n%2 == 0 :
square_mat = square(mat,n//2)
return multi(square_mat,square_mat,size)
else :
square_mat = square(mat,n//2)
return multi(mat,multi(square_mat,square_mat,size),size)
C = square(A,b)
for i in range(n) :
for j in range(n) :
print(C[i][j]%1000,end=' ')
print()
8. 11444번 피보나치 수 6
문제 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그다음 2번째부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다. n=17일 때까지 피보나치 수를 써보면 다음과 같다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오
피보나치 수를 구하는 다양한 방법이 있다. 하나하나 계산을 통해 구하는 방법이 있는가 하면 행렬의 제곱을 통해서도 구할 수 있다. 이 정도 설명을 들으면 피보나치 수를 어떻게 분할 정복으로 해결할지 감이 올 것이다.
행렬 $\begin{vmatrix} 1 & 1 \\ 1 & 0 \end{vmatrix}$를 n 제곱했을 때 0행 1열에 있는 수가 피보나치 n번째 수이다. 이 행렬을 피보나치 행렬이라고 하자. 7번 문제와 마찬가지로 행렬을 곱하는 함수 multi를 구현한다. 다음 피보나치 행렬을 n번 제곱한 행렬을 구한 뒤 0행 1열의 숫자를 출력한다. 이때 행렬을 제곱하는 과정을 분할 정복을 통해 해결한다.
#11444번 피보나치 수 6
n = int(input())
mod = 1000000007
def multi(mat1,mat2,size) :
mat3 = [[0]*size for i in range(size)]
for i in range(size) :
for j in range(size) :
for l in range(size) :
mat3[i][j] += mat1[i][l]*mat2[l][j]%mod
return mat3
def square(mat, n) :
size = len(mat)
if n == 1 :
return mat
elif n%2 == 0 :
square_mat = square(mat,n//2)
return multi(square_mat,square_mat,size)
else :
square_mat = square(mat,n//2)
return multi(mat,multi(square_mat,square_mat,size),size)
A = [[1,1],[1,0]] # 피보나치 수를 행렬을 통해 구하는 방법
if n == 0 :
print(0)
else :
C = square(A,n)
print(C[0][1]%mod)
9. 6549번 히스토그램에서 가장 큰 직사각형
문제 히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다. 히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오.
상당히 어려운 수준의 문제이며, 코딩 테스트를 준비하는 내 입장에서는 굳이 이런 문제까지 풀 필요가 있나 싶지만 일단 풀어는 보았다. 처음에 감이 안 잡힐 수 있지만 분할 정복 문제를 푸는 방법과 동일한 시각으로 바라보면 방향성을 찾을 수 있다. 가장 먼저 큰 문제를 어떻게 나눌까 이다. 별다른 규칙성이 보이지 않으니 히스토그램을 반으로 나누기로 한다. 히스토그램을 반으로 나눠 왼쪽 히스토그램과 오른쪽 히스토그램 각각에서 가장 큰 직사각형을 구한 후 더 큰 직사각형의 크기를 저장한다. 이렇게 언제까지 나눌 것이냐 하면 히스토그램이 하나가 남을 때까지 나눈다. 히스토그램이 하나일 때는 해당 히스토그램의 높이만 반환해주면 된다. 단 이때 나누기 전의 히스토그램에서 가장 큰 직사각형이 나올 수 있다. 때문에 나누기 전의 히스토그램, 즉 현재 히스토그램에서 가장 큰 직사각형을 먼저 구할 필요가 있다.
현재 히스토그램에서 가장 큰 직사각형, 왼쪽 절반 히스토그램에서 가장 큰 직사각형, 오른쪽 절반 히스토그램에서 가장 큰 직사각형 중 가장 큰 직사각형을 result에 저장하며, 왼쪽과 오른쪽 히스토그램으로 나누는 과정을 분할 정복을 통해 해결한다.
#6549번 히스토그램에서 가장 큰 직사각형
test_case = []
def current_rectangle(n,h) : #현재 히스토그램에서 가장 큰 직사각형 찾기
if n%2 != 0 : # 가장 정중앙에 있는 히스토그램부터 시작하여 좌우로 넓혀가면서 직사각형의 크기를 측정
left = n//2
right = n//2
height = h[left]
else :
left = n//2 -1
right = n//2
height = min(h[left],h[right])
width = right-left+1
area = height*width
while left != 0 or right != n-1 :
if h[left-1] > h[right+1] : # 좌측에 있는 히스토그램이 더 크다면 좌측 히스토그램부터 고려
left -= 1
height = min(height,h[left]) # 현재 높이와 새로 추가된 히스토그램의 높이 중 더 작은 값
width = right-left+1 # 너비는 1추가
area = max(area, height*width) # 넓이는 너비 x 높이
else : # 우측에 있는 히스토그램이 더 크면 우측 히스토그램부터 고려
right += 1
height = min(height,h[right])
width = right-left+1
area = max(area, height*width)
if left == 0 or right == n-1 : # 만약 어느 하나라도 끝에 도달했다면 반복문 종료
break
while left != 0 : # 좌 또는 우의 끝에 도달하지 못했다면 도달할때까지 반복 수행
left -= 1
height = min(height,h[left])
width = right-left+1
area = max(area, height*width)
while right != n-1 :
right += 1
height = min(height,h[right])
width = right-left+1
area = max(area, height*width)
return area
def largest_rectangle(n,h) : #히스토그램을 절반으로 나누기
if n == 1 :
return h[0]
mid = n//2
devide_1 = h[:mid]
devide_2 = h[mid:]
if n % 2 == 0 :
result = max(current_rectangle(n,h),largest_rectangle(n//2,devide_1),largest_rectangle(n//2,devide_2))
#현재 히스토그램에서의 가장 큰 직사각형, 현재 히스토그램을 두개로 나눈 두 히스토그램에서의 가장 큰 직사각형, 총 세개 중 가장 큰값
else :
result = max(current_rectangle(n,h),largest_rectangle(n//2,devide_1),largest_rectangle((n//2)+1,devide_2))
return result
while True :
test_case = list(map(int,input().split()))
if test_case == [0] :
break
n = test_case[0]
h = test_case[1:]
print(largest_rectangle(n,h))
10. 2261번 가장 가까운 두 점
문제 2차원 평면상에 n개의 점이 주어졌을 때, 이 점들 중 가장 가까운 두 점을 구하는 프로그램을 작성하시오.
매우 어려운 문제로 9번과 마찬가지로 코딩 테스트를 준비하는데 이 정도의 문제까지 풀 수 있어야 하나 싶다. 사실상 풀이를 모르면 풀 수 없는 문제이니 검색을 통해 풀이를 정확히 이해하고 풀어보기를 추천한다. 나 또한 그렇게 풀었다. 아래 올려놓은 코드는 참고만 했으면 한다.
#2261번 가장 가까운 두점
def distance(point1, point2) : #두 점 사이의 거리
return (point1[0]-point2[0])**2 + (point1[1]-point2[1])**2
def d_min(points) :
n = len(points)
if n == 2 : #점이 2개 일 때
return distance(points[0],points[1])
if n == 3 : # 점이 3개 일 때
return min(distance(points[0],points[1]),distance(points[0],points[2]),distance(points[1],points[2]))
d = min(d_min(points[:n//2]),d_min(points[n//2:])) # 가운데 x좌표를 기준으로 양쪽으로 나눔
check = [] # 최소 거리가 될 수 있는 후보 점들
for p in points :
if (points[n//2][0]-p[0])**2 < d : # d보다 짧은 거리에 있는 점들만 후보로
check.append(p)
check = sorted(check, key = lambda x : x[1]) # y좌표로 정렬
for i in range(len(check)-1) :
for j in range(i+1,len(check)) :
if (check[i][1]-check[j][1])**2 < d : # y좌표 기준으로 d보다 짧은 거리에 있는 점들만
d = min(d,distance(check[i],check[j])) # 확인
else :
break
return d
#main
num = int(input())
point = []
for i in range(num) :
x,y = map(int,input().split())
point.append([x,y])
point = sorted(point, key = lambda x : x[0])
d = d_min(point)
print(d)
