230426 - 위상정렬, 동전DP

[robert-min]

줄 세우기 링크

• 대표적인 위상정렬 문제
• 위상정렬 : 위상 정렬(Topological sort)은 비순환 방향 그래프(DAG)에서 정점을 선형으로 정렬하는 것

import sys from collections import deque input = sys.stdin.readline

N, M = map(int, input().split())

graph = [[] for in range(N + 1)] inDegree = [0 for in range(N + 1)] # 진입차수

for i in range(M): a, b = map(int, input().split()) graph[a].append(b) inDegree[b] += 1

1. 진입차수가 0인 정점을 큐에 삽입

queue = deque() for i in range(1, N+ 1): if inDegree[i] == 0: queue.append(i)

answer = []

4. 이후 2~3의 과정을 반복

while queue: temp = queue.popleft() answer.append(temp) for i in graph[temp]:

2. 큐에서 원소를 꺼내 해당 원소와 연결된 간선을 모두 제거

    inDegree[i] -= 1
    # 3. 제거한 후에 진입차수가 0인 정점을 큐에 삽입
    if inDegree[i] == 0:
        queue.append(i)

print(*answer)

[robert-min]

동전 1 링크

• DP 문제
  • 전체 문제를 부분 문제로 나누어지는지 확인
  • 문제를 해결하는 점화식이 무엇인지
  • 부분 문제들을 해결하면서 얻는 결과 값을 메모이제이션 하는지
  • 부분 문제의 점화식은 부분 문제들 사이의 관계를 빠짐없이 고려하는지
• 풀이 참고

  
  # 이 동전을 적당히 사용해서, 그 가치의 합이 k원
  # 첫째 줄에 경우의 수를 출력한다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우

동전은 몇 개라도 사용

import sys input = sys.stdin.readline

n, k = map(int, input().split())

coins = [] for _ in range(n): coins.append(int(input()))

dp[i] -> i원 만들 때 가능한 경우의 수

dp = [0 for i in range(k+1)] dp[0] = 1

for coin in coins: for i in range(coin, k + 1):

coin원 동전으로 i원 만들기 -> i - coin원을 추가하는 것과 동일

    possible = dp[i - coin]
    dp[i] += possible

print(dp[k])