스택 자료구조, 큐 자료구조, 재귀함수

 

그래프 탐색 알고리즘을 사용하기 위해 알아야할 자료구조를 알아보자

 

스택 자료구조

• 선입후출: 먼저 들어온 데이터가 나중에 나가는 형식의 자료구조
• 입구와 출구가 동일한 형태로 스택을 시각화 할 수 있다.(ex: 박스 쌓기)
• 스택 동작 예시

 

스택 구현 예제(python)

리스트 자료형 사용

- append() :가장 오른쪽에 원소 삽입

- pop(): 가장 오른쪽  원소 삭제

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[::-1]) #최상단 원소부터 출력(뒤집어서 출력)
print(stack[])

#실행결과 
#[1,3,2,5]
#[5,2,3,1]

 

 

---

큐 자료구조

• 선입선출: 먼저 들어온 데이터가 먼저 나가는 형식의 자료구조
• 큐는 입구와 출구가 모두 뚫혀있는 터널과 같은 형태로 시각화 할 수 있다.
• 리스트로도 큐를 구현할 수 있지만 deque를 이용하는게 시간복잡도가 작다.

큐 자료구조 예시 (이코테 강의)

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) #나중에 들어온 원소부터 출력

#실행결과
#deque([3,7,1,4])
#deque([4,1,7,3])

 

---

재귀함수

재귀함수(Recursive Function)란 자기 자신을 다시 호출하는 함수

 

1.단순한 형태의 재귀함수 예제

• '재귀 함수를 호출합니다.' 라는 문자열을 무한히 출력합니다.
• 어느정도 출력하다가 최대 재귀 깊이 초과 메세지가 출력됩니다.

def recursive_function():
  print('재귀 함수를 호출합니다.')
  recursive_function()
  
recursive_function()

 

2. 재귀함수 종료 조건

• 재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수의 종료 조건을 반드시 명시해야 합니다.
• 종료 조건을 제대로 명시하지 않으면 함수가 무한히 호출될 수 있다.
• 종료 조건을 포함한 재귀 함수 예제

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

 

3. 팩토리얼 구현 예제

• n! = 1 x 2 x 3 x ••• x (n-1) x n
• 수학적으로 0!과 1!의 값은 1입니다.

#반복적으로 구현한 n!
def factiorial_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: #n이 1이하인 경우 1을 반환
    return 1
  #n! = n *(n-1)!를 그대로 코드로 작성하기
  return n * factorial_recursive(n-1)
  
#각각의 방식으로 구현한 n! 출력(n = 5)
print('반복적으로 구현:',factiorial_iterative(5) )
print('재귀적으로 구현:',factorial_recursive(5) )

#실행결과
#반복적으로 구현: 120
#재귀적으로 구현: 120

 

4. 최대공약수 계산(유클리드 호제법) 예제

• 두 개의 자연수에 대한 최대공약수를 구하는 대표적인 알고리즘으로는 유클리드 호제법이 있습니다.
• 유클리드 호제법
  • 두 자연수 A,B에 대하여 (A > B) A를 B로 나눈 나머지를 R이라고 합시다.
  • 이때 A와 B의 최대공약수는 B와 R의 최대공약수와 같습니다.
• 유틀리드 호제법의 아이디어를 그대로 재귀함수로 작성
  • 예시 : GCD(192, 162)

단계	A	B
1	192	162
2	162	30
3	30	12
4	12	6

 

def gcd(a, b):
  if a % b == 0:
     return b
  else:
     return gcd(b, a % b)
  
 print(gcd(192,162))
 #실행결과
 #6

 

5. 재귀 함수 사용의 유의 사항

• 재귀 함수를 잘 활용하면 복잡한 알고리즘을 간결하게 작성할 수 있다.
• 모든 재귀 함수는 반복문을 이용하여 동일한 기능을 구현할 수 있다.
• 재귀 함수가 반복문보다 유리한 경우도 있고 불리한 경우도 있다.
• 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓인다.
  • -> 그래서 스택을 사용해야 할 때 구현상 스택 라이브러리 대신에 재귀 함수를 이용하는 경우가 많다.

 

 

- 출처 : 이코테 강의