자료구조와 Algorithm

수업 내용

Queue

입구와 출구가 다르기 때문에 먼저 들어간 것이 먼저 나오는 FIFO(First In First Out) 자료구조
- e.g. 병원에서 먼저 온 환자가 먼저 진료를 받을 수 있는 것처럼.
- c.f. 입구와 출구가 같은 Stack은 LIFO(Last in First Out)
앞쪽을 front, 뒤쪽을 rear

선형 큐(Linear Queue)

rear와 front가 insert/pop의 방향이 뒤쪽으로만 향한다.
한 번 사용한 메모리 공간이 버려진다.
모든 요소를 앞으로 당겨주지 않으면 overflow 발생
모든 요소를 앞으로 당겨주려면 그만큼 시간복잡도가 비효율적이다.
구현하기 Pseudocoding
- front와 rear는 queue를 나타내는 list의 인덱스 값이다.
- front 인덱스값은 항상 첫 자료를 가리킨다.
- rear 인덱스 값은 마지막 자료의 다음 인덱스이다.
- front와 rear의 값이 같다면 큐는 비어있다.
- append할 때는 rear가 가리키는 자리에 data를 넣고 rear에 1을 더해준다.
- pop할 때는 front가 가리키는 값을 리턴해주고 front가 갖는 값을 None으로 바꿔준 후 front에 1을 더해준다.
- queue를 보여줄 때는 list에서 front와 rear 전까지의 범위를 슬라이싱하여 출력

class LinearQueue:
    def __init__(self, Qsize):
	self.front = 0
	self.rear = 0
	self.capacity = Qsize
	self.queuelist = [None]*self.capacity

    def isEmpty(self):
	flag = False
	if self.front == self.rear:
	    flag = True
	return flag

    def append(self, value):
	self.queuelist[self.rear] = value
	self.rear += 1

    def popleft(self):
	if self.isEmpty:
	    return None
	answer = self.queuelist[self.front]
	self.queuelist[self.front] = None
	self.front += 1
	return answer

    def show(self):
	queue = self.queuelist[self.front:self.rear]
	print(queue)

원형 큐 (Circular Queue)

선형 큐의 단점을 보완하기 위해 등장한 큐 자료구조
rear가 list의 끝으로 가서 더이상 갈 곳이 없으면 처음으로 돌아온다.
- 다만 꽉 차있으면 갈 수 없다.
- rear에 list의 length로 나눈 나머지로 계산해 넣음으로써 list의 length를 초과하지 않도록 제한할수 있다.
front도 동일하게 처리해준다.
구현하기 pseudocoding
- front와 rear의 값이 같고 front가 가리키는 위치의 값이 None이 아니면 리스트가 꽉 차 있다는 뜻
- append할 때도 리스트가 꽉 차 있는지 확인한 후 동작시킨다.
- show는 네 가지 경우의 수를 가지므로 각각 나누어 처리한다.
  - 리스트가 비어있는 경우
  - 리스트가 꽉 차 있는 경우
  - 그 외의 경우 중 front가 rear보다 큰 / 작은 경우

