[Week01] 알고리즘 - 재귀함수

[Week01] 알고리즘 키워드 - 정수론, 배열, 문자열, 재귀함수, 정렬, 완전탐색, 시간복잡도

 

재귀함수

• 작은 문제의 해결법을 사용해서 더 큰 문제를 푼다
• 절차적 지향적 사고를 버리고 수학적 귀납방식으로 생각하기 
• 점화식(두개의 항 사이에 성립하는 관계)과 초항 구하기
• loop(반복문)와 recursion(재귀)은 서로 변환이 가능하다

재귀함수는 자기자신을 부르는 함수이기 때문에 절차적으로 코드를 쫒아가면 헷갈릴 수 밖에 없다. 귀납법적으로 생각할 수 있다면 이상적이지만, 힘들다면 처음 불렀던 함수와 그 안에서 부른 함수, 그 안에서 부른 함수 다다른 한수라고 생각하고 함수인자와 depth를 적어가면서 어떻게 돌아가는지 하나하나 쫓아가는 것도 이해하는 방법 중 하나이다. 

 

구현방법

1. 문제의 정의를 정확하게 표기한다. (선언형 프로그래밍*)2. 종료 조건+ 컬스택 : 호출의 흐름을 저장해서 이번 처리가 끝나면 돌아갈 곳을 기억하는 장소.

               호출의 흐름을 따라갈줄알아야한다. (컬스택이 어떻게 쌓이고 줄어드는 지)

 

 

✅ 순열과 조합

 

순열 - 서로 다른 n 개 중 r 개를 골라 순서를 정해 나열하는 가짓수

def permutation(arr, n):
    result = []
    if n == 0:
        return [[]]
    for i in range(len(arr)):
        elem = arr[i]
        for rest in permutation(arr[:i] + arr[i+1:], n - 1):
            result.append([elem] + rest)
    return result

print(permutation([0,1,2,3], 2))

 

조합 - 서로 다른 n개 중 r개를 취하여 조를 만든다. 

def combination(arr, n):
    result = []
    if n == 0:
        return [[]]
    for i in range(len(arr)):
        elem = arr[i]
        for rest in combination(arr[i + 1:], n - 1):
            result.append([elem] + rest)
    return result

print(combination([0,1,2,3], 2))

 

 

 

✅ 백트래킹 : 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘

 

DFS의 일종인 백트래킹, 문제 제한이 크지않을 경우 사용가능하다.

 

백트래킹 연습 문제 - 백준 1569(N과 M)

import sys

x,y = map(int,sys.stdin.readline().split())

arr = [0] * y #수열 조합을 담는 리스트
isused = [False] * (x+1) #해당 수가 사용됐는지 확인 - 인덱스 값이 해당 수

def back(n) :
    if n == y :
        print(' '.join(map(str,arr)))
    else :
        for i in range(1,x+1) :
            if isused[i] == False :
                    arr[n] = i
                    isused[i] = True
                    back(n+1)
                    isused[i] = False

back(0)

좀 더 깔끔하게 표현

이 경우 isused list가 따로 없어 중복 값을 허용하는 경우 이슈가 발생할 수 있다.

n,m = map(int,input().split())
 
arr = []
 
def back():
    if len(arr)==m:
        print(' '.join(map(str,arr)))
        return
    
    for i in range(1,n+1):
        if i not in arr: #중복값을 허용할 경우 조건문에 걸리지않음
            arr.append(i)
            back()
            arr.pop()
 
back()

 

 

 

재귀함수는 뒤에 나오는 다양한 알고리즘 방식에 쓰이기 때문에 꼭 익혀두길 바란다...!