Day2 - Stack1

재귀 호출

자기 자신을 호출하여 순환 수행되는 것
함수에서 실행해야 하는 작업의 특성에 따라 일반적인 호출방식보다 재귀호출방식을 사용하여 함수를 만들면 프로그램의 크기를 줄이고 간단하게 작성
- 재귀 호출의 예) factorial
  - n에 대한 factorial : 1부터 n까지의 모든 자연수를 곱하여 구하는 연산
  - 마지막에 구한 하위 값을 이용하여 상위 값을 구하는 작업을 반복
factorial 함수에서 n=4인 경우의 실행

0과 1로 시작하고 이전의 두 수 합을 다음 항으로 하는 수열을 피보나치라 한다.
피보나치 수열의 i번 째 값을 계산하는 함수 F를 정의하면 다음과 같다.
- F0 = 0, F1 = 1
- Fi = F(i-1) + F(i-2) for i≥2
위의 정의로부터 피보나치 수열의 i번째 항을 반환하는 함수를 재귀함수로 구현할 수 있다.

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

Memoization

앞의 예에서 피보나치 수를 구하는 함수를 재귀함수로 구현한 알고리즘은 문제점이 있다.
“엄청난 중복 호출이 존재한다”는 것

메모이제이션(memoization)은 컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행속도를 빠르게 하는 기술이다. 동적 계획법에 핵심이 되는 기술이다.
앞의 예에서 피보나치 수를 구하는 알고리즘에서 fibo(n)을 값을 계산하자마자 저장하면(memoize), 실행시간을 Θ(n)으로 줄일 수 있다.

# memo를 위한 배열을 할당하고, 모두 0으로 초기화 한다.
# memo[0]을 0으로 memo[1]는 1로 초기화 한다.

def fibo(n)
        global memo
        if n >= 2 and memo[n] == 0;
                memo[n] = (fibo(n-1) + fibo(n-2))
        return memo[n]

memo = [0] * (n+1)
memo[0] = 0
memo[1] = 1

DP(Dynamic Programming)

동적 계획(Dynamic Programming) 알고리즘은 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘이다.
동적 계획 알고리즘은 먼저 입력 크기가 작은 부분 문제들을 모두 해결한 후에 그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결하여, 최종적으로 원래 주어진 입력의 문제를 해결하는 알고리즘이다.
피보나치 수 DP 적용
- 피보나치 수는 부분 문제의 답으로부터 본 문제의 답을 얻을 수 있으므로 최적 부분 구조로 이루어져 있다.
1. 문제를 부분 문제로 분할한다.
  - Fibonacci(n) 함수는 Fibonacci(n-1) 과 Fibonacci(n-2)의 합
  - Fibonacci(n-1) 은 Fibonacci(n-2) 과 Fibonacci(n-3)의 합
  - Fibonacci(2) 함수는 Fibonacci(1) 과 Fibonacci(0)의 합
  - Fibonacci(n) 은 Fibonacci(n-1), Fibonacci(n-2), … Fibonacci(2), Fibonacci(1), Fibonacci(0) 의 부분집합으로 나뉜다.
2. 부분 문제로 나누는 일을 끝냈으면 가작 작은 부분 문제부터 해를 구한다.
3. 그 결과는 테이블에 저장하고, 테이블에 저장된 부분 문제의 해를 이용하여 상위 문제의 해를 구한다.
4. def fibo(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의 구현 방식
- recursive 방식 : fib1()
- iterative 방식 : fib2()
- memoization을 재귀적 구조에 사용하는 것보다 반복적 구조로 DP를 구현한 것이 성능 면에서 보다 효율적이다.
- 재귀적 구조는 내부에 시스템 호출 스택을 사용하는 오버헤드가 발생하기 때문이다.

DFS(깊이우선탐색)

비선현구조인 그래프 구조는 그래프로 표현된 모든 자료를 빠짐없이 검색하는 것이 중요함.
두 가지 방법
- 깊이 우선 탐색(Depth First Search, DFS)
- 너비 우선 탐색(Breadth First Search, BFS)
시각 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 정점으로 탐색을 계속 반복하여 결국 모든 정점을 방문하는 순회방법
가장 마지막에 만났던 갈림길의 정점으로 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 후입선출 구조의 스택사용

DFS 알고리즘

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

DFS 예

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

정점 A를 시작으로 깊이 우선 탐색을 시작

정점 A에 방문하지 않은 정점 B, C가 있으므로 A를 스택에 push하고, 인접정점 B와 C 중에서 오름차순에 따라 B를 선택하여 탐색을 계속한다.

정점 B에 방문하지 않은 정점 D, E가 있으므로 B를 스택에 push 하고, 인접정점 D와 E 중에서 오름차순에 따라 D를 선택하여 탐색을 계속한다.

정점 D에 방문하지 않은 정점 F가 있으므로 D를 스택에 push 하고, 인접정점 F를 선택하여 탐색을 계속한다.

정점 F에 방문하지 않은 정점 E, G가 있으므로 F를 스택에 push 하고, 인접정점 E와 G 중에서 오름차순에 따라 E를 선택하여 탐색을 계속한다.

정점 E에 장문하지 않은 정점 C가 있으므로 E를 스택에 push 하고, 인접정점 C를 선택하여 탐색을 계속한다.

정점 C에서 방문하지 않은 인접정점이 없으므로, 마지막 정점으로 돌아가기 위해 스택을 pop 하여 받은 정점 E에 대해서 방문하지 않은 인접정점이 있는지 확인한다.

정점 E는 방문하지 않은 인접정점이 없으므로, 다시 스택을 pop 하여 받은 정점 F에 대해서 방문하지 않은 인접정점이 있는지 확인한다.

정점 F에 방문하지 않은 정점 G가 있으므로 F를 스택에 push 하고, 인접정점 G를 선택하여 탐색을 계속한다.

정점 G에서 방문하지 않은 인접정점이 없으므로, 마지막 정점으로 돌아가기 위해 스택을 pop 하여 받은 정점 F에 대해서 방문하지 않은 인접정점이 있는지 확인한다.

정점 F에서 방문하지 않은 인접정점이 없으므로, 다시 마지막 정점으로 돌아가기 위해 스택을 pop 하여 받은 정점 D에 대해서 방문하지 않은 인접정점이 있는지 확인한다.

정점 D에서 방문하지 않은 인접정점이 없으므로, 다시 마지막 정점으로 돌아가기 위해 스택을 pop 하여 받은 정점 B에 대해서 방문하지 않은 인접정점이 있는지 확인한다.

정점 B에서 방문하지 않은 인접정점이 없으므로, 다시 마지막 정점으로 돌아가기 위해 스택을 pop하여 받은 정점 A에 대해서 방문하지 않은 인접정점이 있는지 확인한다.

현재 정점 A에서 방문하지 않은 인접 정점이 없으므로, 마지막 정점으로 돌아가기 위해 스택을 pop하는데, 스택이 공백이므로 깊이 우선 탐색을 종료한다.

728x90