class CircularQueue:
    def __init__(self, Qsize):
	self.front = 0
	self.rear = 0
	self.capacity = Qsize
	self.queuelist = [None]*self.capacity

    def isEmpty(self):
	flag = False
	if self.front == self.rear and self.queuelist[self.front] == None:
	    flag = True
	return flag

    def isFull(self):
	flag = False
	if self.front == self.rear and self.queuelist[self.front != None:
	    flag = True
	return flag

    def append(self, value):
	if not self.isFull():
	    self.queuelist[self.rear] = value
	    self.rear = (self.rear + 1) % self.capacity
	    return True # append 잘 됐다는 의미로 True 반환
	else:
	    return False


    def popleft(self):
	if not self.isEmpty():
	    answer = self.queuelist[self.front]
	    self.queuelist[self.front] = None
	    self.front = (self.front + 1) % self.capacity
	    return answer
	else:
	    return None

    def show(self):
	out = []
	if self.isFull():
	    out = self.queuelist[self.front:] + self.queuelist[:self.rear]
	elif not self.isEmpty():
	    if self.front < self.rear:
		out = self.queuelist[self.front:self.rear]
	    else:
		out = self.queuelist[self.front:] + self.queuelist[:self.rear]
	return out

노드 기반 큐 (Linked Queue)

노드를 기반으로 구현된 큐 자료형태
구현하기 Pseudocoding
- prev와 next를 None값으로 가지며 value를 전달받아 초기화되는 노드 클래스를 정의한다.
- 초기화에서 노드처럼 head와 tail을 갖게끔 하고 둘다 None을 가리키게 한다.
- append 빈 큐의 경우 새로 노드를 생성한 후 head와 tail이 모두 새로 생성된 노드를 가리키게 한다.
  - 비어있지 않은 큐의 경우 tail이 가리키는 노드를 prev 값으로 가지게 하여 새로운 노드를 생성한 후 tail이 가리키고 있는 노드의 next에 의해 가리켜지게 하고, tail은 새로운 노드를 가리키게 한다.
- popleft
  - 빈 큐의 경우 pop 하려면 None을 return한다.
  - 노드 하나만 있는 경우(head와 tail이 가리키는 노드가 같은 경우) 해당 노드의 value를 리턴하고 head와 tail은 None값을 할당
  - 그 외의 경우는 head가 가리키는 노드의 value를 리턴한 후 head가 원래 head가 가리키던 노드의 next를 가리키게 한다.
  - 원래 next였던 새로운 head의 prev에 None을 할당하여 pop된 데이터가 garbage collection 대상이 될 수 있도록 해야 한다.
- show는 리스트처럼 출력되게 하기 위해서 스트링으로 작업해주되, linked list처럼 curr 변수가 None이 될때까지 값을 조회하여 출력한다.

class Node:
    def __init__(self, value, prev, next):
	self.prev = prev
	self.next = next
	self.value = value

class LinkedQueue:
    def __init__(self):
        self.head = None
        self.tail = None
    
    def append(self, value):
	if self.head is None:
	    self.head = Node(value, None, None)
	else:
	    self.tail.next = Node(value, self.tail, None)
	    self.tail = self.tail.next

    def popleft(self):
	if self.head is None:
	    return None
	if self.head == self.tail:
	    answer = self.head.value
	    self.head = None
	    self.tail = None
	    return answer

	answer = self.head.value
	self.head = self.head.next
	self.head.prev = None
	    return answer

    def show(self):
	s = '[ '
	curr = self.head
	while curr is not None:
	    s += str(curr.value) + ' '
	    curr = curr.next
	s += ']'
	print(s)

head가 가리키는 노드의 prev와 tail가 가리키는 노드의 next는 항상 None을 가리켜야 한다.

재귀함수

DFS(Depth First Search, 깊이우선탐색)에 활용된다.
if와 else를 나누면 웬만한 재귀는 다 해결할 수 있다.
- if는 재귀를 종료하고 탈출하는 리턴문
- else는 자기자신을 호출하며 퍼져나가는 영역

스택프레임 작동 원리

스택프레임에는 동작하고 있는 함수가 지역변수, 매개변수, 복귀 주소 등을 가지고 저장되며 해당 함수의 모든 코드가 끝나기 전에는 pop되지 않는다.
동작하던 함수의 모든 코드가 끝나기 전에 다른 함수를 호출하면 스택프레임의 위에 쌓이며, 위에 있는 함수가 pop되어 나가고 나서 다시 복귀주소를 가지고 진행 중이던 코드로 돌아가 나머지를 실행한다.
아래 함수를 호출한 경우 인자로 들어간 숫자 n이 print된 후 자기자신을 n-1의 인자를 넘기며 호출하기 때문에 3, 2, 1 순서로 출력된다.

def DFS(n):
    if n == 0:
	return
    else:
	print(n, end=' ')
	DFS(n-1)

DFS(3)
# 3, 2, 1

print문을 재귀호출 후에 실행하면, 스택프레임에 쌓인 재귀함수가 pop 되기 전에 print를 하기 때문에 1, 2, 3 순서로 출력된다

def DFS(n):
    if n == 0:
	returnn
    else:
	DFS(n-1)
	print(n, end=' ')

DFS(3)
# 1, 2, 3

Memoization

이미 호출되었던 재귀함수의 값을 저장해두면 호출할 때마다 뻗어나가지 않고 이미 저장된 값을 가져다 씀으로써 성능을 획기적으로 올릴 수 있다.
memoize 없이 호출하는 경우
- 스택프레임에는 [fibo(5), [fibo(4), [fibo(3), [fibo(2), fibo(1)], fibo(2)], fibo(3), [fibo(2), fibo(1)]]] 등 같은 함수가 여러번 호출된다.

def fibo(n):
    if n <= 2:
	return 1
    else:
	return fibo(n-1) + fibo(n-2)

fibo(5)

dynamic table을 두고 저장하게끔 하면 이미 호출된 재귀함수의 리턴값을 보관하고 있다가 다시 호출하지 않고 꺼내다 쓸 수 있다.

def fibo(n):
    if dy[n] > 0:
	return dy[n]
    if n <= 2:
	return 1
    else:
	dy[n] = fibo(n-1) + fibo(n-2)
	return dy[n]

dy = [0] * 50
fibo(5)

이진트리(Binary Tree) for DFS (Depth First Search)

자식이 두 개 이하인 트리자료구조
array를 이진트리로 만드는 공식 규칙
- (부모노드 인덱스)* 2 + 1 = (왼쪽 자식노드 인덱스)
- (부모노드 인덱스)* 2 + 2 = (오른쪽 자식노드 인덱스)

이진트리의 순회방식

전위순회(preorder): 부모노드-> 왼쪽자식->오른쪽자식 순서로 순회
중위순회(inorder): 왼쪽자식->부모노드->오른쪽자식 순서로 순회
후위순회(postorder): 왼쪽자식->오른쪽자식->부모노드 순서로 순회

구현하기 pseudocoding

이진트리 클래스의 초기화로 array를 만들어준다.
각 순회방식을 메서드로 정의하는데 그 메서드 안에서는 DFS라는 함수를 정의하고 인자로 인덱스값 0을 넣어 실행한다.
- DFS 함수는 자기자신을 호출하되 인덱스값이 이진트리의 노드 개수와 크거나 같으면 리턴한다.
각 순회방식 메서드 안의 DFS 함수는 전위, 중위, 후위에 따라 print문 위치가 달라진다.
- 전위순회: 현재 노드의 값을 print 먼저 하고 자식 노드의 인덱스 넣어 DFS 호출
- 중위순회: 왼쪽 자식 노드의 인덱스 값을 넣어 DFS 호출 후 현재 노드값 print, 그 후 오른쪽 자식 노드 호출
- 후위순회: 자식노드들의 인덱스를 넣어 DFS 호출한 후에 현재 노드의 값을 print

import array
class BinaryTree:
    def __init__(self, arr):
	self.array = array.array('l', arr) #arr에 담긴 정수 자료형을 배열로.

    def preorder(self):
	def DFS(self):
	    if idx >= len(self.array):
		return
	    else:
		print(self.array[idx])
		DFS(idx * 2 + 1)
		DFS(idx * 2 + 2)
	DFS(0)

    def inorder(self):
	def DFS(self):
	    if idx >= len(self.array):
		return
	    else:
		DFS(idx * 2 + 1)
		print(self.array[idx])
		DFS(idx * 2 + 2)
	DFS(0)

    def postorder(self):
	if idx >= len(self.array):
	    return
	else:
	    DFS(idx * 2 + 1)
	    DFS(idx * 2 + 2)
	    print(self.array[idx])
	DFS(0)

느낀 점

큐 안에도 선형 큐, 원형 큐, 노드기반 큐 등 여러가지 종류가 있다니 재미있다.
트리구조를 배열 형태로 나타낼 수 있다는 게 흥미롭고 특히 순회 방식이 엄청 복잡할 줄 알았는데 단순히 프린트문의 위치에 따라 달라진다는 것은 인상적이었다.

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

20210625.md

20210625.md

자료구조와 Algorithm

수업 내용

Queue

선형 큐(Linear Queue)

원형 큐 (Circular Queue)

노드 기반 큐 (Linked Queue)

재귀함수

스택프레임 작동 원리

Memoization

이진트리(Binary Tree) for DFS (Depth First Search)

이진트리의 순회방식

구현하기 pseudocoding

느낀 점

Files

20210625.md

Latest commit

History

20210625.md

File metadata and controls

자료구조와 Algorithm

수업 내용

Queue

선형 큐(Linear Queue)

원형 큐 (Circular Queue)

노드 기반 큐 (Linked Queue)

재귀함수

스택프레임 작동 원리

Memoization

이진트리(Binary Tree) for DFS (Depth First Search)

이진트리의 순회방식

구현하기 pseudocoding

느낀 점