재귀호출 문제

1. k번째 수 찾기

• 문제 : n개의 숫자가 차례대로 주어질 때, 매 순간마다
  “지금까지 입력된 숫자들 중에서 k번째로 작은 수”를 반환하는 프로그램을 작성하세요.
  프로그램의 입력으로는 첫째줄에 n과 k가 입력되고,
  둘째줄에 n개의 숫자가 차례대로 주어집니다.
• 코드 :

def findKth(myInput, k) :
    # 매 순간마다 k번째로 작은 원소를 리스트로 반환합니다.
    result = []
    data = []
    for elment in myInput:
        data.append(elment)
        data.sort()
        if len(data)<k:
            result.append(-1)
        else:
            result.append(data[k-1])
    return result


def main():
    firstLine = [int(x) for x in input("n과 k를 입력하세요 (예시:10 3): ").split()]
    myInput = [int(x) for x in input("n개의 숫자를 차례대로 입력하세요 (예시:1 9 8 5 2 3 5 6 2 10): ").split()]
    print('정렬 결과: ', *findKth(myInput, firstLine[1]))


if __name__ == "__main__":
    main()

2. 퀵정렬

• 문제 : 입력으로 n개의 수가 주어지면, quick sort를 구현하는 프로그램을 작성하세요.
• 1차 코드

def quickSort(array):
    if len(array) <= 1:
        return array
    
    data = array[0] 
    # 본인이 들어가서 그런가....?
    bigList=[]
    smallList=[]
    for i in array:
        if i >data:
            bigList.append(i)
        elif i < data:
            smallList.append(i)

• 분석 : 첫번째 테케는 맞췄지만 나머지 4개의 테케가 틀림.
• 정답 코드

def quickSort(array):
    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. isRightParenthesis(p)

1. 함수정의 : 괄호가 쌍이 맞게 설계가 되어있으면 yes를 아니면 no를 반환한다.
2. 기저조건 : '공백' | '(' | ')' 요러게 3가지의 경우임.
3. 동작설계 : 인접한 괄호를 쌍으로 계속 지워가면서 마지막으로 괄호가 1개 남으면 no 한개도 안 남으면 yes

• 분석 : 왼쪽, 오른쪽의 괄호 개수가 같다면 결국엔 올바른 짝이 된다는 생각... 하지만 이것은 재귀함수가 아니다....
• 코드

def checkParen(p):
    if len(p) == 0:
        return "YES"
    elif len(p) == 1:
        return "NO"
    
    for i in range(len(p)-1):
        if p[i] == '(' and p[i+1] == ')' :
            q = p[:i] +p[i+2:]
            return checkParen(q)

    return "NO"

• 분석
  1.우선 항상 recursionerror가 뜨지 않도록 기저조건을 맞춰줘야함.
  2.return 값에는 반드시 해당 함수가 들어있어야 함.
  3.동작설계부분은 아직 너무 어려움...

기타 코드

name => python에 내장되어있는 하나의 변수
main을 실행시키는 방법
1. run
2. if name == "main":
main() // java처럼 main 메소드 시작
else name == "파일이름":
ex) print("이 것은 파일이름에서 import 되었습니다.")