[이론]파이썬 알고리즘 - 정렬 / 이진탐색

1. 정렬

• 데이터를 특정 기준에 따라 순서대로 나열하는 것
• 문제 상황에 따라서 적절한 정렬 알고리즘을 공식처럼 사용

1-1. 선택정렬

• 처리되지 않은 데이터 중 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 위치를 바꾼다.

구현 예)

array=[7,5,9,0,3,1,6,2,4,8]

for i in range(len(array)):
  min_index=i # 가장 작은 원소의 인덱스
  # i이후의 값들 중 가장 작은 값을 찾는 반복문
  for j in range(i+1,len(array)):
    if array[min_index]>array[j]:
      min_index=j
  # 작은 값을 찾았으면 i번째 값과 스와프
  array[i],array[min_index]=array[min_index],array[i]
print(array)

• 선택정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 하므로 시간복잡도는 O(N^2)이다.

1-2. 삽입정렬

• 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다.

구현 예)

array=[7,5,9,0,3,1,6,2,4,8]

for i in range(1,len(array)):
  for j in range(i,0,-1):
    if array[j]<array[j-1]:
      array[j],array[j-1]=array[j-1],array[j]
    else:
      break
print(array)

• 삽입정렬은 선택정렬과 마찬가지로 반복문이 두 번 중첩되므로 시간복잡도는 O(N^2)이다.

1-3. 퀵정렬

• 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법
• 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나
• 기본적으로 첫 번째 데이터를 기준 데이터(Pivot)으로 설정
• 왼쪽에서는 피벗보다 큰 데이터를 선택하고, 오른쪽 끝에서는 피벗보다 작은 데이터를 선택해 둘의 위치를 바꾸는 것을 반복한다. 이 때 위치가 엇갈리는 경우, 피벗과 작은 데이터의 위치를 서로 바꾼다. 결과적으로 피벗을 기준으로 왼쪽은 피벗보다 작고 오른쪽은 피벗보다 큰 값이 모여있으므로, 왼쪽과 오른쪽에 대해 각각 퀵정렬을 수행하는 것을 반복하면 전체적으로 정렬이 완성된다.
• 퀵정렬의 시간복잡도는 O(NlogN)이나, 최악의 경우(배열이 이미 정렬된 경우) O(N^2)이다.

구현 예)

array=[5,7,9,0,3,1,6,2,4,8]

def quick_sort(array, start, end):
  if start>=end: # 원소가 1개인 경우 종료
    return
  pivot=start # 피벗은 첫 번째 원소
  left=start+1
  right=end
  while(left<=right):
    # 피벗보다 큰 데이터를 찾을 때까지 반복
    while(left<=end and array[left]<=array[pivot]):
      left+=1
    # 피벗보다 작은 데이터를 찾을 때까지 반복  
    while(right>start and array[right]>=array[pivot]):
      right-=1
    if(left>right): # 엇갈렸다면 작은 데이터와 피벗을 교체
      array[right],array[pivot]=array[pivot],array[right]
    else: # 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
      array[left],array[right]=array[right],array[left]
  # 분할 이후 왼쪽과 오른쪽에서 각각 정렬 수행
  quick_sort(array, start, right-1)
  quick_sort(array, right+1,end)
quick_sort(array,0,len(array)-1)

print(array)

구현 예2) 파이썬의 장점을 살린 방식

array=[5,7,9,0,3,1,6,2,4,8]

def quick_sort(array):
  # 리스트가 하나 이하의 원소만을 담고 있다면 종료
  if len(array)<=1:
    return array
  pivot=array[0] # 피벗은 첫 번째 원소
  tail=array[1:] # 피벗을 제외한 리스트

  left_side=[x for x in tail if x<=pivot] # 분할된 왼쪽 부분
  right_side=[x for x in tail if x>pivot] # 분할된 오른쪽 부분
  # 분할 이후 왼쪽과 오른쪽 부분에서 각각 정렬이 재귀함수로 수행되고 전체 리스트 반환
  return quick_sort(left_side)+[pivot]+quick_sort(right_side)

print(quick_sort(array))

문제) 두 배열의 원소 교체
두 배열 A,B는 N개의 자연수로 구성되어 있으며 K번의 바꿔치기 연산을 수행해서 배열 A의 모든 원소의 합이 최대가 되도록 하는 방법과 최댓값
로직) 매번 배열 A에서 가장 작은 원소, B에서 가장 큰 원소를 서로 교환한다. 이를 위해 A는 오름차순, B는 내림차순 정렬한다. 두 배열의 첫 번째 원소부터 확인하면서 A의 원소가 B의 원소보다 작을 때만 교환한다.
풀이)

