Stack

김윤빈·2021년 6월 8일

algorithm

목록 보기

1/23

Stack에 대해 알아보자!

1. Stack?

물건을 쌓아 올리는 듯한 자료 구조로, 스택에 저장된 자료는 선형 구조를 갖는다. 스택에서 자료를 삽입하거나 꺼낼 수 있고, 마지막에 삽입한 자료를 가장 먼저 꺼내는 방식으로 후입선출(LIFO, Last-In-First-Out) 이라고 부른다.

스택에서의 연산은 크게 삽입, 삭제, 공백확인, top확인 이 있으며 각각 append , pop , isEmpty , peek 등으로 구현한다.

2. 스택 응용 : function call

프로그램에서의 함수 호출과 복귀에 따른 수행 순서를 관리한다. 실제로 재귀함수를 호출할 경우 스택에 쌓이는 형태로 함수가 실행 된다.

2.1 피보나치 수열의 재귀

일반적으로 피보나치를 재귀함수로 구현하면 아래와 같다. 함수가 한번 실행 될때, 베이스케이스가 아니라면 2개씩의 함수를 새로 실행하게 되는데, 이중 중복값이 아주 많이 존재하고, N이 커질 수록 중복호출과 연산 횟수가 기하급수적으로 늘어나게 된다.

구현 방법

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

시간복잡도 : O( $2^n$ )
실행 모습

2.2 피보나치 메모이제이션

위와 같은 재귀 방식에서 불필요한 중복계산을 없애고, 동일한 n에 대해 1번만 함수를 호출하도록 하기 위해 메모이제이션을 사용한다.

메모이제이션(Memoization)

컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행 속도를 빠르게 하는 기술로, 동적 계획법의 핵심이 되는 기술이다.

구현방법

def fibo1(n):
	global memo
    if n >= 2 and len(memo) <= n:
    	memo.append(fibo1(n-1) + fibo1(n-2))
    return memo[n]

memo = [0, 1]

시간복잡도 : O(n)
실행 모습

함수의 호출이 발생할 때마다 스택에 쌓고, n이 2보다 작아진 경우 memo에 있는 값들을 리턴하고, 저장하면서 한번 구해진 값에 대해서는 함수를 호출하지 않고, memo에서 값을 꺼내 계산을 하여 중복을 줄인다.

2.3 피보나치 DP

동적 계획법(Dynamic Programming) 알고리즘은 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘이다. 동적계획 알고리즘은 입력 크기가 작은 부분 문제들을 모두 해결한 후에 그 해들을 이용하여 큰 부분문제를 해결해나가고, 최종적으로 원래 주어진 입력의 문제를 해결하는 알고리즘이다.

구현방법

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

	return f[n]

재귀와의 차이점

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

3. DFS(깊이 우선 탐색)

비선형 구조인 그래프를 빠짐없이 검색하는 방법(완전탐색). 깊이 우선 탐색과 너비 우선 탐색이 있다. 시작 정점의 한방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 막다른 길이면, 이전 갈림길로 돌아가 탐색을 진행한다. 마지막 갈림길로 돌아가는 행위를 하기 위해 후입 선출 구조인 스택을 사용한다.

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

V, E = map(int,input().split())
node = list(map(int,input().split()))

matrix = [[ 0 for _ in range(V+1)] for _ in range(V+1)]
for i in range(E):
    matrix[node[i * 2]][node[i * 2 + 1]] = 1
    matrix[node[i * 2 + 1]][node[i * 2]] = 1

stack = [1]
visited = [0] * (V+1)
visited[1] = 1

while stack :
    v = stack.pop()
    for i in range(1, V+1):
        if matrix[v][i] and not visited[i]:
            stack.append(i)
						visited[i] = 1

4. 계산기

중위 표현식으로 표기된 문자열이 주어질 때, 이를 후위 표현식으로 변환하고 연산을 수행한다.

알고리즘

