[TIL: 0214] 스택2

ryun·2023년 2월 14일

TIL

목록 보기

18/34

재귀호출

자기 자신을 호출하여 순환 수행되는 것
함수에서 실행해야 하는 작업의 특성에 따라 일반적인 호출방식보다 재귀호출방식을 사용하여 함수를 만들면 프로그램의 크기를 줄이고 간단히
함수 호출하면 메모리 영역이 구분이 되고 따로따로 만들어지게 된다
리턴이라는 동작은 값을 대신 남겨놓으라는 의미
0과 1로 시작하고 이전의 두 수 합을 다음 항으로 하는 수열을 피보나치라 한다
i 번째 값 계산하는 함수 F를 정의한다면
F0 = 0, F1 = 1
Fi = Fi-1 + Fi-2 for i >= 2 전과 전전꺼를 더하면 현재가 된다 (단 i가 2이상)
피보나치 수열 i번째 항을 반환하는 함수를 재귀함수로 구현할 수 있다

 def fibo(n):
 	if n < 2:
    	return n
    else:
    	return fibo(n-1) + fibo(n-2)

메모이제이션

재귀호출 문제점
엄청난 중복 호출이 존재
컴퓨터 프로그램 실행할 때 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 해 실행속도 빠르게 하는 기술 > 동적계획법 핵심 기술
fibo(n)의 값을 계산하자마자 저장하면 실행시간을 O(n)으로 줄일 수 있다

DP(다이나믹 프로그래밍)

동적계획 알고리즘은 그리디와 같이 최적화 문제를 해결하는 알고리즘이다
동적 계획 알고리즘은 먼저 입력 크기가 작은 부분 문제들을 모두 해결한 후에 그 해들을 이용해 보다 큰 크기의 부분 문제를 해결해 최종적으로 원래 주어진 입력의 문제를 해결하는 알고리즘
피보나치 수 DP 적용 알고리즘

def fibo2(n):
f = [0] * (n + 1)
f[0] = 0
f[1] = 1
for i in range(2, n + 1):
	f[i] = f[i-1] + f[i-2]
    
return f[n]

메모이제이션을 재귀적 구조에 사용하는 것보다 반복적 구조로 DP를 구현한 것이 성능 면에서 보다 효율적
재귀적 구조는 내부에 시스템 호출 스택을 사용하는 오버헤드가 발생하기 대문
두 개의 인자를 갖는게 재귀의 기본형

def f(i, k):
    if i == k:  # 목표에 도달하면
        print(B)
        return
    else:
        B[i] = A[i]
        f(i + 1, k)


A = [i for i in range(1000)]
B = [0] * 1000
f(0, 1000)

DFS(깊이우선탐색)

비선형구조인 그래프 구조는 그래프로 표현된 모든 자료를 빠짐없이 검색하는 것이 중요

두 가지 방법
깊이 우선 탐색 (DFS)
너비 우선 탐색 (BFS)

DFS
"내가 다시 되돌아 올 곳을 저장"
시작 정점 한 방향으로 갈 수 있는 경로가 있는 곳까지 탐색해가다가 갈 곳이 없다면!
가장 마지막 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 정점으로 탐색을 계속하여
결국 모든 정점을 방문하는 순회방법(뒷걸음질)

그래프를 표현하는 방법

1. 딕셔너리의 활용

graph = {}

graph['A'] = ['B', 'C']
grpah['B'] = ['D', 'F']
.
.
.

2차원 배열의 활용

#   A B C D E F
# A 0 1 1 0 0 0
# B 0 0 0 1 0 1
# C 
# D
# E
# F

7 8  V E
1 2 1 3 2 4 2 5 4 6 5 6 6 7 3 7 

#V(정점), E(간선)
V, E = map(int, input().split())

data = list(map(int, input().split())

arr = [[0] * (V + 1) for _ in range*(V+i)]

visited = [0] * (V + i) # 방문 여부 확인하는 리스트

# 언더스코어 쓰는 이유 꺼내오는 값 쓰지 않을 경우
for _ in range(E):
	n1, n2 = arr[i+2], arr[i+2+i]
	arr[n1][n2] = 1 # n1과 n2는 인접해있다.
    arr[n2][n1] 1

탐색해보기 (이 형태에서 크게 벗어나지 않는다)

def dfs(v): # v는 지금 현재 탐색하는 정점
	visited[v] = 1
    print(v)
    
    # 현재 v는 시작정점, 인접한 정점 중 방문을 안한 곳
    for w in range(1, V + i):
    	if arr[v][w] == 1 and visited[w] == 0:
        dfs(w)
        
dfs(1)

가장 마지막에 만났던 갈림길의 정점으로 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 후입선출 구조의 스택 사용

1) 시작 정점 v를 결정하여 방문한다
2) 정점 v에 인접한 정점 중에서
방문하지 않은 정점 w가 있으면, 정점 v를 스택에 push하고 정점 w를 방문한다
그리고 w를 v로 하여 다시 2를 반복한다
방문하지 않은 정점이 없으면, 탐색 방향 바꾸기 위해 스택을 pop하여 받은 가장 마지막 방문 정점을 v로 하여 다시 2를 반복
3) 스택이 공백이 될때까지 2를 반복

초기상태: 배열 visited를 False로 초기화하고, 공백 스택을 생성

A 선택
A에 방문하지 않은 B, C가 있으니까 A를 스택에 push하고 B, C중에서 오름차순에 따라 B를 선택
B에서 D로 간다
D에서 F로 이동
F에서 E로 이동
E에서 C로 이동
스택이 비어있지 않으면 꺼낼 것
F에서 G로 이동
pop을 하는데 스택이 빌것 같으면 종료