이코테 2021] 3. 스택, 큐, 재귀함수

https://youtu.be/7C9RgOcvkvo

 

그래프 탐색 알고리즘

• 탐색(Search) : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
• ex) DFS, BFS : 코딩 테스트에서 매우 자주 등장하는 유형

 

스택 자료구조

• 먼저 들어온 데이터가 나중에 나가는 형식(선입후출)
• 입구와 출구가 동일한 형태

파이썬에서의 스택 : 리스트(List)

stack = []

stack.append(5) # 삽입
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()

print(stack[::-1]) # 최상단 원소부터 출력 == 먼저 나가고자 하는 원소부터
print(stack) # 최하단 원소부터 출력 == 가장 먼저 들어온 순서부터

---

큐 자료구조

• 먼저 들어 온 데이터가 먼저 나가는 형식(선입선출)
• 입구와 출구가 모두 뚫려 있는 터널과 같은 형태

파이썬에서의 큐 : 라이브러리 사용

리스트 자료형으로도 큐 구현 가능 but 시간 복잡도가 더 높아져 비효율적

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(queue) # 먼저 들어온 순서대로 출력
queue.reverse() # 역순으로 바꾸기
print(queue) # 나중에 들어온 순서대로 출력

---

재귀 함수(Recursive Function)

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

종료 조건

• 재귀 함수를 문제 풀이에서 사용할 땐, 재귀 함수의 종료 조건을 반드시 명시해야
• if not, 함수가 무한히 호출될 수 있음

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

실행 결과)

1번째 재귀함수에서 2번째 재귀함수를 호출합니다.

2번째 재귀함수에서 3번째 재귀함수를 호출합니다.

3번째 재귀함수에서 4번째 재귀함수를 호출합니다.

...

98번째 재귀함수에서 99번째 재귀함수를 호출합니다.

99번째 재귀함수에서 100번째 재귀함수를 호출합니다.

99번째 재귀함수를 종료합니다.

98번째 재귀함수를 종료합니다.

97번째 재귀함수를 종료합니다.

...

2번째 재귀함수를 종료합니다.

1번째 재귀함수를 종료합니다.

 

---

활용 예제) 팩토리얼 구현

(수학적 약속: 0! = 1! = 1)

# 재귀적으로 구현한 n!
def factorial_recursive(n):
	if n<=1:
    	return
    return n * factorial_recursive(n-1)

# 출력
print('재귀적으로 구현:', factorial_recursive(5))

실행 결과)

재귀적으로 구현: 120

---

최대공약수 계산

 

 

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

print(gcd(192,162))
# 실행결과
# 6

유의 사항

• 복잡 알고리즘을 간결하게 작성 가능
• 오히려 다른 사람이 이해하기 어려운 코드가 될 수 있으므로, 신중하게 사용
• 모든 재귀 함수는 반복문을 이용하여 동일한 기능을 구현 가능 (유리한 경우도 있고 불리한 경우도 있고)
• 컴퓨터가 함수를 연속으로 호출 시 -> 컴퓨터 메모리 내부에 스택 프레임이 쌓임
  • 따라서, 스택 사용 시 스택 라이브러리 대신에 재귀 함수를 이용하는 경우가 많다.