Merge sort
리스트 길이가 1이하이면 이미 정렬된 것으로 본다.
1. 분할 : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두부분 리스트로 나눈다.
2. 정복 : 각 부분 리스트를 재귀적으로 합병정렬을 이용해 정렬한다.
3. 결합 : 각 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 이때 정렬 결과가 임시 배열에 저장된다.
4. 복사 : 임시 배열에 저장된 결과를 원래 배열에 복사한다.
def merge(arr, left, mid, right):
# TODO: 왼쪽과 오른쪽 부분 배열을 임시 배열로 복사
left_arr=arr[left:mid+1]
right_arr=arr[mid+1:right+1]
# TODO: 두 배열을 병합
# TODO: left_arr와 right_arr를 비교하며 작은 값을 arr에 복사
l=0
r=0
i=left
while l<len(left_arr) and r<len(right_arr):
if left_arr[l]<=right_arr[r]:
arr[i]=left_arr[l]
l+=1
else:
arr[i]=right_arr[r]
r+=1
i+=1
# TODO: 남은 원소들을 복사
# left_arr에 남은 원소가 있으면 복사
# right_arr에 남은 원소가 있으면 복사
while l<len(left_arr):
arr[i]=left_arr[l]
i+=1
l+=1
while r<len(right_arr):
arr[i]=right_arr[r]
i+=1
r+=1
def merge_sort(arr, left, right):
"""
머지 정렬 재귀 함수
Args:
arr: 배열
left: 시작 인덱스
right: 끝 인덱스
"""
# TODO: base case - left가 right보다 작을 때만 정렬
## 중간 지점 계산
## 왼쪽 절반 재귀 정렬
## 오른쪽 절반 재귀 정렬
## 정렬된 두 절반을 병합
if left<right:
mid=left+(right-left)//2
merge_sort(arr, left, mid)
merge_sort(arr, mid+1, right)
merge(arr,left,mid,right)
Quick sort
- 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다.
- 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
- 분할된 두 개의 작은 리스트에 대해 재귀적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.
재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.
def partition(arr, low, high):
# TODO: 피벗을 선택 (일반적으로 마지막 원소)
pivot=arr[high]
# TODO: i는 작은 원소들의 마지막 인덱스를 추적
i=low-1
# TODO: low부터 high-1까지 순회하면서
## 현재 원소가 피벗보다 작거나 같으면:
## 1. i를 1 증가
## 2. arr[i]와 arr[j]를 교환
for j in range(low,high):
if arr[j]<=pivot:
i+=1
arr[i],arr[j]=arr[j],arr[i]
# TODO: 피벗을 올바른 위치(i+1)에 배치
arr[i+1],arr[high]=arr[high],arr[i+1]
return i + 1
def quick_sort(arr, low, high):
# TODO: base case - low가 high보다 작을 때만 정렬
## 분할하여 피벗 인덱스 얻기
## 피벗 왼쪽 부분 재귀 정렬
## 피벗 오른쪽 부분 재귀 정렬
if low<high:
pivot_index=partition(arr, low, high)
quick_sort(arr, low, pivot_index-1)
quick_sort(arr, pivot_index+1,high )
분할 정복
https://www.acmicpc.net/problem/1780
import sys
read=sys.stdin.readline
board=[]
n=int(read().strip())
for _ in range(n):
board.append(list(map(int,read().strip().split())))
result=[0]*3
ck_values=[-1,0,1]
# 종이가 다 1,0,-1 인지 체크
def check(x,y,gap,comp):
for i in range(x,x+gap):
for j in range(y,y+gap):
if board[i][j]!=comp:
return False
return True
# 9등분하고 만약 다 같은 종이면 종료된다
def sol(x,y,gap):
# 1x1 종이를 더이상 나눌 수 없을때 모두 같은 숫자 임으로 종료조건 추가할 필요 없다
for i in range(len(ck_values)):
if check(x,y,gap,ck_values[i]):
result[i]+=1
return
tri=gap//3
for i in range(3):
for j in range(3):
sol(x+tri*i,y+tri*j,tri)
sol(0,0,n)
for r in result:
print(r)