n,k=map(int,input().split())
arrayA=list(map(int,input().split()))
arrayB=list(map(int, input().split()))

arrayA.sort()
arrayB.sort(reverse=True)

for i in range(k):
  if arrayA[i]<arrayB[i]:
    arrayA[i],arrayB[i]=arrayB[i],arrayA[i]
  else: # A의 원소가 B의 원소보다 크거나 같을 때 반복문 탈출(이미 정렬되어 있기 때문에 다음 원소로 이동할 필요 없음)
    break
print(sum(arrayA))

2. 이진탐색

• 순차탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 하나씩 확인
• 이진탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색
  -> 시작점, 끝점, 중간점을 이용하여 탐색 범위 설정
• 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 $log_2N$에 비례하고, 탐색 범위를 절반씩 줄이므로 시간복잡도는 O(logN)이다.

구현 예) 재귀함수

def binary_search(array, target, start, end):
  if start>end:
    return None
  mid=(start+end)//2
  # 찾은 경우 중간점 인덱스 반환
  if array[mid]==target:
    return mid
  # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽만 확인
  elif array[mid]>target:
    return binary_search(array,target,start,mid-1)
  # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽만 확인
  else:
    return binary_search(array, target, mid+1,end)

n,target=map(int,input().split())
array=list(map(int,input().split()))

result=binary_search(array,target,0,n-1)
if result==None:
  print('원소가 존재하지 않습니다.')
else:
  print(result+1)

구현 예2) 반복문

def binary_search(array, target, start, end):
  if start>end:
    return None
  while start<=end:
    mid=(start+end)//2
    if array[mid]==target:
      return mid
    elif array[mid]>target:
      end=mid-1
    else:
      start=mid+1
    
n,target=map(int,input().split())
array=list(map(int,input().split()))

result=binary_search(array,target,0,n-1)
if result==None:
  print('원소가 존재하지 않습니다.')
else:
  print(result+1)

※ 파이썬의 이진탐색 라이브러리

• bisect_left(list, x): 정렬된 순서를 유지하면서 list에 x를 삽입할 가장 왼쪽 위치를 반환

• bisect_right(list, x): 정렬된 순서를 유지하면서 list에 x를 삽입할 가장 오른쪽 위치를 반환

from bisect import bisect_left, bisect_right

a=[1,2,4,4,8]
x=4

print(bisect_left(a,x))
print(bisect_right(a,x))

구현 예) 값이 특정 범위에 속하는 데이터 개수 구하기

from bisect import bisect_left, bisect_right

def count_by_range(a, left_value, right_value):
  right_index=bisect_right(a,right_value)
  left_index=bisect_left(a,left_value)
  return right_index-left_index

a=[1,2,3,3,3,3,4,4,8,9]
# 값이 4인 데이터 개수
print(count_by_range(a,4,4))
# 값이 [-1,3] 범위에 있는 데이터 개수
print(count_by_range(a,-1,3))

문제1) 떡볶이 떡 만들기
파라메트릭 서치: 최적화 문제를 결정문제(예/아니오)로 바꾸어 해결하는 기법. 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제 등. 이진탐색을 통해 해결
로직) 적절한 높이를 찾을 때까지 이진탐색을 수행해서 높이를 반복 조정. 현재 이 높이로 자르면 조건을 만족할 수 있는가?'를 확인한 뒤, 조건의 만족 여부에 따라 탐색 범위를 좁힌다. 탐색범위가 10억 등과 같이 클 경우, 가장 먼저 이진탐색을 떠올려야 한다.
풀이)

n,m=map(int,input().split())
lst=list(map(int, input().split()))
# 시작점과 끝점 설정
lt=0
rt=max(lst)
length=0
# 반복문을 통한 이진탐색 수행
while lt<=rt:
  mid=(lt+rt)//2
  sum=0
  for i in lst:
    # 잘린 떡의 양 계산
    if i-mid>0:
      sum+=(i-mid)
  # 떡의 양이 충분한 경우 덜 자르기(오른쪽 부분 탐색)
  if sum>=m:
    length=mid
    lt=mid+1
  # 떡의 양이 부족한 경우 더 많이 자르기(왼쪽 부분 탐색)
  else:
    rt=mid-1
print(length)

문제2) 정렬된 배열에서 특정 수의 개수 구하기
N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있을 때 이 수열에서 x가 등장하는 횟수를 계산. 단, 시간복잡도 O($logN$)으로 설계해야 한다.
로직) 특정 값이 등장하는 첫 번째 위치와 마지막 위치를 찾아, 인덱스 차이를 계산한다.
풀이) 이진탐색 라이브러리를 활용