공부하자 동진아

정의

  - 동적 계획법 (DP 라고 많이 부름)

      • 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서, 보다 큰 크기의 부분 문제를 해결,

            최종적으로 전체 문제를 해결하는 알고리즘

      • 상향식 접근법으로, 가장 최하위 답을 구한 후 저장, 해당 결과 값을 이용해서 상위 문제를 풀어가는 방식

      • Memoization 기법을 사용

          • Memoization (메모이제이션) 이란?

              • 프로그램 실행 시 이전에 계산한 값을 저장하여, 다시 계산하지 않도록 하여 실행 속도를 빠르게 하는 기술

      • 문제를 잘게 쪼갤 때, 부분 문제는 중복되어, 재활용됨

          • 예 : 피보나치 수열

  - 분할 정복

      • 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘

      • 하향식 접근법으로, 상위의 해답을 구하기 위해, 아래로 내려가면서 하위의 해답을 구하는 방식

          • 일반적으로 재귀함수로 구현

      • 문제를 잘게 쪼갤 때, 부분 문제는 서로 중복되지 않음

          • 예 : 병합 정렬, 퀵 정렬 등

공통점과 차이점

  - 공통점

      • 문제를 잘게 쪼개서, 가장 작은 단위로 분할

  - 차이점

      • 동적 계획법

          • 부분 문제는 중복되어, 상위 문제 해결 시 재활용됨

          • Memoization 기법 사용(부분 문제의 답을 저장해서 재활용하는 최적화 기법으로 사용)

      • 분할 정복

          • 부분 문제로 서로 중복되지 않음

          • Memoization 기법 사용 안함

동적 계획법 알고리즘 이해 (피보나치 수열)

  - recursive call 활용

def fibonacci(num):
	if num <= 1:
		return num
	return fibonacci(num + 1) + fibonacci(num + 2)

print(fibonacci(10))		# 55

  - 동적 계획법 활용

def fibonacci_dp(num):
	cache = [index for index in range(num + 1)]		# list comprehension
	cache[0] = 0
	cache[1] = 1

	for index in range(2, num + 1):
		cache[index] = cache[index - 1] + cache[index - 2]
	return cache[num]

print(fibonacci_dp(10))		# 55

재귀 용법(recursive call, 재귀 호출)

  - 함수 안에서 동일한 함수를 호출하는 형태

  - 여러 알고리즘 작성 시 사용되므로, 익숙해져야 한다.

예제

  - 팩토리얼 구하는 알고리즘 작성하기

  - 2! = 1 * 2

     3! = 1 * 2 * 3

     4! = 1 * 2 * 3 * 4

     규칙 : n! = n * (n-1)!

def factorial(num):
	if num > 1:
		return num * factorial(num - 1)
	else:
		return num	# 재귀 함수 종료
        
print(factorial(10))	# 362880

  - factorial() 함수를 호출할 때마다, 지역변수 n 이 생성됨

  - 시간 복잡도 / 공간 복잡도는 O(n)

  - 함수는 내부적으로 스택처럼 관리된다.

  - 리스트 총 합 알고리즘 작성하기

def sum_list(data):
	print(data)
	if len(data) == 1:
		return data[0]
	return data[0] + sum_list(data[1:])

data_list = [1, 2, 3, 4, 5]

print(sum_list(data_list))

#  [1, 2, 3, 4, 5]
#  [2, 3, 4, 5]
#  [3, 4, 5]
#  [4, 5]
#  [5]
#  15

선택 정렬이란?

  - 다음과 같은 순서를 반복하며 정렬하는 알고리즘

      1. 주어진 데이터 중, 최솟값을 찾음

      2. 해당 최솟값을 데이터 맨 앞에 위치한 값과 교체

      3. 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복

단계별로 생각하기

  - 예 : data_list = [5, 19, 3, 14]

  - 1차 로직

4개의 값 중에서 가장 작은 값 3을 제일 앞에 있는 5와 교체

맨 앞에 위치한 3고정

  - 2차 로직

맨 앞의 위치를 뺀 나머지 값에서 가장 작은 값 5를 19와 교체

앞으로 위치한 5고정

  - 3차 로직

고정 값을 제외한 나머지 값에서 가장 작은 값 14와 19교체

정렬 완료

알고리즘 구현

def selection_sort(data):
	for stand in range(len(data) - 1):
		lowest = stand
		for index in range(stand + 1, len(data)):
			if data[lowest] > data[index]:
				lowest = index
		data[lowest], data[stand] = data[stand], data[lowest]
	return data
    
data_list = [5, 19, 3, 14]
print(selection_sort(data_list))	# [3, 5, 14, 19]

정리

  - 버블 정렬과 성능상 큰 차이가 없다.

  - 비교연산에 대한 빅-오는 최악의 경우와 최선의 경우 구분 없이 O(n^2)이다.

  - 이동연산에 대한 빅-오는 최악의 경우와 최선의 경우 구분 없이 O(n)이다.

삽입 정렬이란?

  - 삽입 정렬은 두 번째 인덱스부터 시작하여 그 앞의 데이터들과 비교하여 삽입할 위치를 지정한 후

     데이터를 뒤로 옮기고 지정한 자리에 삽입하여 정렬하는 알고리즘

단계별로 생각하기

  - 예 : data_list = [9, 4, 1, 5, 7]

  - 두 번째 인덱스부터 시작

  - 앞의 데이터들과 비교하여 삽입할 위치를 지정 후, 데이터를 뒤로 옮기고 지정한 자리에 삽입

  - n개의 리스트가 있는 경우 최대 n-1번의 로직 적용

  - 1차 로직

  - 2차 로직

  - 3차 로직

  - 4차 로직

알고리즘 구현

def insertion_sort(data):
	for index in range(len(data) - 1):	# 로직 횟수
		for index2 in range(index + 1, 0, -1):	# index+1에서부터 -1씩 빼면서 1까지, range[start, stop, step]
			if data[index2] < data[index2 - 1]:
				data[index2], data[index2 - 1] = data[index2 - 1], data[index2]
			else:
				break
	return data
    
data_list = [9, 4, 1, 5, 7]
print(insertion_sort(data_list))	# [1, 4, 5, 7, 9]

정리

  - 비교연산과 이동연산에 대한 빅-오는 O(n^2)이다.

  - 보는 관점에 따라서 별도의 메모리를 필요로 하지 않는 '개선된 선택 정렬'과 유사하다고 느낄 수 있다.