[Python] [알고리즘] 3. 스택(1)

스택의 특성

스택에 저장된 구조는 선형 구조를 가진다. 선형구조는 자료 간의 관계가 1:1의 관계를 갖는 것을 의미하며, 비선형구조는 자료 간의 관계가 1:N의 관계를 갖는 것을 의미한다.

스택에 자료를 삽입하거나 스택에서 자료를 꺼낼 수 있으며, 마지막에 삽입한 자료를 가장 먼저 꺼낸다. (후입선출)

스택의 구현

스택을 프로그램에서 구현하기 위해서 필요한 자료구조와 연산

자료구조: 자료를 선형으로 저장할 저장소, 배열을 사용할 수 있다. 저장소 자체를 스택이라고 부르기도 한다. 스택에서 마지막 삽입된 원소의 위치를 top이라고 한다.

연산

• 삽입: 저장소에 자료를 저장한다. 보통 push라고 부른다.
• pop: 저장소에서 자료를 꺼낸다. 꺼낸 자료는 삽입한 자료의 역순으로 꺼낸다.(데이터가 바로 삭제되는 것은 아니다.)
• isEmpty : 스택이 공백인지 아닌지를 확인하는 연산을 의미한다.
• peek: 스택의 top에 있는 원소를 반환하는 연산을 의미한다

스택의 push

append 메소드를 통해 리스트의 마지막에 데이터 삽입

def push(item):
	s.append(item)

스택의 pop

def pop():
	if len(s) == 0:
		#underflow
		return
	else:
		return s.pop()

스택의 응용1: 괄호 검사

• 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같아야 한다.
• 같은 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 한다.
• 괄호 사이에는 포함 관계만 존재한다.

문자열에 있는 괄호를 차례대로 조사하며 왼쪽 괄호를 만나면 스택에 삽입하고, 오른쪽 괄호를 만나면 스택에서 top 괄호를 삭제한 후 오른쪽 괄호와 짝이 있는지를 검사한다.

스택의 응용2: function call

프로그램에서의 함수 호출과 복귀에 따른 수행 순서를 관리

• 가장 마지막에 호출된 함수가 가장 먼저 실행을 완료하고 복귀하는 후입선출 구조로, 스택을 이용해서 수행순서를 관리한다.
• 함수 호출이 발생하면 호출한 함수 수행에 필요한 지역변수, 매개변수 및 수행 후 복귀 주소 등의 정보를 스택 프레임에 저장하여 시스템 스택에 삽입한다.
• 함수의 실행이 끝나면 시스템 스택을 pop하면서 프레임에 저장되어 있던 복귀주소를 확인 후 복귀한다.
• 함수 호출과 복귀에 따라 이 과정을 반복하며 전체 프로그램 수행이 종료되면 시스템 스택은 공백 스택이 된다.

재귀호출

자기 자신을 호출하여 순환 수행하는 것을 의미한다. 함수에서 실행해야 하는 작업의 특성에 따라 일반적인 호출방식보다 재귀호출방식을 사용해 함수를 만들어 프로그램 크기를 줄이고 간단히 작성한다.

memoization

컴퓨터를 실행할 때 이전에 계산한 값을 메모리에 저장하여 매번 다시 계산하지 않도록 하여 전체적인 실행속도를 빠르게 하는 기술이다. DP의 핵심

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

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

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

DP

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]

fibo1은 recursive 방식이고, fibo2는 iterative 방식이다. memoization을 재귀적 구조에 사용하는 것보다 반복적 구조로 DP를 구현한 것이 성능 면에서 효율적이다. 재귀적 구조는 내부에 시스템 호출 스택을 사용하는 오버헤드가 발생하기 때문.

DFS(깊이 우선 탐색)

시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 탐색해 더 갈 곳이 없게 되면, 마지막 갈림길의 정점으로 돌아와서 다른 방향의 정점으로 탐색을 계속 반복하여 모든 정점을 순회하는 방법. 가장 마지막에 만난 갈림길의 정점으로 돌아가야 하므로 스택을 이용한다.

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

 

인접 리스트

아래의 Goal은 인접 리스트이다. 인접 리스트는 특정 지점마다 리스트를 부여하고, 그 안에 인접한 지점의 이름을 저장한다. 보통 지점이 1부터 시작하기 때문에 앞에 빈 리스트를 넣어준다.

