코딩테스트/알고리즘 기초

스택, 큐, 재귀 함수

ggulgood 2022. 4. 22. 04:34

탐색(Search): 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룬다.

대표적인 탐색 알고리즘 : DFS, BFS

 

- 스택

- 큐

- 재귀함수

 

 

자료구조(Data Structure) : 데이터를 표현하고 관리하고 처리하기 위한 구조

-> 스택과 큐는 자료구조의 기초 개념

  • 삽입(push): 데이터를 삽입한다.
  • 삭제(pop): 데이터를 삭제한다.

- 스택 

- 큐

- 재귀함수

 

  • 오버플로: 특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할 때 발생
  • 언더플로: 특정한 자료구조에 데이터가 전혀 들어가있지 않은 상태에서 삭제 연산을 수행하면 언더플로 발생

 

 

 

스택(Stack)

박스 쌓기에 비유 가능.

선입후출(First In Last Out) 구조 또는 후입선출(Last In Fist Out)

 

 

예제

stack = []

stack.append(5) # append()로 삽입
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop() # pop()으로 삭제, 삭제할 때 가장 나중에 들어온 수가 먼저 삭제된다
stack.append(1)
stack.append(4)
stack.pop()

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

 

결과

[5, 2, 3, 1]
[1, 3, 2, 5]

 

 

큐(Queue)

대기 줄에 비유 가능

선입선출(First In First Out) 구조

 

파이썬으로 큐를 구현할 때는 collections 모듈에서 제공하는 deque 자료구조를 활용하자.
list(queue)로 리스트화 시킬 수 있다.

 

 

예제

from collections import deque

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

queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()


print(list(queue))

 

결과

[3, 7, 1, 4]

 

 

 

재귀 함수

자기 자신을 다시 호출하는 함수

 

 

예제

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

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

recursive_function(1)

 

재귀 함수의 수행은 스택 자료 구조를 이용한다.

함수를 계속 호출했을 때 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료되기 때문이다.

 

-> 스택 자료구조를 활용해야 하는 상당수 알고리즘은 재귀 함수를 이용해서 간편하게 구현 가능

-> DFS

 

 

 

재귀 함수로 팩토리얼 구현

return n * factorial_recursive(n - 1)

 

예제

# 반복적으로 구현한 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: # n이 1 이하인 경우 1을 반환
        return 1
    # n! = n * (n - 1)!를 그대로 코드로 작성하기
    return n * factorial_recursive(n - 1)

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

 

 

출처: [이것이 취업을 위한 코딩 테스트다 with 파이썬] 서적

저작자표시