[이코테] 스택, 큐, 재귀

 탐색 (Search)

•   탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정이며, 대표적인 탐색 알고리즘으로 DFS, BFS가 존재함
•  DFS와 BFS를 제대로 이해하려면 기본 자료구조인 스택, 큐와 재귀에 대한 이해가 있어야함

 

 자료구조(Data Structure)

  : 데이터를 표현하고 관리하고 처리하기 위한 구조로, 스택과 큐는 자료구조의 기초 개념

  : 자료구조의 기초 개념으로 삽입(Push), 삭제(Pop) 등의 핵심적인 함수로 구성됨

 

 

 스택

• 스택은 박스 쌓기로 비유할 수 있음. 박스를 쌓을 때는 아래에서 위로 차곡차곡 쌓으며, 박스를 치울 때는 위에서 박스를 내려야함
• 이처럼, 선입후출(FILO - First In Last Out) 구조 또는 후입선출(LIFO - Last In First Out) 구조 라고 함
• 다음은 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제() 의 예시

# 스택 파이썬 구현
stack = []

# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()

print(stack) # 최하단 원소부터 출력
print(stack[::-1]) # 최상단 원소부터 출력

// 스택 구현 - 자바
import java.util.*;

public class exex{
	public static void main(String[] args) {
		Stack<Integer> s = new Stack();
		
		// 삽입(5) - 삽입(2) - 삽입(3) -삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
		s.push(5);
		s.push(2);
		s.push(3);
		s.push(7);
		s.pop();
		s.push(1);
		s.push(4);
		s.pop();
		
		// 스택의 최상단 원소부터 출력
		while (!s.empty()) {
			System.out.println(s.peek());
			s.pop();
		}
	}
}

 

 

큐

• 큐는 놀이공원 대기줄을 비유할 수 있음. 줄을 설 때 먼저 온 사람이 먼저 들어가며, 나중에 온 사람일 수록 나중에 들어감
• 이처럼, 선입선출(FIFO - First In First Out) 구조임
• 다음은 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()의 예시
• 파이썬에서 큐를 구현할 때 collections 모듈에서 제공하는 deque 자료구조를 활용하면 데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적이며, queue 라이브러리를 이용하는 것보다 더 간단함

 

 

 

# 큐 구현 - 파이썬
from collections import deque

# 큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque()

# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()

print(queue) # 먼저 들어온 순서대로 출력
queue.reverse() # 다음 출력을 위해 역순으로 바꾸기
print(queue) # 나중에 들어온 원소부터 출력

// 큐 구현 - 자바
import java.util.*;

public class exex{
	public static void main(String[] args) {
		Queue<Integer> q = new LinkedList<>();
		
		// 삽입(5) - 삽입(2) - 삽입(3) -삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
		q.offer(5);
		q.offer(2);
		q.offer(3);
		q.offer(7);
		q.poll();
		q.offer(1);
		q.offer(4);
		q.poll();
		
		// 스택의 최상단 원소부터 출력
		while (!q.isEmpty()) {
			System.out.println(q.poll());
		}
	}
}

 

 

재귀 함수

• DFS 와 BFS를 구현하기 위해 재귀 함수도 필요하며, 재귀 함수란 자기 자신을 다시 호출하는 함수
• 재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수가 언제 끝날지, 종료 조건을 꼭 명시해야 함
• 재귀 함수를 이용하는 대표적인 예제로는 팩토리얼(factorial) 문제가 있음
• 컴퓨터 내부에서 재귀 함수의 수행은 스택 자료구조를 이용하며, 함수를 계속 호출했을 때 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료되기 때문
• 스택 자료구조를 활용해야하는 상당수 알고리즘은 재귀 함수를 통해 간편하게 구현될 수 있으며, DFS가 대표적인 예

# 재귀함수 예제1 - 파이썬
def recursive_function(i):
	# 100번째 출력했을 때 종료되도록 종료 조건 명시
    if i == 100:
    	return
    print(i, '번째 재귀 함수에서', i + 1, '번째 재귀 함수를 호출합니다.')
    recursive_function(i+1)
    print(i, '번째 재귀 함수를 종료합니다.')


recursive_function(1)

출력 예시 1번째 재귀 함수에서 2번째 재귀 함수를 호출합니다. 2번째 재귀 함수에서 3번째 재귀 함수를 호출합니다. 3번째 재귀 함수에서 4번째 재귀 함수를 호출합니다. . . . 99번째 재귀 함수에서 100번째 재귀 함수를 호출합니다. 99번째 재귀 함수를 종료합니다. . . . 1번째 재귀 함수를 종료합니다.

 

 

# 2가지 방식으로 구현한 팩토리얼 - 파이썬
# 반복적으로 구현한 n!
def factorial_iterative(n):
	result = 1
    # 1부터 n까지의 수를 차례대로 곱하기
    for i in range(1, n+1):
    	result *= i
    return result

# 재귀적으로 구현한 n!
def factorial_recursive(n):
	if n <= 1:
    	return 1
    # n! = n * (n-1)!를 그대로 코드로 작성하기
    return n * factorial_recursive(n-1)


# 각각의 방식응로 구현한 n! 출력 (n = 5)
print('반복적으로 구현:', factorial_iterative(5))
print('재귀적으로 구현:', factorial_recursive(5))

출력 예시 반복적으로 구현 : 120 재귀적으로 구현 : 120

: 두 번째 재귀 함수를 사용해서 팩토리얼 구현한 방식이 소스코드가 더욱 간결하고, 수학에서 점화식(재귀식)을 그대로 구현했기 때문에 중요하다. 또한 이 개념은 나중에 '다이나믹 프로그래밍'의 알고리즘 방식에서도 이어진다

 

 

 

 

Ellen's thinking

: 학과 전공 수업인 자료구조 시간에 어렵게 스택, 큐 등을 구현한 것을 배웠는데 라이브러리나 파이썬의 방식을 이용한다면 저렇게 간결하게 구현할 수 있다는 것이 놀랍다. 이후에 라이브러리를 사용하지 않고 스택, 큐 등의 자주 쓰이는 자료구조 소스코드 구현을 정리해봐야겠다.