V = 7+1 #(0번은 안 쓸 것. 편의를 위해서 0번 땅을 만들어주었다고 생각하기)
S = '1 2 1 3 2 4 2 5 4 6 5 6 6 7 3 7'
# Goal = [[], [2,3], [1,4,5], [1,7], [2,6], [2,6], [4,5,7], [3,6]]
S = list(map(int, S.split()))
Goal = [[] for _ in range(V)]
for idx in range(0,len(S),2):
    v1 = S[idx]
    v2 = S[idx+1]
    Goal[v1].append(v2)
    Goal[v2].append(v1)
print(Goal)

인접 리스트를 이용한 경로 짜기

인접 리스트는 경로가 중요할 때 사용한다. 만일 특정 경로의 맨 끝까지 탐색한 경우, 직전 갈림길까지 왔던 길을 되돌아가는데, 그 과정을 전부 스택에 기록한다.

G = [[], [2,3], [1,4,5], [1,7], [2,6], [2,6], [4,5,7], [3,6]]
V = 7+1
def dfs(v):
    ST = []
    visited = [False] * V
    ST.append(v)
    visited[v] = True
    print(v)
    while ST:
        for w in G[v]: #v와 연결되어있는 w들 찾기
            if not visited[w]:
                visited[w] = True
                print(w)
                ST.append(v)
                v = w
                break
        else:
            v = ST.pop()
dfs(1)

#순서가 중요할 때는 이러한 방식으로 짠다. 반드시 이렇게만 풀어야 하는 경우는 매우 적기 때문에 그냥 알아두고만 넘어가자.

 

인접 행렬

아래의 Goal은 인접 행렬이다. 인접 행렬은 (N+1)*(N+1) 행렬에 해당 지점과 인접한 지점이 있으면 1, 없으면 0으로 표시한다.  만일 G[1][2] = 1이라면 지점 1과 지점 2는 인접했다는 의미이다.

V = 7+1 #(0번은 안 쓰지만 편의를 위해 생성)
#Goal = [[0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 1, 1, 0, 0, 0, 0], [0, 1, 0, 0, 1, 1, 0, 0], [0, 1, 0, 0, 0, 0, 0, 1], [0, 0, 1, 0, 0, 0, 1, 0], [0, 0, 1, 0, 0, 0, 1, 0], [0, 0, 0, 0, 1, 1, 0, 1], [0, 0, 0, 1, 0, 0, 1, 0]]


S = '1 2 1 3 2 4 2 5 4 6 5 6 6 7 3 7'
S = list(map(int, S.split()))

G = [[0]*V for _ in range(V)]
for idx in range(0,len(S),2):
    v1 = S[idx]
    v2 = S[idx+1]
    G[v1][v2] = 1
    G[v2][v1] = 1
print(G)

인접 행렬을 이용한 경로 짜기

인접 행렬은 순서가 필요하지 않을 때 이용한다. 뒷걸음질을 쳐서 갈림길(선택지가 많은 곳)으로 돌아가는 과정을 하나하나 기재하지 않는다.

#행렬 이용
G = [
    [0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 1, 1, 0, 0, 0, 0],
    [0, 1, 0, 0, 1, 1, 0, 0],
    [0, 1, 0, 0, 0, 0, 0, 1],
    [0, 0, 1, 0, 0, 0, 1, 0],
    [0, 0, 1, 0, 0, 0, 1, 0],
    [0, 0, 0, 0, 1, 1, 0, 1],
    [0, 0, 0, 1, 0, 0, 1, 0]
]
V = 7+1
def dfs(v):
    ST = []
    visited = [False] * V
    ST.append(v)
    visited[v] = True

    while ST:
        v = ST.pop()
        print(v)
        for w in range(V):
            if G[v][w] == 1 and not visited[w]:
                ST.append(w)
                visited[w] = True

dfs(1)

+재귀를 이용한 방법

#재귀를 이용한 경우
G = [[], [2,3], [1,4,5], [1,7], [2,6], [2,6], [4,5,7], [3,6]]
V = 8
#재귀
visited = [False] * V
def dfsr(v):
    print(v)
    visited[v] = True
    for w in G[v]:
        if not visited[w]:
            dfsr(w)

dfsr(1)