[Concept] 재귀함수와 연결리스트(linked list)

패스트 캠퍼스 알고리즘 강의를 듣고 정리한 글입니다.

 

재귀함수

재귀란 컴퓨터 과학에 있어서 재귀는 자신을 정의할 때 자기 자신을 재참조하는 방법을 뜻하며, 이를 프로그래밍에 적용한 재귀 호출의 형태로 많이 사용된다.    - 위키백과 -

재귀함수는 함수가 자신을 정의할 때 다시 자신(함수)을 호출하는 함수입니다.

자칫하면 무한 반복이 될 수 있기 때문에 종료 조건을 무조건 추가해주어야 합니다.

 

하나의 예를 봅시다.

def recursive(data):
  if data <0:
    print('ended')
  else:
    print(data)
    recursive(data-1)
    print('returned', data)
    
recursive(4)

 

어떻게 출력될까요?

• 4를 인자로 넘겨줬고, 4는 0 이상이니까, 4 출력 후 3을 인자로 넘겨줍니다.
• 3을 인자로 넘겨줬고, 3은 0 이상이니까, 3 출력 후 2를 인자로 넘겨줍니다.
• 2을 인자로 넘겨줬고, 2는 0 이상이니까, 2 출력 후 1을 인자로 넘겨줍니다.
• 1을 인자로 넘겨줬고, 1은 0 이상이니까, 1 출력 후 0을 인자로 넘겨줍니다.
• 0을 인자로 넘겨줬고, 0은 0 이상이니까, 0 출력 후 -1을 인자로 넘겨줍니다.
• -1을 인자로 넘겨줬고, -1은 0 미만이므로 'ended' 출력 후 recursive(-1) 함수가 종료됩니다. 종료되면서 다시 돌아오면 데이터가 0인 상태에서 print문으로 넘어가 'returned0'이 출력됩니다.
• recursive(0)이 끝났으니, 다시 데이터가 1인 상태로 돌아와서 print문으로 넘어가 'returned1'이 출력됩니다.
• recursive(1)이 끝났으니 다시 데이터가 2인 상태로 돌아와서 print문으로 넘어가 'returned2'가 출력됩니다.
• recursive(2)가 끝났으니 다시 데이터가 3인 상태로 돌아와서 print문으로 넘어가 'returned3'이 출력됩니다.
• recursive(3)이 끝났으니 다시 데이터가 4인 상태로 돌아와서 print문으로 넘어가 'returned4'가 출력됩니다.

그렇기 때문에 순서대로 'returned0', 'returned1', 'returned2', 'returned3', 'returned4'를 출력합니다.

 

결과는

4
3
2
1
0
ended
returned0
returned1
returned2
returned3
returned4

 

재귀함수는 스택의 동작 구조를 이용합니다.

 

사진과 함께 다시 설명하겠습니다.

위에서 언급했듯이, data가 -1이 되면서 0보다 작아져서 드디어 if문이 실행된 후 해당 함수의 동작은 끝나게 되는데

해당 함수가 끝나면 Process Stack에서 recursive(-1) 함수가 종료되면서

1. Process Stack에서 -1이 사라지고,  (아래 사진은 사라진 모습) 그다음 줄인 print('returned', data)  가 실행됩니다.

2. 그후 함수 recursive(0)이 Process Stack에서 꺼내지고(종료되고), 그다음 print문이 실행됩니다.

이 과정을 데이터 4가 나올 때까지 반복합니다.

 

왼) 데이터 -1이 꺼내진 모습  오) 데이터 0이 꺼내진 모습

 

 

연결 리스트 (linked list)

연결 리스트, 링크드 리스트는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다.   - 위키백과 -

위키백과에서 내린 정의처럼, 한 노드는 데이터와 포인터 두개의 값을 가지고 있습니다.

포인터가 보통 다음 노드의 주소값을 가지고 있는데 만약 마지막 노드라면, 해당 포인터는 null값입니다.

 

사진으로 봤을 때, B 데이터를 가지고 있는 노드의 주소(0011h)를 A 데이터를 갖고 있는 노드가 가리키고 있네요.

위처럼 다음 노드의 주소값을 포인터라는 공간에 가지고 있기 때문에

우리는 첫 번째 노드만 알면 되겠지요?

 

파이썬 구현

• 파이썬에서 링크드 리스트 구현시, 파이썬 클래스를 활용합니다. 데이터와 주소를 저장하기위한 구조로 class가 적당!
• node 생성하는  클래스를 만든 뒤 객체를 생성해봅시다.

class Node:
    def __init__(self, data, next=None): # 다음 노드를 가리킬거면 next도 전달
        self.data = data
        self.next = next
                
# 노드 객체 생성
node1 = Node(1)
node2 = Node(2)

# Node와 Node 연결(포인터 활용)
node1.next = node2

head = node1  # 가장 앞에 있는 주소를 head로 저장

 

링크드 리스트에서는 무조건 맨 첫번째의 노드를 이용해서 시작해야합니다. (계산이든 뭐든!)

head에 저장하는 것이 그 이유입니다.

 

