[알고리즘] 재귀호출, 퀵정렬, 완전탐색

채림·2022년 6월 29일

수학적 귀납법

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

N=1일때 성립함을 보인다(기저조건)
P(k)가 성립한다고 가정할 때 P(k+1)도 성립함을 보인다
모든 자연수에 대해 성립하게 됨

=>재귀호출 알고리즘 끝까지 제대로 되나 들여다 볼 필요 없음, 처음이랑 그 다음만 되면 그 뒤로는 쭉 된다고 보자!!

퀵정렬(quick sort)

재귀호출을 이용한 정렬, 빠름
피봇(첫번째 값)을 기준으로 피봇보다 작은건 왼쪽, 큰건 오른쪽에 정렬, 왼쪽과 오른쪽에서 재귀호출
원소가 1개 or 0개이면 정렬 완료된 상태(기저조건)
수학적 귀납법처럼 처음 한 번이랑 기저조건일때만 보기

#오름차순 정렬
def quickSort(array):
    if len(array) <= 1: #array 요소가 하나인 경우(=정렬완료, 기저조건)
        return array #정렬완료된 array 반환

    pivot = array[0] #첫번째 원소를 pivot으로 설정

    left = getSmall(array[1: ], pivot) #첫번째 원소를 뺀 배열과 첫번째 원소(=pivot)을 넘김
    right = getLarge(array[1: ], pivot)

    return quickSort(left) + [pivot] + quickSort(right) #좌/우의 정렬된 리스트와 가운데 pivot값을 합쳐 리턴

def getSmall(array, pivot) : #array에서 pivot보다 작은 값을 리스트로 반환
    data = []
    for a in array :
        if a <= pivot :
            data.append(a)
    return data

def getLarge(array, pivot) : #array에서 pivot보다 큰 값을 리스트로 반환
    data = []
    for a in array :
        if a > pivot :
            data.append(a)
    return data

재귀함수 디자인하기

함수의 정의를 명확히(명확한 명제)
기저 조건(Base condition)에서 함수가 제대로 동작하게(n=1일때 or 남은 원소개 0/1개일 때 등...)
함수가 작은 input에 대하여 제대로 동작한다고 가정하고 함수를 완성(n-1에 대해 동작한다고 가정하고 n을 설계)

실습) 짝 맞는 괄호 판단

#짝 맞는 괄호인지 판단하기
def checkParen(p):
    #1. 기저조건 처리
    #2. p에서 인접한 괄호쌍을 찾아 제거
    #3. 재귀호출에서 괄호쌍 끝까지 제거해 나가기
    if len(p) == 0 : #문자열 길이가 0이면 yes
        return "YES"
    elif len(p) == 1 : #1이면 (이나 )만 있는거니까 no
        return "NO"
    for i in range(len(p)-1) : #쌍이 맞으면 마지막은 )일거니까 (마지막-1)번째까지 (를 확인하기
        if p[i] == '(' and p[i+1] == ')' :
            q = p[:i] + p[i+2:] #p[i]랑 p[i+1]을 뺀 나머지로 배열을 다시 만들기
            return checkParen(q)
    return "NO" #문자열에 2개 이상 있는데 제거가 안된다면 쌍이 안맞는 괄호