재귀, DFS

알고리즘하면서 재귀의 중요성을 알려준 DFS. 하지만 어려워서 계속 까먹는다. 그래서 이번에 정리를 아예 해둘려고 한다.

 

재귀를 쓰는 이유

 

뭐 사실 알고리즘 시간에서는 특정 케이스를 제외하면 시간복잡도나 효율면에서 떨어진다고 학습을 하기 마련이다. 하지만 재귀를 사용하면 수많은 for문을 사용해야되는 경우, 복잡한 코드 같은 경우를 손 쉽게 구현할 수 있다.

종만북에서 n 개의 서로 다른 원소a 중 x 개의 원소를 순서를 고려해서 뽑는 경우의 수를 구한다면, x개만큼의 반복문이 필요하기 때문

재귀함수를 잘 사용할려면 문제를 소문제로 잘 분리 시켜야된다.

 

간단한 아래 예시를 보자

 

아래는 중복순열을 구하는 재귀함수코드이다. 이 코드의 핵심은 트리를 만들면서 진행한다는 소리인데 이게 아는 사람들은 금방 이해하겠지만 나같은 경우는 이해하는데 상당히 까다로웠던 코드이다.

def DFS(L):
    global cnt
    if L==m:
        for j in range(m):
            print(res[j], end=" ")
        print()
        cnt+=1
    else:
        for i in range(1, n+1):
            res[L] = i
            DFS(L+1)


n, m = map(int, input().split())
cnt = 0
res = [0] * m
DFS(0)
print(cnt)

 

일단 변수 설명부터하면 res는 통이라고 생각하면 될 듯 하다.

내가 n개의 공을 가지고 있는데 m개 뽑는 경우의 수 여기서 m개 뽑아서 넣는 통이다. 그리고 DFS코드를 보게 되면 L이라는 변수를 받아 함수가 실행되게 된다. 이 L은 Level로 알고리즘시간의 트리 레벨과 동일한 의미이다.

 

어쨋든 함수는 for문으로 진행되게 되는데 1, n까지 뿌리를 펼치는거라고 생각하면 편하다. 촥촥촥 펼치면서 통에 하나씩 i를 투입하게 된다. 만약 3 1 이 들어가게 되면 1 2 3 의 문어발을 뻗는다. 그런 다음 재귀함수로 문어발을 계속해서 뻗어나간다. 재귀함수는 종료조건이 가장 중요한데 여기서 L==m일때 종료인건데 상자의 개수보다 넘칠때를 기준으로 상자값을 출력해주는 코드이기 때문이다.

 

이를 통해서 상당히 많은 곳에 응용이 가능한데 DFS, 브루드포스, DP 등에도 응용이 가능하다. 이 상태트리를 머리속으로 그려나가는게 포인트인 것 같다.

 

두번째로 비슷한 유형인 순열문제를 한 번 더 설명하겠다. 

 

순열은 고등학교때 배운 P를 이용하면 되는데 순서가 있는 n개의 원소중 m개를 뽑는 경우를 말한다. 

쨋든 이것도 마찬가지로 재귀함수로 구현이 가능하다. 사실 위와 거의 흡사다.

def DFS(L):
    global cnt
    if L == m:
        cnt+=1
        for i in range(m):
            print(arr[i], end=" ")
        print()
        return
    else:
        for i in range(1, n+1):
            if check[i] == 0:
                check[i] = 1
                arr[L]=i
                DFS(L+1)
                check[i] = 0


n, m = map(int,input().split())

arr = [0] * (n)
check = [0] * (n+1)
cnt = 0
DFS(0)

print(cnt)

하지만 차이점은 check라는 리스트가 있고, 이를 통해 뽑은 것을 또 뽑지 않도록 만들어줄 수 있다. check는 0으로 세팅을 하고 만약 0이다! 하면 들어가서 아까와 같이 통에 넣어준다. 포인트는 통에서 꺼낼때 DFS(L+1) 다음에 check를 다시 0으로 복구시켜 다시 공을 사용가능하게 만드는 것이 핵심 부분이다.

 

 

위를 잘 이용하면 DP로 유명한 퇴사도 재귀함수로 구현이 가능하다. 

 

https://www.acmicpc.net/problem/14501

14501번: 퇴사

 

이는 추후 작성하겠다.

 

완성