📌 DP

✏️ 종이붙이기(DP)

import sys; sys.stdin=open('input.txt','r')

def f(n):
    if n <= 1:
        return 1

    else:
        return f(n-2)*2+f(n-1)

T = int(input())
for tc in range(1, T+1):
    N = int(input())
    n = N//10
    ans = f(n)
    print(f'#{tc} {ans}')

해당 문제는 점화식을 워낙 많이 작성해보아서, 어려움이 없었지만, DP에 대해서 부족함을 많이 느끼고 있는 중이다. 일단 계획하던대로 IM, Advanced 및 A형 기출문제를 다 풀고, DP문제만 골라서 풀어보는 시간을 가져야할듯 싶다.

📌 Stack

✏️ 괄호검사

import sys; sys.stdin=open('input.txt','r')

def bracket_check(str):
    stack = []
    for i in str:
        if not stack and i in '({':
            stack.append(i)
        elif not stack and i in ')}':
            stack.append(i)

        elif stack and i in '({':
            stack.append(i)
        elif stack and i in ')}':
            if stack[-1] == '(' and i == ')':
                stack.pop()
            elif stack[-1] == '{' and i == '}':
                stack.pop()
            else:
                stack.append(i)

    if stack:
        return 0
    elif not stack:
        return 1

T = int(input())
for tc in range(1, T+1):
    str1 = list(input())
    ans = bracket_check(str1)
    print(f'#{tc} {ans}')

✏️ 반복문자 지우기

import sys; sys.stdin=open('input.txt','r')

T = int(input())
for tc in range(1, T+1):
    lst = list(input())
    # lst.sort()
    # print(lst)

    stack = []
    for i in lst:
        if stack and stack[-1] == i:
            a = stack.pop()
        elif not stack or stack[-1] != i:
            stack.append(i)

    print(f'#{tc} {len(stack)}')

stack의 습성을 충분히 고려하여 푼다면, 여러 조건 및 예외만 잘 생각한다면 쉽게 풀수있다고 생각한다.

📌 DFS

✏️ 그래프 경로

import sys; sys.stdin=open('input.txt','r')

def dfs(st, graph, visited):
    global en, ans
    if st == en:
        ans = 1
        return

    else:
        for i in graph[st]:
            if not visited[i]:
                visited[i] = 1
                dfs(i, graph, visited)

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

    for _ in range(e):
        a, b = map(int, input().split())
        graph[a].append(b)

    # 출발, 도착
    st, en = map(int, input().split())

    ans = 0
    dfs(st, graph, visited)

    print(f'#{tc} {ans}')

DFS를 어느정도 알고 풀어서 어렵지 않았다. 나는 재귀로 풀었는데, 스택으로 푸는 방법도 있음을 간과하지 말자. (그래도 지금은 재귀가 더 편한거 같다)