[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가 나올 때까지 반복합니다.
연결 리스트 (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) 언어입니다. 이전 글에서 생성자와 소멸자에 대해 언급하였는데, 아래 내용을 필수적으로 알고있어야 이또한 이해할 수 있겠죠!
간단한 사각형 클래스 생성 코드입니다.
