C++156 [Algorithm] 위상 정렬 - Topology Sort (파이썬, C++) 위상 정렬 - Topology Sort 위상 정렬은 순서가 정해져 있는 노드들을 차례대로 정렬할 때 사용할 수 있는 알고리즘이다. 더 개념적으로 정의하자면, 위상 정렬이란 "방향 그래프의 모든 노드를 방향성에 따라 정렬"하는 것이다. 위상 정렬에서 그래프는 방향 그래프이므로 각 방향에 대한 간선이 존재한다. 이때 어떤 노드가 다른 노드를 가리킬 때, 들어오는 간선의 개수를 "진입 차수"라 한다. 위상 정렬 알고리즘 ① 진입 차수가 0인 노드를 큐에 넣는다. ② 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다. ③ 새롭게 진입 차수가 0이 된 노드를 큐에 넣는다. ④ 큐가 빌 때까지 ②,③ 과정을 반복한다. 파이썬 소스 코드) C++ 소스 코드) 위상 정렬의 시간 복잡도 위상 정렬을 .. 2021. 3. 10. [백준] 1520번 - 내리막 길 (C++, 파이썬) 문제 및 풀이 문제) 백준 - 동적 계획법 (Dynamic Programming) - 내리막 길 -> www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 각 지점까지 이동할 수 있는 경로의 수를 저장한 2차원 리스트(dist)에 메모이제이션을 적용한다. dist 리스트의 초기값을 -1로 선언해 방문 여부를 판단한다. 각 지점까지 이동할 수 있는 경우의 수는 dfs를 이용하여 경로가 겹치는 지점에서 서로의 경로 수를 합친다. Python 소스 코드) C++ 소스 코드) Python .. 2021. 3. 9. [백준] 11051번 - 이항 계수 2 (C++ / 파이썬) 문제 및 풀이 문제) 백준 - 동적 계획법 (Dynamic programming) - 이항 계수 2 -> www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 주어지는 N과 K가 최대 1000이므로 기본 조합 공식으로 팩토리얼로 구한다면 시간 초과가 날 것이다. 따라서 우리는 동적 계획법을 이용하여 시간을 줄일 것이다. 고등학교 수학 시간에 조합 관련 개념에서 우리는 다음과 같은 수식을 배웠다. (기억이 안난다면, 지금 알아 놓도록 하자.) 이 식을 이용해 우리는 동적 계획법의 수열을 쉽게 새울 수 있다. 우리가 구할 값을 dp[n][k]라 했을 .. 2021. 2. 20. 이전 1 ··· 15 16 17 18 다음 반응형
