[자료구조] 스택, 큐, 재귀함수 / Python 파이썬

2022. 5. 6. 14:33·python/자료구조 & 알고리즘
728x90
반응형

 

이번 포스트에서는 스택, 큐, 재귀함수에 대해 살펴볼 예정이다.

 


스택 자료구조

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

ex) 박스 쌓기, 프링글스 통 구조

 

(LIFO) 마지막에 있는 데이터가 먼저 처리된다.

 

스택구조를 이용하는 것은 단순한 리스트 삽입구조를 이용하면된다. (시간 복잡도 O(1), 상수시간)

stack = [] 
stack.append(n) 
stack.pop(n)

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

이미지 출처: awesomeo184.log


큐 자료구조

  • 먼저 들어온 데이터가 먼저 나가는 형식(선입선출)의 자료구조이다.
  • 큐는 입구와 출구가 모두 뚫려있는 터널과 같은 형태로 시각화할 수 있다.

(FIFO)차례대로 먼저 들어온 데이터가 먼저 처리된다.

큐의 기본 연산

파이썬의 리스트를 이용하면 큐는 기본적으로 다음과 같은 연산들이 필요하다.

Q.enqueue(e): back에 요소 e를 추가
Q.dequeue(): front의 요소를 반환하면서 제거
Q.first(): front의 요소를 제거하지 않고 반환
Q.is_empty(): 큐가 비어있으면 True를 반환

 

 

 

큐 구조를 이용하는 것은 deque 라이브러리를 이용한다. (시간 복잡도 O(1), 상수시간)

리스트로 구조 적으로는 큐를 구현할 수 있지만 시간복잡도가 길어진다는 단점이 있다.

from collections import deque

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

queue.append(n) #원소를 넣을 때
queue.popleft(n) #원소를 뺄 때

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

 

 


재귀 함수

  • 재귀 함수(Recursive Function)란 자기 자신을 다시 호출하는 함수를 의미한다.
  • 단순한 형태의 재귀함수 예재
    • '재귀 함수를 호출합니다.'라는 문자열을 무한히 출력합니다.
    • 어느 정도 출력하다가 최대 재귀 깊이 초과 메시지가 출력됩니다.
def recursive_function():
	print('재귀 함수를 호출합니다.')
    recursive_function()
recursive_function()

 

 

재귀 함수가 계속 출력된 창

*코딩테스트에는 일반적으로 재귀함수를 이용해도 통과할 수 있다.

재귀 함수를 통해 while이나 for문을 이용하지 않아도 반복문을 이용할 수 있다.

스택 프레임과 비슷하다. (선입 후출)

재귀 함수의 종료 조건

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

* 종료 조건을 포함한 재귀 함수 예제

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

재귀함수 구현 예제

팩토리얼 구현 

  • n! = 1 * 2 * 3 * ''' * (n-1) * n
  • 수학적으로 0!과 1!의 값은 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):
    # n이 1 이하인 경우 1을 반환    
    if n <=1:
        return 1
    # n! = n * (n-1)!를 그대로 코드로 작성
    return n * factorial_recursive(n-1)

 

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

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

 

1단계: A = 192 ,B = 162 

R = A % B = 30

# 이 때 나머지 값(R)을 구하고 나면 2단계에서 A,B = B,R 로 스왑된다.

 

2단계: A = 162 (1단계의 B값), B = 30 (1단계의 R값)

 

R = A % B = 12

 

3단계: A = 30 (2단계의 B값), B = 12 (2단계의 R값)

 

R = A % B = 6

 

4단계: A = 12 (2단계의 B값), B = 6 (2단계의 R값)

 

R = A % B = 0

 

나머지가 0이므로 따라서 6이 최대공약수가 된다.

 

def gcd(a, b): 
	if a % b == 0: 
    	return b
    else: 
    	return gcd(b, a % b)

 

재귀함수 사용의 유의 사항

 

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



 

 

 

 

 


References

- 알음알음 성장로그

  https://hei-jayden.tistory.com/35

- awesomeo184.log

  https://velog.io/@awesomeo184/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%81%90Queue

728x90
반응형

'python > 자료구조 & 알고리즘' 카테고리의 다른 글

[자료구조] 트리 Tree / Python 파이썬  (0) 2022.05.25
[자료구조] 연결 리스트 Linked-List / Python 파이썬  (0) 2022.05.12
[알고리즘] 정렬 알고리즘 / Python 파이썬  (0) 2022.05.03
[알고리즘] 8-Puzzle (8 퍼즐) BFS, DFS 구현 / Python 파이썬  (0) 2022.04.28
[자료구조] 해시, 해시법(hashing) / Python 파이썬  (0) 2022.04.12
'python/자료구조 & 알고리즘' 카테고리의 다른 글
  • [자료구조] 트리 Tree / Python 파이썬
  • [자료구조] 연결 리스트 Linked-List / Python 파이썬
  • [알고리즘] 정렬 알고리즘 / Python 파이썬
  • [알고리즘] 8-Puzzle (8 퍼즐) BFS, DFS 구현 / Python 파이썬
sillon
sillon
꾸준해지려고 합니다..
    반응형
  • sillon
    sillon coding
    sillon
  • 전체
    오늘
    어제
    • menu (614)
      • notice (2)
      • python (68)
        • 자료구조 & 알고리즘 (23)
        • 라이브러리 (19)
        • 기초 (8)
        • 자동화 (14)
        • 보안 (1)
      • coding test - python (301)
        • Programmers (166)
        • 백준 (76)
        • Code Tree (22)
        • 기본기 문제 (37)
      • coding test - C++ (5)
        • Programmers (4)
        • 백준 (1)
        • 기본기문제 (0)
      • 공부정리 (5)
        • 신호처리 시스템 (0)
        • Deep learnig & Machine lear.. (41)
        • Data Science (18)
        • Computer Vision (17)
        • NLP (40)
        • Dacon (2)
        • 모두를 위한 딥러닝 (강의 정리) (4)
        • 모두의 딥러닝 (교재 정리) (9)
        • 통계 (2)
      • HCI (23)
        • Haptics (7)
        • Graphics (11)
        • Arduino (4)
      • Project (21)
        • Web Project (1)
        • App Project (1)
        • Paper Project (1)
        • 캡스톤디자인2 (17)
        • etc (1)
      • OS (10)
        • Ubuntu (9)
        • Rasberry pi (1)
      • App & Web (9)
        • Android (7)
        • javascript (2)
      • C++ (5)
        • 기초 (5)
      • Cloud & SERVER (8)
        • Git (2)
        • Docker (1)
        • DB (4)
      • Paper (7)
        • NLP Paper review (6)
      • 데이터 분석 (0)
        • GIS (0)
      • daily (2)
        • 대학원 준비 (0)
      • 영어공부 (6)
        • job interview (2)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    programmers
    Python
    백준
    소수
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
sillon
[자료구조] 스택, 큐, 재귀함수 / Python 파이썬
상단으로

티스토리툴바