[SWEA] [파이썬 SW 문제해결 기초] 3. Stack1

[Stack 자료구조]

Stack: 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조 (선형구조) => 활용도 多
- 후입선출(LIFO)인건 기본 지식

- 자료를 선형으로 저장할 저장소 필요 => 리스트로 구현
- 마지막 삽입된 원소의 위치: top
- 삽입 연산: push / 삭제 연산: pop / 공백 확인 연산: isEmpty / top에 있는 원소 반환: peek

# push 알고리즘
def push(item):
  # 파이썬 리스트: 크기 제한 없이 데이터 삽입 가능 => overflow 고려할 필요 X
  # append() 함수로 리스트 마지막에 요소 넣을 수 있음 => top 변수 사용할 필요 X
  s.append(item)	


# pop 알고리즘
def pop():
  if len(s) == 0:	# 리스트의 크기를 len() 함수를 통해 알 수 있음 => top 변수 사용할 필요 X
    # underflow
    return
  else:
    return s.pop(-1)

※ 리스트 사용해서 스택 구현
: 구현이 용이하지만, 리스트 크기를 변경하는 작업은 내부적으로 큰 overhead가 발생함

※ 해결 방법
1) 리스트의 크기가 변동되지 않도록 배열처럼 크기를 미리 정해놓고 사용
2) 동적 연결리스트를 이용하여 저장소를 동적으로 할당하여 스택 구

 

[Stack 응용]

1. 괄호 검사
- 여는 괄호이면 스택에 저장 / 닫는 괄호이면 저장한 여는 괄호를 pop으로 꺼내서 비교
- 수식이 끝났는데 괄호 남아있으면 올바르지 못한 사용

2. 함수 호출
- 프로그램에서의 함수 호출과 복귀에 따른 수행 순서 관리
- 후입선출 구조 이용

3. 재귀 호출
- 프로그램의 크기를 줄이고 간단하게 작성 가능, but 디버깅 어렵고 잘못 작성하면 시간 오래 걸림
- ex. factorial

 

[Memoization]

재귀 호출을 작성할 수 있는 예시 하나 더 => 피보나치 수열

# 피보나치 수열 알고리즘
# 엄청난 중복 호출이 존재한다는 단점
def fibo(n):
  if n < 2:
    return n
  else:
    return fibo(n-1) + fibo(n-2)

중복 호출을 없앨 수 있는 기법 = Memoization(메모이제이션)
- 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 함 => 실행 속도 빨라짐
- DP(동적계획법)의 핵심이 되는 기술

# Memoization 적용 fibo 함수

# memo를 위한 리스트를 작성하고,
# memo[0]을 0으로 memo[1]은 1로 초기화.

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]

 

[DP(동적 계획법, Dynamic Programming)]

- 최적화 문제를 해결하는 알고리즘
- 입력 크기가 작은 부분 문제들을 모두 해결한 후에, 그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결
- 최종적으로 원래 주어진 입력의 문제를 해결

ex) 피보나치 수열에 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. 결과를 테이블에 저장하고, 이를 이용하여 상위 문제 답 구하기
'''

# 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]

※ DP 구현 방식
1) recursive 방식: fibo1() => overhead 발생할 수 있음
2) iterative 방식: fibo2() => 더 효율적인 성능

 

★[DFS(깊이 우선 탐색)] → stack 이용

1) 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색
2) 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아옴
3) 다른 방향의 정점으로 탐색을 계속 반복하여, 결국 모든 정점을 방문하여 순회

'''
DFS 알고리즘
1) 시작 정점 v를 결정하여 방문
2) 정점 v에 인접한 정점 중에서
  - 방문하지 않은 정점 w가 있으면: 정점 v를 스택에 push + 정점 w 방문 
       => w를 v로 하여 다시 1) 반복
  - 방문하지 않은 정점이 없으면: 스택을 pop하여 받은 가장 마지막 방문 정점을 v로 하여 다시 1) 반복
