본문은 파이썬 알고리즘 인터뷰( 박상길 저 )를 참고하여
리트코드의 24번 문제를 풀이한 것임을 미리 밝힌다.
//재귀함수
어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.
"재귀함수가 뭔가요?"
"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어. 마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지. 그의 답은 대부분 옳았다고 하네.
그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.
"재귀함수가 뭔가요?"
"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을...
출처는 나무위키다.
그러니까 자기자신과 똑같은 기능을 하는 함수를 품은 함수로
나선을 생각하면 가장 쉽다.
특정 조건을 달성하면 그 나선의 끝에 다다르고
그러면 백트랙킹을 통해서 확정하지 못한 모든 값들을 정해주게 된다.
// 예
리트코드 ( leetcode ) 24 번 문제 24. Swap Nodes in Pairs 를 보면 재귀적인 풀이법을 잘 알 수 있다.
재귀함수는 보통 선형자료형의 재정렬에 많이 쓰는데
특히 연결리스트의 풀이에 사용되는 경우가 많은 것 같다.
문제는
저런식으로 2개 단위로 노드를 묶어서 바꾸라는 것인데
아래와 같이 생각할 수 있다.
노드가 3개일때 이렇게 바꾸면 잘 연결될것 같다.
그렇지만 노드가 4개 이상일 경우 문제가 생긴다.
사진 속 2번으로 바꾸어준 노드가 이전의 노드와 연결되어있지 않기 때문이다.
그래서 더 많은 노드에 대해서 그려보면
이런식의 교환을 해주면 된다는 사실을 알게 된다.
이런식으로 꼬인건 같지만 마지막 노드에 도달했을때 쭉 잡아당겨서 펴주기만 하면
하나의 새로운 연결리스트가 생기는 과정은 재귀함수를 쓰기 딱 좋은 과정이다.
그러면 재귀문을 만들기 위한 패턴을 찾아보자.
노드가 길어지면 길어질수록
저 까만 큰 원 안에 있는 패턴들이 반복된다는 것을 알 수 있다.
따라서 저 단위의 기능들을 함수로 구현하여 중첩시키면
재귀적인 풀이가 완성된다.
그러면 한번 생각해보자.
함수라면 입력과 출력이 있어야한다.
그러면 첫번째 원을 봤을때 입력값은 맨 처음 주어지는 노드(head)임을 알 수 있다.
그러면 이 함수의 중첩이 끝나고 정말로 마지막에 리턴해야하는 값은 무엇일까?
그것은 바로 잡아당겨 쭉 편 후의 첫번째 노드가 되는 두번째 노드 (head.next) 임도 알 수 있다.
그러면 이 입력과 출력을 유지하면서 다음 큰원의 입력과 출력도 같은 모양으로 만들어 줄 수 있을까?
오른쪽 원이 왼쪽원의 안으로 들어가게 쌓아올린다고 생각하고
화살표를 유지하면서 원들을 한번 겹쳐보자.
조악한 수준의 그림이지만 어찌됐건 재귀적인 구조를 나름 최대한 표현해 보았다.
위의 사슬같았던 그림을 겹쳐놓은 모양이다.
왜 처음에 나선이야기를 했고
나선의 끝에서는 어떤 일이 벌어지는지 이야기했는지 이제는 알 수 있겠다.
이런식으로
1. 현재의 정렬상태를 그리고
2. 바꿔야하는 정렬상태를 그린 후
3. 패턴의 최소단위를 찾아내고
4. 최초의 패턴에서 함수의 입출력을 찾은 다음
(어차피 최종적으로 이루어지는 입출력은 최초의 패턴이다.)
5. 패턴들을 겹치면서 입출력이 어떻게 구성되는지 파악한다.
위의 과정을 거치면 재귀함수의 구조를 조금은 쉽게 발견할 수 있을 것이다.
위의 그림과 같은 내용의 코드를 첨부하면서
글을 마치도록 하겠다.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
if head and head.next:
pin = head.next
head.next = self.swapPairs(pin.next)
pin.next = head
return pin
return head
댓글