<aside> ✅ 금주의 키워드
이분탐색
분할정복
스택
큐
우선순위 큐 </aside>
2630번 색종이 만들기
이 문제는 쿼드트리의 대표적인 문제였다.
처음 이 문제를 풀때 N-Queen 과 같이 접근하였다.
from functools import reduce
import sys
N = int(input())
soted_paper = [[0]*8 for _ in range(N)]
given_paper = [list(map(int,sys.stdin.readline().split())) for _ in range(N)]
global total_blue
total_blue = 0
global total_white
total_white = 0
def papercount(arr,jstart,jend,istart,iend):
global total_blue
global total_white
blue = [0,0,0,0]
white = [0,0,0,0]
n = jend - jstart + 1
if n == 2:
if arr[jstart][istart] == arr[jstart][iend] and arr[jstart][iend] == arr[jend][istart] and arr[jend][istart] == arr[jend][iend]:
if arr[jstart][istart] == 0:
return [1,1,1,1] , [0,0,0,0]
elif arr[jstart][istart] == 1:
return [0,0,0,0] , [1,1,1,1]
else:
for j in range(jstart,jend+1):
for i in range(istart,iend+1):
if arr[j][i] == 0:
total_white += 1
else:
total_blue += 1
return [1,0,1,0],[0,1,0,1]
mj = (jstart +jend) // 2
mi = (istart +iend) // 2
chk = 0
for j in range(jstart,mj+1):
chk += reduce(lambda x , y: x+y,arr[j][istart:mi+1])
if chk == (n**2)//4:
blue[0] = blue[0] + 1
elif chk == 0:
white[0] = white[0] + 1
chk = 0
for j in range(jstart,mj+1):
chk += reduce(lambda x , y: x+y,arr[j][mi+1:iend+1])
if chk == (n**2)//4:
blue[1] = blue[1] + 1
elif chk == 0:
white[1] = white[1] + 1
chk = 0
for j in range(mj+1,jend+1):
chk += reduce(lambda x , y: x+y,arr[j][istart:mi+1])
if chk == (n**2)//4:
blue[2] = blue[2] + 1
elif chk == 0:
white[2] = white[2] + 1
chk = 0
for x in range(mj+1,jend+1):
chk += reduce(lambda x , y: x+y,arr[x][mi+1:iend+1])
if chk == (n**2)//4:
blue[3] = blue[3] + 1
elif chk == 0:
white[3] = white[3] + 1
if white == [1,1,1,1]:
return [1,1,1,1] , [0,0,0,0]
elif blue == [1,1,1,1]:
return [0,0,0,0] , [1,1,1,1]
total_blue += sum(blue)
total_white += sum(white)
return white, blue
print(jstart,jend,istart,iend,end=" ---> ")
print(white,blue,total_white,total_blue,end=" (흰, 파, 전체흰, 전체파)\\n",sep=', ')
# papercount(arr,n//2)
def mergeSort(arr,jstart,jend,istart,iend):
global total_white
global total_blue
if jstart < jend or istart < iend:
mj = (jstart +jend) // 2
mi = (istart +iend) // 2
result = papercount(arr,jstart,jend,istart,iend)
if result[0] == [1,1,1,1]:
total_white += 1
return
elif result[1] == [1,1,1,1]:
total_blue += 1
return
else:
for i in range(4):
if result[0][i] == 1 or result[1][i] == 1:
continue
elif i == 0:
mergeSort(arr,jstart,mj,istart,mi)
elif i == 1:
mergeSort(arr,jstart,mj,mi+1,iend)
elif i == 2:
mergeSort(arr,mj+1,jend,istart,mi)
else:
mergeSort(arr,mj+1,jend,mi+1,iend)
mergeSort(given_paper,0,N-1,0,N-1)
print(total_white)
print(total_blue)
지수적으로 나뉘고 색종이를 판별하는데 해당영역의 합을 구하고 해당영역의 합이 파란종이인지 확인 한후 맞지않으면 다시 분할하였다. 식을 적다보니 길이도 너무 길고 팀원들에게 설명하기 힘들었다. 나중에 보니 내가 어떻게 작성했는지도 기억이 나질 않았다.
그래서 구글링을 통해 다른 사람들의 답안을 참고하였다.
import sys
global blue
blue = 0
global white
white = 0
def quadTree(y,x,n):
global blue
global white
start = n_list[y][x]
chk = False
for j in range(y,y+n):
if chk: ##이미 한개라도 다르면 break
break
for i in range(x,x+n):
if start != n_list[j][i]: #색종이의 색이 다르면
quadTree(y,x,n//2) #시작점을 사분할 하여 각각 탐색시작
quadTree(y,x+n//2,n//2)
quadTree(y+n//2,x,n//2)
quadTree(y+n//2,x+n//2,n//2)
chk = True
break
if not chk: #모든곳의 색종이 색이 같다면
if start == 1: #색종이 색에 따라 색종이 수를 갱신
blue += 1
else:
white += 1
return
if __name__ == "__main__":
N = int(input())
n_list = [ list(map(int,sys.stdin.readline().split())) for _ in range(N)]
quadTree(0,0,N)
print(white)
print(blue)
내가 어떻게 문제상황을 분할하느냐에 따라 코드의 복잡도가 바뀔수 있다는것을 깨달았다.
위 내용은 아래 블로그를 참고하여 작성하였습니다.
6549번 히스토그램에서 가장 큰 직사각형
처음 문제를 읽었을때 문제 이해하기도 너무 버거웠다. 문제 접근조차도 못하고 팀원의 설명을 듣고 구글링하여 구현해 보았다. 우선 아래 방법은 스택을 이용한 풀이이다.
import sys
from collections import deque
while True:
case = list(map(int,sys.stdin.readline().split())) #타워 정보 입력받음
if len(case) == 1: #0이 입력되면 종료
exit(0)
n = case.pop(0)
max_area = 0
stack = []
for i,h in enumerate(case): #히스토그램의 높이와 인덱스를 반복
start = i
while stack and stack[-1][1] > h: # stack[-1] 높이보다 h가 작으면
index , height = stack.pop()
max_area = max(max_area,height*(i-index)) #이전까지의 히스토그램 넓이를 계산하여 갱신함
start = index
stack.append((start,h)) #스택이 비어있거나 스택의 마지막 높이보다 작으면 스택에 추가
for i , h in stack:
max_area = max(max_area,(n-i)*h) #시작부터 축적되어온 히스토그램들의 넓이를 계산하여 갱신
# ex) 높이 1 인것은 끝까지 남아있음
print(max_area)
위 코드는 아래 유튜브내용을 참고하여 작성했습니다.
LARGEST RECTANGLE IN HISTOGRAM - Leetcode 84 - Python
이 코드는 매우 간단하지만 이해하기가 쉽지 않았다. 위 영상을 반복적으로 시청하며 이해하려 노력했다.
아래 코드는 팀원의 설명을 듣고 구현해본 코드이다. 분할 정복을 하는데 현재 분할지점에서의 넓이 계산이 추가된다는것이 인상적이었다.
import sys
def getCenterArea(arr,mid):
first = mid -1
second = mid
width = 2
min_height = min(arr[first], arr[second]) #분할지점의 양쪽 높이중 작은값을 선택
max_area = width * min_height #넓이 계산
while not (first == 0 and second == len(arr)-1): #양쪽 끝에 도달할때까지 반복
current_height = 0
if first == 0:
second += 1
current_height = arr[second]
elif second == len(arr)-1:
first -= 1
current_height = arr[first]
elif arr[first-1] > arr[second+1]: #우선 높은쪽으로 이동하며 높이를 갱신
first -= 1
current_height = arr[first]
else:
second += 1
current_height = arr[second]
min_height = min(current_height,min_height) #히스토그램의 넓이는 최소높이에 따라 다르므로 최소값을 선택
width += 1 #한칸 이동했으므로 가로길이 1증가
max_area = max(max_area,width * min_height) #넓이의 최대값을 갱신
return max_area #끝까지 모두 탐색 후 반환
def getArea(arr):
if len(arr) == 1:
return arr[0]
mid = len(arr) // 2
a = max(getArea(arr[:mid]),getArea(arr[mid:]),getCenterArea(arr,mid))
# mid 왼쪽 , mid 오른쪽, mid로부터 탐색한 넓이 중 최대값을 반환
return a
if __name__ == "__main__":
while True:
histogram = list(map(int,sys.stdin.readline().split()))
n = histogram.pop(0)
if n == 0:
exit(0)
print(getArea(histogram))
다른 분할 정복과 달리 분할시 따져봐야 할것이 매우 많았다. 그래서 복잡하고 어려운 문제가 아닐가 싶었다. 이와 같이 분할한다고 다 되는건 아니고 분할 후 어떤방식으로 탐색하여 갱신해야 하는지 고민하게 만드는 문제였다. 위 풀이는 아래 블로그 내용과 비슷하니 참고하면 좋을것 같다.
2493번 탑
처음 문제를 봤을 때 만만하게 본것 같았다. 하지만 스택을 사용하지 않으니 시간 복잡도가 커서 시간 초과가 발생했다. 최악의 경우 반복횟수가 굉장이 클수 있어서 시간초과가 발생했다.
tower_num = int(input())
towers = list(map(int,input().split()))
towers_copy = list(map(lambda x : x ,towers))
ans= [0]*tower_num
cnt = tower_num - 1
while towers_copy:
current_tower = towers_copy.pop()
for i in towers_copy[::-1]:
if current_tower < i:
ans[cnt] = towers.index(i)+1
break
cnt -= 1
print(*ans)
팀원의 설명을 듣고 다시 작성해 보았다. 스택을 이용한 방법인데 스택에 타워의 높이와 위치를 같이 추가하여 후에 위치를 활용할수 있게끔 설계하였다.
from collections import deque
import sys
def searchTower(arr,n):
result = [0] * n
stack = []
for i in range(n-1,-1,-1): #맨 뒤의 타워부터 검색 반복
stack.append([i,arr.pop()]) #스택에 위치와 높이를 추가
while stack and arr and arr[-1] >= stack[-1][1]: #스택 최상단 높이가 남은 타워의 맨 끝 높이보다 작을때
idx , _ = stack.pop()
result[idx] = i #결과 인덱스에 전파를 받는 타워의 인덱스를 기록
return result
if __name__ == "__main__":
tower_num = int(input())
towers = list(map(int,sys.stdin.readline().split()))
print(*searchTower(towers,tower_num))
처음에 스택에는 숫자만 넣을것이라고 생각했는데 필요한 데이터를 넣는 방법이 있다는 것을 알게되었다.
1655번 가운데를 말해요
수가 주어질때 마다 수열의 가운데 값을 출력하는 문제이다. 사실 입력 받은후 정렬한 뒤 중앙값을 출력해도 되지만 데이터 양이 많아지면 시간복잡도가 급증하여 좋지 못한 방법이다.
그래서 보통은 우선순위 큐를 사용한다. 긴 수열에서 최대, 최소값을 구하고 수열에 추가 및 요소 제거에 강점이 있기 때문이다.
import heapq
import sys
from collections import deque
from heapq import heappop, heappush, _heapify_max, heappushpop
N = int(input())
min_heap = [] ## 상위그룹의 최소값
max_heap = [] ## 하위그룹의 최대값
for i in range(N):
x = int(sys.stdin.readline())
if i % 2 == 0:
heapq.heappush(max_heap,-x)
else:
heapq.heappush(min_heap,x)
if min_heap and max_heap and min_heap[0] < -max_heap[0]: #상위그룹의 최소값이 하위그룹의 최대값보다 작은경우 교체
y =heappushpop(min_heap,-heappop(max_heap))
heappush(max_heap,-y)
print(-max_heap[0])
처음 해설을 볼때 잘 이해가 되지 않았는데 아래 블로그를 정독하며 이해하려고 노력하였다. 가운데 값을 구하는 발상이 인상적이어서 기록하게 되었다.
위 내용은 아래 페이지를 참고하였습니다.
13334번 철로
처음 이 문제를 보았을 때는 이걸 어떻게 다세어야 할까였다. 이 어지러운 데이터를 하나하나 다본다면 당연하게 시간초과가 발생할것 같았다. 발상이 도저히 생각나지 않아 구글링하였다.
import sys
import heapq
n = int(sys.stdin.readline())
roads = []
ans = 0
roads_info = []
for i in range(n):
house , office = list(map(int,sys.stdin.readline().split()))
a = (house,office)
roads.append(a)
d = int(sys.stdin.readline())
for road in roads:
house , office = road
if abs(house-office) <= d:
road = sorted(road)
roads_info.append(road)
roads_info.sort(key=lambda x : x[1])
heap = []
for road in roads_info:
if not heap:
heap.append(road)
else:
while heap and road[1] - heap[0][0] > d:
heapq.heappop(heap)
if not heap:
break
heapq.heappush(heap,road)
ans = max(ans, len(heap))
print(ans)
노선중 노선의 길이가 기준값보다 큰것들은 미리 제거 한다. 그리고 기준의 오른쪽 좌표를 기준으로 노선들을 정렬한다. 그 후 노선들 중 가장 왼쪽에 있는 좌표와 가장 오른쪽에 있는 좌표간 거리가 기준 길이가 될때까지 제거하여 힙 안에 기준값 이하인 노선만 남게한다. 이 과정을 반복하며 최대값을 갱신하여 답을 얻는다. 말로 설명하는것보다 아래 블로그를 참고하는 것이 이해하는데 좋은 방법인것 같다.
위 내용은 아래 블로그의 내용을 참고하였습니다.
2261번 가장 가까운 두점
처음 이 문제를 보고는 바로 구글링 했었다. 이걸 어떻게 할지 막막했다. 사실 알고보니 철로나 히스토그램에서 직사각형 넓이 구하기와 비슷한 사고방식인것 같았다. 다만 이 문제를 그 과정을 두번이나 시행하여 이해하기 너무 어려웠었다.
import sys
def calDistance(point0, point1):
return (point0[0]-point1[0]) ** 2 + (point0[1]-point1[1]) ** 2
def searchPoint(arr):
if len(arr) == 2:
return calDistance(arr[0],arr[1])
if len(arr) == 3:
return min(calDistance(arr[0],arr[1]),calDistance(arr[1],arr[2]),calDistance(arr[0],arr[2]))
mid = len(arr) // 2
d = min(searchPoint(arr[:mid]),searchPoint(arr[mid:]))
check = []
for i in arr:
if (i[0]-arr[mid][0]) ** 2 < d:
check.append(i)
check.sort(key=lambda x: x[1])
for i in range(len(check)-1):
for j in range(i+1,len(check)):
if (check[i][1] - check[j][1]) ** 2 < d:
d = min(d,calDistance(check[i],check[j]))
else:
break
return d
if __name__ == "__main__":
n = int(input())
point = []
for i in range(n):
x , y = list(map(int,sys.stdin.readline().split()))
point.append((x,y))
point.sort(key=lambda x : x[0])
d = searchPoint(point)
print(d)
우선 x 좌표 기준으로 정렬 한 후 중앙점을 기준으로 분할 하며 최소 거리를 구한다. 이후 x 좌표와 중앙점의 x좌표 거리가 d보다 작은 점들을 골라 준 후 y좌표를 기준으로 정렬한다. 이후 순차 탐색을 통해 거리의 최소값을 갱신해 나간다.
이 문제의 해설을 보며 이정도로 나누고 계산을 해줘야 하는건지 의문이 들었지만.. 인상적인 문제였다.
위 내용은 아래 블로그를 참고하여 작성하였습니다.
느낀점 및 더 보아야 할것