알고리즘 :: 재귀호출, 수학적 귀납법, 퀵정렬, 재귀함수 디자인

엘리스 알고리즘의 정석에서 배운 내용

 

 

알고리즘

• 유한성
  • 무한루프는 알고리즘이 아니다
• 명확성
• 입력
• 출력
• 효과성

 

 

재귀호출

함수가 자기 자신 호출

왜 사용할까?

 

 

수학적 귀납법

모든 자연수 n에 대해 n! <= nⁿ 증명하시오

3가지 확인

1. N = 1 일 때 성립

1 <= 1

 

2. P(k)가 성립한다고 가정하고, P(k + 1)이 성립한지 본다

k! * (k + 1) <= k^k * (k + 1)

 

3. 1과 2를 만족하면 모든 자연수 n에 대해 P(n)의 성립

 

위 방법은 그저 하나의 판단법

진짜 의미는

명제를 재귀적으로 증명하는 방법

 

 

퀵정렬

재귀호출의 대표적 예시

일반적인 정렬중 가장 빠른 정렬

 

방법

피벗(기준)을 잡고

작거나 같은 값을 왼쪽으로,

큰 값은 오른쪽으로 정렬

 

퀵정렬 사용 예시

# quickSort
def quickSort(array):
	
    # 길이가 1보다 작으면 반환
    if len(array) <= 1 :
        return array
    
    # 피벗(기준)을 맨 앞에 값으로
    pivot = array[0]        
    
    # 피벗 제외하고 왼쪽, 오른쪽으로 정렬
    left = getSmall(array[1:], pivot)
    right = getLarge(array[1:], pivot)
        
    # 왼쪽과 오른쪽 리스트 더하기
    return quickSort(left) + [pivot] + quickSort(right)
        
    # 작거나 같은 값 반환
def getSmall(array, pivot) :
    data = []
    
    for a in array :
        if a <= pivot:
            data.append(a)
    return data

	# 큰 값 반환
def getLarge(array, pivot):
    data = []
    
    for a in array :
        if a > pivot:
            data.append(a)
    return data

 

 

재귀함수 디자인

재귀함수 디자인 3단계

1. 함수의 정의 명확히
2. Base condition(기저 조건)에서 함수가 제대로 동작하도록
3. 함수가 작은 input에서 제대로 동작한다고 가정하고 완성

 

재귀함수 이용 올바른 괄호 판단 예시

# 재귀함수 이용 올바른 관호 판단
def checkParen(p):

	# 길이가 0이면 올라잇
    if len(p) == 0 :
        return "YES"
    # 길이가 1이 되면 NO
    elif len(p) == 1 :
        return "NO"
    
    # () 쌍을 확인해서 제거하고 1이나 0이 될 때까지 재귀
    for i in range(len(p) - 1):
        if p[i] == "(" and p[i+1] == ")":
            q = p[:i] + p[i+2:]
            return checkParen(q)

    # 길이가 1초과되어 남으면 당연 NO
    return "NO"

 

 

recursion by startuplab.io