24.01.17 분할정복, 병합정렬, 코어타임

24.01.17 분할정복, 병합정렬, 코어타임

코테가 바로 내일이여서 백준 문제를 많이 풀려고 노력했다.

쉽지않다. 흑흑..

Algorithm

분할정복(Divide and Conquer)

• 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방식
• 대표적인 예
  • 퀵정렬
  • 합병정렬
  • 이진탐색
  • 선택문제
  • 고속 푸리에 변환

분할정복의 설계

1. Divide - 원래 문제가 분할하여 비슷한 유형의 더 작은 하위 문제로 분할 가능할때까지 나눈다.
2. Conquer - 각 하위 문제를 재귀적으로 해결한다. 하위 문제의 규모가 나눌 수 없는 단위가 되면 탈출 조건을 설정하고 해결한다.
3. Combine - Conquer한 문제들을 통합하여 원래 문제의 답을 얻어 해결한다.

• Divide를 제대로 나누면 Conquer 과정은 자동으로 쉬워진다. 그래서 Divide를 잘 설계하는 것이 중요하다.
• 분할정복 알고리즘은 재귀 알고리즘이 많이 사용되는데, 이 부분에서 분할정복 알고리즘의 효율성을 깎아 내릴 수 있다.

분할정복 특징 및 장단점

• 분할 된 작은 문제는 원래 문제와 성격이 동일하다 → 입력 크기만 작아짐
• 분할 된 문제는 서로 독립적이다.(중복 제거 X) → 순환적 분할 및 결합 가능
• 장점
  • Top-down 재귀 방식으로 구현하기에 코드가 직관적이다.
  • 문제를 나누어 해결한다는 특징상 병렬적으로 문제 해결이 가능하다.
• 단점
  • 재귀 함수 호출로 오버헤드가 발생할 수 있다.
  • 스택에 다량의 데이터가 보관되는 오버플로우가 발생할 수 있다.

병합정렬(Merge Sort)

• 하나의 리스트를 두개의 균일한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법.

동작과정

1. Divide - 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다
2. Conquer - 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면(left < right) 순환호출을 이용해 다시 분할 정복 방법을 적용한다.
3. Combine - 정렬된 부분 배열들을 하나의 배열에 병합한다.

def merge_sort(arr):
	def sort(low, high):
		if high - low < 2:
			return
		mid= (low + high) // 2
		sort(low, mid)
		sort(mid, high)
		merge(low, mid, high)

	def merge(low, mid, high):
		temp = []
		l,h = low, mid

		while l <mid and h<high:
			if arr[l] < arr[h]:
				temp.append(arr[l])
				l += 1
			else:
				temp.append(arr[h])
				h += 1
		while l < mid:
			temp.append(arr[l])
			l += 1
		while h < high:
			temp.append(arr[h])
			h += 1

		for i in range(low,high):
			arr[i] = temp[i - low]

코어타임

index는 왜 0부터 시작할까?

• 다익스트라
• 인덱스 규칙
  1. half-open interval [a,b)
  2. zero-base numbering

버블정렬의 진화

• 칵테일 정렬

요세푸스 문제

• queue 사용
• deque 사용
• 모듈러스 연산 사용

키워드 다시 한번 정리

• 몰랐던 부분 구멍이었던 부분을 메꿀 수 있었다.