[SW Intermediate] Stack1

Stack1

---

Stack 자료구조

✔ 스택 구현 시 고려 사항: 

리스트를 사용하여 스택을 구현하는 경우

- 장점: 구현이 용이

- 단점: 리스트의 크기를 변경하는 작업은 내부적으로 큰 오버헤드가 발생하는 작업으로 많은 시간을 소요

 

✔ 해결 방법

1) 리스트의 크기가 변동되지 않도록 배열처럼 크기를 미리 정해 놓고 사용하는 방법

2) 동적 연결리스트를 이용하여 저장소를 동적으로 할당하여 스택을 구현하는 방법

 - 장점: 구현이 용이

 - 단점: 리스트로 구현하는 것보다 구현이 복잡함 

---

괄호 검사

1) 괄호의 종류: 대괄호('[', ']'), 중괄호('{', '}'), 소괄호('(', ')')

2) 조건:

(1) 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같아야 한다.

(2) 같은 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 한다.

(3) 괄호 사이에는 포함관계만 존재한다.

 

3) 괄호를 조사하는 알고리즘:

(1) 문자열에 있는 괄호를 차례대로 조사

(2) 왼쪽 괄호를 만나면 스택에 삽입

(3) 오른 쪽 괄호를 만나면 스택에서 top 괄호를 삭제한 후(pop) 오른 쪽 괄호와 짝이 맞는지 확인

(3)-1 스택이 비어 있음 → 조건 1 또는 조건 2 위배

(3)-2 괄호의 짝이 맞지 않음 → 조건 3 위배

(3)-3 문자열 끝까지 조사한 후에도 스택에 괄호가 남아있음 → 조건 1 위배

---

함수 호출 관리

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

 

1) 가장 마지막에 호출 된 함수가 가장 먼저 실행을 완료하고 복귀하는 후입 선출 구조 이므로, 후입 선출 구조의 스택을 이용하여 수행 순서를 관리한다.

2) 함수의 호출이 발생하면 호출한 함수 수행에 필요한 지역변수, 매개변수 및 수행 후 복귀할 주소등의 정보를 스택 프레임에 저장하여 시스템 스택에 삽입한다.

3) 함수의 실행이 끝나면 시스템 스택의 top 원소(현재 실행 중인 스택 프레임)을 삭제(pop) 하면서 프레임에 저장되었던 복귀 주소를 확인하고 복귀한다.

4) 함수 호출과 복귀에 따라 이 과정을 반복하여 전체 프로그램 수행이 종료되면 시스템 스택은 공백 스택이 된다. 

---

Memoization

1) 정의:

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

- DP(동적 계획법)의 핵심이 되는 기술

 

2) Memoization 방법을 적용한 알고리즘

- 피보나치수를 구하는 알고리즘에서 fibo(n) 값을 계산하자마자 저장하면 실행시간을 줄일 수 있다.

- 만약 기존에 계산하여 저장된 값이 있을 경우에는 다시 계산하지 않겠다는 알고리즘이다.

 

# memo를 위한 리스트 생성
# memo[0]을 0으로 memo[1]은 1로 초기화

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

memo[0,1]

 

---

DP(동적 계획법)

1) 정의:

-  먼저 입력 크기가 작은 부분 문제들을 모두 해결한 후에 그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결

-  최종적으로 원래 주어진 입력의 문제를 해결

 

2) 피보나치 수를 구하는 함수에 DP 적용하기

- 문제를 부분 문제로 분할한다.

- 부분 문제로 나누는 일을 끝냈으면 가장 작은 부분 문제부터 해를 구한다.

- 그 결과는 테이블에 저장하고, 테이블에 저장된 부분 문제의 해를 이용하여 상위 문제의 해를 구한다.

 

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

 

3) DP 구현 방식

- Recursive 방식: fibo1()

재귀적 구조는 내부에 시스템 호출 스택을 사용하는 오버헤드가 발생할 수 있음

- Iterative 방식: fibo2()

Memoization을 재귀적 구조에 사용하는 것 보다 반복적 구조로 DP 를 구현하는 것이 성능면에서 보다 효율적이다.

 

---

DFS(깊이 우선 탐색)

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

- 깊이 우선 탐색(Depth First Search; DFS)

- 너비 우선 탐색(Breadth First Search; BFS)

 

1) DFS 방법

- 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색한다.

- 더이상 갈 곳이 없게 되면 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아온다.

- 다른 방향의 정점으로 탐색을 계속 반복하여 결국 모든 정점을 방문하여 순회한다.

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

 

2) DFS 알고리즘

(1) 시작 정점 V를 결정하여 방문

(2) 정점 V에 인접한 정점 중에서 방문하지 않은 정점 W 가 있으면, 정점 V를 Stack에 push 하고 정점 w를 방문 

    - W 를 V로 하여 다시 (1)을 반복

(3) 정점 V에 인접한 정점 중에서 방문하지 않은 정점이 없으면, 탐색의 방향을 바꾸기 위해 스택을 pop() 하여 받은 가장 마지막 방문 정점을 V 로 하여 다시 (1) 반복

* 스택이 빌 때 까지 반복

 

---

문1: 종이 붙이기

# dp 이용 문제 풀이

def paper_num(n):
    global memo

    if n == 1:
        return memo[0]
    elif n == 2:
        return memo[1]
    elif n>2 and len(memo) < n:
        memo.append(paper_num(n-1) + 2*paper_num(n-2))
    return memo[n-1]

T = int(input())
for test_case in range(1, T + 1):
    memo = [1,3]
    n = int(input())
    print(f'#{test_case} {paper_num(n//10)}')

 

문2: 괄호 검사

def check_match(str):
    dict_form = {']': '[', ')': '(', '}': '{'}
    stack = []

    for w in string:
        if w in list(dict_form.values()):
            stack.append(w)
            continue
        if w in list(dict_form.keys()):
            if not stack: # 스택이 빈 값인 경우(비교 값 존재x)
                return 0
            if dict_form[w] != stack.pop(): # 괄호 짝이 안맞는 경우
                return 0
    if stack:  # 문자열을 다 돌았음에도 stack에 괄호가 남아있는 경우(괄호 짝 안맞음)
        return 0
    return 1

T = int(input())
for test_case in range(1, T + 1):
    string = input()
    print(f'#{test_case} {check_match(string)}')

 

문3: 그래프 경로

# 정답 풀이..
# dfs 개념이 많이 부족하다! 정리하자..! 


def dfs(start, end):
    stack = []
    visited = [False]*(v+1)
    stack.append(start)

    while stack:
        start = stack.pop()
        visited[start] = True

        for i in range(1, v+1):
            if not visited[i] and graph[start][i]:
                stack.append(i)

    if visited[end]:
        return 1
    else:
        return 0


T = int(input())
for test_case in range(1, T + 1):
    v, e = map(int, input().split())
    graph = [[0 for _ in range(v+1)] for _ in range(v+1)]

    for _ in range(e):
        start, end = map(int, input().split())
        graph[start][end] = 1

    start, end = map(int, input().split())
    print(f'#{test_case} {dfs(start, end)}')

 

문4: 반복문자지우기

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    words = input()
    result = []

    for w in words:
        if result and w == result[-1]:
            result.pop()
        else:
            result.append(w)
    print(f'#{test_case} {len(result)}')