'''


visited[], stack[] 초기화		# stack[]: 경로 역추적에 필요, visited[]: 정점 방문 여부 기록
DFS(v)
  v 방문:
  visited[v] ← true;	# 시작 정점을 visited[v] 표시
  do {
    if (v의 인접 정점 중 방문 안 한 w 찾기)
      push;
    while(w) {
      w 방문;
      visited[w] ← true;
      push(w);
      v ← w;
      v의 인접 정점 중 방문 안 한 w 찾기
    }
    v ← pop(stack);
  } while(v)
end DFS()

근데 DFS는 듣다가 알고리즘 설명하는 부분에서 끔뻑 끔뻑 졸아버려서, 이 부분은 다시 듣는 게 좋을 것 같은데... 근데 또 무슨 말인지는 다 알 듯하고. 일단 조금만 자고 일어나서 문제를 풀어보고 생각해보자..

 

---

 

4869. 어린이 알고리즘 교실의 선생님은 경우의 수 놀이를 위해, 그림처럼 가로x세로 길이가 10x20, 20x20인 직사각형 종이를 잔뜩 준비했다. 그리고 교실 바닥에 20xN 크기의 직사각형을 테이프로 표시하고, 이 안에 준비한 종이를 빈틈없이 붙이는 방법을 찾아보려고 한다. N이 30인 경우 다음 그림처럼 종이를 붙일 수 있다. 10의 배수인 N이 주어졌을 때, 종이를 붙이는 모든 경우를 찾으려면 테이프로 만든 표시한 영역을 몇 개나 만들어야 되는지 계산하는 프로그램을 만드시오. 직사각형 종이가 모자라는 경우는 없다.

T = int(input())

for test_case in range(1, T+1):
    N = int(input())//10
    
    dp = [0] * 51
    dp[0] = 1
    dp[1] = 1
    
    for i in range(2, N+1):
        dp[i] = dp[i-1] + 2*dp[i-2]

    print(f"#{test_case} {dp[N]}")

이건 점화식을 생각해내는 게 어려웠다. 혼자서 어찌저찌 하다가 T(n) = T(n-1) + 2*T(n-2)인 것까지는 알았는데 그 이후로 이해가 잘 안 가서 여러 가지 찾아다녔다.

그렇게 나름대로 이해한 내용 작성하기:
1. 너비 10, 높이 20인 면적 채우기 => 20*10 종이 밖에 안됨 => T(n-10)
2. 너비 20, 높이 20인 면적 채우기 => 20*10 종이 2개 가로로 붙이기 or 20*20 종이 사용 가능 => T(n-20) * 2
3. 그런데 내가 입력을 'int(input())//10'으로 입력했으니까 => T(n) = T(n-1) + 2*T(n-2)

 

4866. 주어진 입력에서 괄호 {}, ()가 제대로 짝을 이뤘는지 검사하는 프로그램을 만드시오. 예를 들어 {( )}는 제대로 된 짝이지만, {( })는 제대로 된 짝이 아니다. 입력은 한 줄의 파이썬 코드일수도 있고, 괄호만 주어질 수도 있다. 정상적으로 짝을 이룬 경우 1, 그렇지 않으면 0을 출력한다. print(‘{‘) 같은 경우는 입력으로 주어지지 않으므로 고려하지 않아도 된다.

def check_parenthesis(line):
    stack = []
    res = 0
    
    for i in line:
        if i == '(' or i == '{':
            stack.append(i)
        elif i == ')' or i == '}':
            stack.pop()
    
    if len(stack) == 0:
        res = 1
        
    return res


T = int(input())

for test_case in range(1, T+1):
    N = input()
    line = [ n for n in N ]
        
    res = check_parenthesis(line)
    print(f"#{test_case} {res}")

보여주는 테스트 케이스 3개는 정상적으로 작동을 하지만, 막상 제출하니 런타임 에러가 뜬다. 뭐가 문제인지 보니까 stack 길이가 0일 때를 고려하지도 않았고 소괄호랑 중괄호 구분을 안해줘서 다음과 같이 바꿔줌.

def push(stack, item):
    stack.append(item)

def pop(stack):
    if len(stack) == 0:
        return
    return stack.pop(-1)

def check_parenthesis(line):
    stack = []
    res = 1
    
    for i in line:
        if i == '(' or i == '{':
            push(stack, i)
        elif i == ')' or i == '}':
            if not stack:       # 스택에 여는 괄호가 없으면
                res = 0         # 닫는 괄호랑 짝이 안맞으므로 탈출
                break
            Bracket = pop(stack)
            if i == ')' and Bracket != '(':     # 짝이 안맞으면 res = 0
                res = 0
            elif i == '}' and Bracket != '{':
                res = 0
    
    if stack:	# stack에 괄호 남아있으면 짝 안 맞는 것
        res = 0

    return res


T = int(input())

for test_case in range(1, T+1):
    N = input()
    line = [ n for n in N ]
        
    res = check_parenthesis(line)
    print(f"#{test_case} {res}")

여러 번의 시행 착오를 거쳐... 그래도 아이디어를 생각해내는 것 자체는 어렵지 않았다. 어떤 논리적인 부분에서 오류가 난 건지를 잘 못 찾은 것 뿐...

 

4871. V개 이내의 노드를 E개의 간선으로 연결한 방향성 그래프에 대한 정보가 주어질 때, 특정한 두 개의 노드에 경로가 존재하는지 확인하는 프로그램을 만드시오. 두 개의 노드에 대해 경로가 있으면 1, 없으면 0을 출력한다. 노드번호는 1번부터 존재하며, V개의 노드 중에는 간선으로 연결되지 않은 경우도 있을 수 있다.

def dfs(start, end):
    global answer
    stack = []
    visited = [False] * (V+1)
    stack.append(start)     # 일단 stack에 시작점 추가
    
    while stack:
        now = stack.pop()   # 현재 살펴볼 노드
        visited[now] = True # 방문했다고 표시
        
        for i in range(1, V+1):     # 전체 노드에 대해서
            if not visited[i] and arr[now][i]:  # 전체 노드 중 i 노드를 방문하지 않았고, now와 연결되어 있을 때
                stack.append(i)     # 살펴볼 노드로 추가
    
    if visited[end]:
        answer = 1
    else:
        answer = 0    

T = int(input())

for test_case in range(1, T+1):
    V, E = map(int, input().split())    # V: 노드 개수, E: 간선 개수
    arr = [[False] * (V+1) for _ in range(V+1)]
    
    for _ in range(E):
        i, j = map(int, input().split())
        arr[i][j] = True
    
    S, G = map(int, input().split())      # S: 시작 노드, G: 도착 노드
    
    answer = 0
    dfs(S, G)
    
    print(f"#{test_case} {answer}")

 

막상 시험 끝나고 다시 보니까 쉬웠다. 뭐지?

 

4873. 문자열 s에서 반복된 문자를 지우려고 한다. 지워진 부분은 다시 앞뒤를 연결하는데, 만약 연결에 의해 또 반복문자가 생기면 이부분을 다시 지운다. 반복문자를 지운 후 남은 문자열의 길이를 출력 하시오. 남은 문자열이 없으면 0을 출력한다.

T = int(input())

for test_case in range(1, T+1):
    strings = input()
    stack = []
    
    for s in strings:
        if len(stack) != 0:
            if s==stack[-1]:
                stack.pop()
            else:
                stack.append(s)
        elif len(stack) == 0:
            stack.append(s)
    
    res = 0
    if stack:
        res = len(stack)
        
    print(f"#{test_case} {res}")

이 문제는 정말 쉬웠다. 처음에 반복된 문자를 지우고 연결시킨 후에, 또 생기면 지운다길래 재귀인 줄 알았다. 근데 반복된 문자를 지우는 걸 보니까 최대 2개까지였어서, 괄호 검사 문제랑 비슷한 유형이겠거니 했다.

나의 풀이. 적을 때는 되게 생각이 원활하게 이뤄져서 뭔가 논리적으로 적은 줄 알았는데, 지금 보니 그냥 결과물 밖에 없군.