< step 1. 중위표기식을 후위표기식으로 바꾸기 >
1. 입력받은 중위 표기식에서 토큰을 읽는다.
2. 토큰이 피연산자(숫자)이면 토큰을 출력한다.
3. 토큰이 연산자(괄호포함)일때, 토큰이 스택의 top에 저장되어 있는 연산자보다 우선순위가 높으면 스택에 push하고, 그렇지 않다면 스택의 top 우선순위가 토큰의 우선순위보다 작을 때까지 스택에서 pop을 한 후 토큰의 연산자를 push한다. 만약 스택이 있다면 push한다.
4. 토큰이 닫는괄호 ) 이면, 스택의 top에 여는괄호 ( 가 나올때까지 스택을 pop하고, 출력한다. 여는 괄호는 만나면 pop만 하고 출력은 하지않는다.
5. 중위 표기식에 더 읽을 것이 없다면 중지하고, 더 읽을 것이 있다면 1부터 다시 반복한다.
6. 스택에 남아있는 연산자를 모두 pop하여 출력한다.

< step 2. 후위표기식 연산 >

피연산자를 만나면 스택에 push한다.
연산자를 만나면 필요한 만큼의 피연산자를 스택에서 pop하여 연산하고, 연산결과를 다시 스택에 push한다.
수식이 끝나면 마지막으로 스택을 pop하여 출력한다.

코드구현

def Calculator(N, s):
    stack = []
    new_s = ''
    calculat = []
    Priority = {'+': 1, '*': 2, '(':0}

    # 1. 중위표현식 > 후위표현식
    for i in range(N):
        if 48 <= ord(s[i]) <= 57: # 숫자이면
            new_s += s[i]
        else: # 숫자가 아니고
            if not stack or s[i] == '(': # 스택이 비어있거나 여는 괄호이면
                stack.append(s[i]) # 스택에 넣자
            else: #스택이 비어있지 않으면
                if s[i] == ')': # 닫는 괄호가 나오면
                    while stack[-1] != '(': # 여는 괄호가 나올때까지 팝
                        new_s += stack.pop()
                    # 여는 괄호가 나와서 반복문이 종료되면, 여는 괄호도 팝
                    stack.pop()
                elif Priority[s[i]] > Priority[stack[-1]]: # 우선순위가 높으면
                    stack.append(s[i]) # 스택에 쌓자
                else: # 우선 순위가 낮으면
                    # 우선 순위가 높은게 나오거나, 스택이 비기 전까지
                    # 스택에 쌓인 연산자를 new_s에 붙여라
                    while stack and Priority[s[i]] <= Priority[stack[-1]]:
                        new_s += stack.pop()
                    stack.append(s[i]) # 위 반복문을 나온 후 스택에 값을 추가해라

    # 남아 있는거 털어라
    for i in range(len(stack)):
        new_s += stack.pop()

    # 2. 후위표현식 > 계산
    for i in range(len(new_s)):
        if 48 <= ord(new_s[i]) <= 57: # 숫자이면
            calculat.append(int(new_s[i]))
        elif new_s[i] == '+': # + 가 나오면 더하고
            b = calculat.pop()
            calculat[-1] += b #
        else: # * 이 나오면 곱해라
            b = calculat.pop()
            calculat[-1] *= b

    return calculat[0]

for tc in range(1, 11):
    N = int(input())
    s = input()
    print('#{} {}'.format(tc, Calculator(N, s)))

5. 백트래킹

백트래킹(Backtracking) 기법은 해를 찾는 도중에 막히면 (즉, 해가 아니면) 되돌아가서 다시 해를 찾아 가는 기법이다. 최적화(Optimization) 문제와 결정(Decision)문제를 해결할 수 있다.

결정문제는 문제의 조건을 만족하는 해가 존재하는지 여부를 Yes 또는 No 로 답하는 문제

미로찾기
n-Queen 문제
Map Coloring
부분 집합의 합 문제 등

백트래킹과 DFS와의 차이
- 어떤 노드에서 출발하는 경로가 해결책으로 이어질 것 같지 않으면 더 이상 그 경로를 따라가지 않음으로써 시도 횟수를 줄인다. (Prunning 가지치기) 즉, 모든 후보를 검사하지 않는다.
- 백트래킹 알고리즘을 적용하면 일반적으로 경우의 수가 줄어들지만, 최악의 경우는 DFS와 마찬가지로 지수함수 시간을 요한다 O( $n^2$ )
백트레킹 기법
- 어떤 노드의 유망성 을 점검한 후에 유망(promising)하지 않다고 결정되면 그 노드의 부모로 되돌아가(backtracking) 다음 자식 노드로 간다.
- 어떤 노드를 방문 하였을때 그 노드를 포함한 경로가 해답이 될 수 없으면 그 노드는 유망하지 않다고 하며, 반대로 해답의 가능성이 있으면 유망하다고 한다.
- 가지치기(pruning) : 유망하지 않은 노드가 포함되는 경로는 더 이상 고려하지 않는다.
백트레킹 구현 개요
- 상태 공간 트리의 깊이 우선 검색을 실시한다.
- 각 노드가 유망한지 점검한다.
- 만일 그 노드가 유망하지 않으면, 그 노드의 부모노드로 돌아가서(스택) 검색을 계속한다.

일반적인 백트레킹 sudo code

def checknode(v):
	if promising(v):
    		if there is a solution at v:
            		write the solution
               	else:
		    for u in each child of v:
			checknode(u)

5.1 미로찾기

그림과 같이 입구와 출구가 주어진 미로에서, 입구부터 출구까지의 경로를 찾는 문제이다.

5.2 N-Queens

n*n 이차원 행렬의 체스판에 n개의 퀸을 놓는 경우의 수. 단, 놓아진 퀸들끼리 서로의 공격 범위안에 들어가지 않으며, 서로가 서로를 잡을 수 없게 놓아야 한다.

상태공간 트리

깊이 우선 탐색 vs 백트레킹

DFS : 155노드
백트래킹 : 27노드

코드 구현

def Is_Cross(idx, c):
    # 이미 놓아진 퀸의 열 인덱스 순회
    for i in range(idx):
        # 대각선상에 놓여있다 : x좌표 차이 == y 좌표 차이
        # ex) (2,2)와 (4,4)는 같은 대각선에 놓여있다.
        # 이미 놓아진 퀸중에서 어느 하나라도 같은 대각선 상에 있으면 True
        if idx - i == abs(c - map_list[i]): return True

    # 어떤 대각선에도 걸리지 않았다면, False
    return False

def dfs(idx):
    global answer

    # idx는 퀸을 놓을 행 인덱스, 모든 행에 퀸이 놓아졌다면
    if idx == N:
        # 경우의 수 +1, 함수 호출 종료
        answer += 1
        return

    # 퀸을 놓을 수 있는 열 체크
    for i in range(N):
        # 이미 퀸이 놓아진 열이라면 넘어감
        if visit[i]: continue
        # 대각선이 겹친다면 넘어감
        if Is_Cross(idx, i): continue

        # 수직수평대각선 위치에 아무것도 걸리는 것 없고,
        # (idx, i)에 퀸을 놓을 수 있는 경우

        # 해당 열을 사용할 것이니 열사용 체크
        visit[i] = 1
        # 마찬가지로 map_list에 열 인덱스 기록
        map_list[idx] = i
        # 다음 행에 대해서도 같은 방식으로 후보군 조사를 위해 재귀호출
        dfs(idx + 1)
        # 재귀호출시 N개의 퀸을 놓아서 함수가 종료되었거나,
        # 앞서 놓아진 퀸들때문에 더 이상 퀸을 놓을 수 없어서(유망하지 않음) 함수 호출이 종료된 경우
        # 가장 최근에 놓은 퀸 제거
        visit[i] = 0

N = 8
# 각 행에 퀸이 놓아진 열 인덱스 기록
# ex) map_list[0] = 1 : 0행1열에 퀸이 놓아져있음
map_list = [0 for _ in range(N)]

# 인덱스에 해당하는 열에 퀸이 놓아져 있는지 체크 (0 or 1)
# ex) visit[2] = 1 : 2열에 퀸이 놓아짐
visit = [0 for _ in range(N)]

answer = 0
dfs(0)
print(answer)

5.3 부분집합 구하기

어떤 집합의 공집합과 자기자신을 포함한 모든 부분집합을 powerset 이라고 하며, 구하고자 하는 어떤 집합의 원소의 개수가 n개 일때 모든 부분집합의 개수는 $2^n$ 개이다.

구현방법
- n개의 원소가 들어있는 집합의 $2^n$ 개의 부분집합을 만들 때는, true 또는 false값을 가지는 항목들로 구성된 n개의 배열을 만드는 방법을 이용한다.
- 여기서 배열의 i번째 항목은 i번째의 원소가 부분집합의 값인지 아닌지를 나타낸다.
실행 모습
코드

def backtrack(a, k, input):
		global MAXCANDIDATES
		c = [0] * MAXCANDIDATES

		if k == input:
				process_solution(a, k) # 답이면 원하는 작업을 한다
		else:
				k += 1
				ncandidates = construct_candidates(a, k, input, c)
				for i in range(ncandidates):
						a[k] = c[i]
						backtrack(a, k, input)

def construct_candidates(a, k, input, c):
		c[0] = True
		c[1] = False
		return 2

MAXCANDIDATES = 100
NMAX = 100
a = [0] * NMAX
backtrack(a, 0, 3)

5.4 순열 구하기

기본적인 내용은 부분집합과 동일

코드

def backtrack(a, k, input):
	global MAXCANDIDATES
    	c = [0] * MAXCANDIDATES

	if k == input:
    	    for i in range(1, k+1):
            	print(a[i], end=" ")
		print()
	else:
	    k += 1
	    ncandidates = construct_candidates(a, k, input, c)
	    for i in range(ncandidates):
	    a[k] = c[i]
	    backtrack(a, k, input)

def construct_candidates(a, k, input, c):
	in_perm = [False] * NMAX

	for i in range(1, k):
            in_perm[a[i]] = True

	    ncandidates  = 0
	    for i in range(1, input + 1):
		if in_perm[i] == False:
           	    c[ncandidates] = i
		    ncandidates += 1
		    return ncandidates

6. 분할정복 알고리즘

분할(Divide) : 해결할 문제를 여러개의 작은 부분으로 나눈다.
정복(Conquer) : 나눈 작은 문제를 각각 해결한다.
통합(Combine) : (필요하다면) 해결된 해답을 모은다.

6.1 거듭제곱

기본적인 거듭제곱 구하는 방법

일반적으로 거듭제곱 계산은 $C^n = C * C * ... * C$ 로 시간복잡도는 O(n)이다.
```
def Power(Base, Exponent):
	if Base == 0: return 1
	result = 1
	for i in range(Exponent):
           result *= Base
	return result
```
분할정복 기반의 알고리즘 : O(logn)

def Power(Base, Exponent):
		if Exponent == 0 or Base == 0:
				return 1

		NewBase = Power(Base, Exponent//2)

		if Exponent % 2 == 0:
				return NewBase * NewBase 
		else:
				return (NewBase * NewBase) * Base

6.2 퀵정렬

주어진 배열을 두개로 분할하고 각각을 정렬한다.

합병 정렬과의 차이점
- 합병정렬은 단순히 두 부분으로 나누는 반면에, 퀵정렬은 분할할 때 기준 아이템(pivot item) 중심으로 작은 것은 왼쪽, 큰것은 오른쪽에 위치시킨다.
- 각 부분 정렬이 끝난 후, 합병 정렬은 합병 이란 후처리 작업이 필요하다, 퀵 정렬은 필요하지 않다.
코드

def quickSort(a, begin, end):
		if begin < end:
		    p = paetition(a, begin, end) # 구간을 나누고 p 기준 반반을 정렬
		    quickSort(a, begin, p-1)
		    quickSort(a, p+1, end)

def partition(a, begin, end):
    pivot = (bigin + end) // 2 # 가운데 위치한 값을 피봇으로 지정
    L = begin # 맨앞
    R = end # 맨뒤
    while L < R :
        while a[L] < a[pivot] and L < R: L += 1 # 왼쪽에 피봇보다 작은 값이 나오면 ok
	while a[R] >= a[pivot] and L < R: R += 1 # 오른쪽엔 피봇보다 큰값들이면 ok
				# 위에서 왼쪽인데, 피봇보다 작은 경우 while문 종료되고, 그때의 값이 a[L]
				# 오른쪽은 반대의 경우이고, a[R]
       	if L < R:
						# 왼쪽은 모두 피봇보다 작아서 L이 피봇까지 왔다면, pivot을 R로
	    if L == pivot: pivot = R 
		a[L], a[R] = a[R], a[L] # 피봇보다 작은건 왼쪽으로, 큰건 오른쪽으로 교환
    a[pivot], a[R] = a[R], a[pivot]
    return R

김윤빈

I'm yunbin

다음 포스트