이제 노드를 추가하는 함수를 생성한 뒤, 데이터 3~9까지의 노드를 생성해봅시다. (데이터 2까지는 생성해놨으니!)

class Node:
    def __init__(self, data, next=None): # 다음 노드를 가리킬거면 next도 전달
        self.data = data
        self.next = next
        
# 맨 뒤에 노드 추가 메서드 생성
def add(data):
	node = head # 맨 앞 노드부터 시작
    while node.next:
    	node = node.next # 맨 끝 노드까지 이동
    node.next = Node(data)
    
for index in range(3,10):
	add(index)

 

이렇게 생성한 노드들을 출력해봅시다.

node = head
while node.next:  # 다음 노드가 있으면 실행
	print(node.data)
    node = node.next

# 마지막 노드는 다음 노드가없으므로 출력이 안됨. 따로 출력해줘야함
print(node.data)  # 9 출력

 

 링크드 리스트의 장단점 (전통적인 C언어에서의 배열과 링크드 리스트)

• 장점
    - 미리 데이터 공간을 미리 할당하지 않아도 됨
      - 배열은 미리 데이터 공간을 할당 해야 함
• 단점
    - 연결을 위한 별도 데이터 공간(포인터)이 필요하므로, 저장공간 효율이 높지 않음
    - 연결 정보를 찾는 시간이 필요하므로 접근 속도가 느림(인덱스 조회와 달리 head로부터 순차적으로 조회해야함)
    - 중간 데이터 삭제/삽입 시, 앞뒤 데이터의 연결을 재구성해야 하는 부가적인 작업 필요

 

링크드 리스트의 복잡한 기능

• 유지 관리에 부가적인 구현이 필요함
• 특정 노드 중간에 삽입 & 삭제

# 삽입 ver.
node3 = Node(1.5)
node = head
search = True

while search:
    if node.data ==1:
        search = False  # 앞 노드를 찾으면 False가 됨
    else:
        node = node.next

node.next, node3.next = node3, node.next  # 2번으로 잇는 것을 3번으로 잇게함


# 삭제 ver.
def delete(self, data):
  if self.head == '':
    print('해당 값을 가진 노드가 없습니다.')
    return
  
  # 첫 노드를 지운다면
  if self.head.data == data:
    temp = self.head
    self.head = self.head.next
    del temp
  else:
    node = self.head
    while node.next:
      if node.next.data == data:
        temp = node.next
        node.next = node.next.next
        del temp
        return
      else:
        node = node.next

 

전체

지금까지 한 것을 한번에 작성해보고, 추가로  특정 데이터를 찾는 메서드도 작성하겠습니다.

코드가 길어져 접은 글로 작성하였습니다.

class Node:
	def __init__(self, data, next=None):
    	self.data = data
        self.next = next

class NodeMgmt:
	def __init__(self, data):
    	self.head = Node(data)
        
    # 추가
    def add(self,data):
    	if (self.head == ''):  # 첫 노드가 없으면
        	self.head = Node(data)  # 첫 노드 생성
        else:  # 첫 노드가 있으면
        	node = self.head
            while node.next:  # 다음 노드가 없는 끝으로 이동
            	node = node.next
            node.next = Node(data)
    # 출력        
    def desc(self):
    	node = self.head
        while node:
        	print(node.data)
            node = node.next
    # 삭제
    # 1. head 삭제
    # 2. 가장 마지막 노드 삭제
    # 3. 중간 노드 삭제
    def delete(self, data):
    	# 노드가 아예 없는 경우
        if self.head == '':
            print ('해당 값을 가진 노드가 없습니다.')
            return
            
        # 경우의 수1: self.head를 삭제해야할 경우 - self.head를 바꿔줘야 함
        if self.head.data == data: 
            temp = self.head # self.head 객체를 삭제하기 위해, 임시로 temp에 담아서 객체를 삭제했음
            self.head = self.head.next # 만약 self.head 객체를 삭제하면, 이 코드가 실행이 안되기 때문!
            del temp  # 해당 객체 주소로 삭제
        
        # 경우의 수2: self.head가 아닌 노드를 삭제해야할 경우
        else:
            node = self.head
            while node.next: 
                if node.next.data == data:
                    temp = node.next
                    node.next = node.next.next  # 삭제할 노드의 next 주소를 저장
                    del temp                         
                    pass                             
                else:
                    node = node.next
    # 조회                
    def search_node(self, data):
        node = self.head
        while node:
            if node.data == data:
                return node
            else:
                node = node.next


# 노드 추가                
linkedlist1 = NodeMgmt(0)
for data in range(1,10):
	linkedlist1.add(data)
linkedlist1.desc()

# 노드 조회
node = node_mgmt.search_node(4)
print (node.data)

 

 

번외)

클래스와 Object

파이썬은 객체지향(OOP, Object Oriented Programming) 언어입니다. 이전 글에서 생성자와 소멸자에 대해 언급하였는데, 아래 내용을 필수적으로 알고있어야 이또한 이해할 수 있겠죠! 

간단한 사각형 클래스 생성 코드입니다.