Go Gradually - Repository

위상 정렬이란, Directed Acyclic Graph(DAG)의 정점들을 각 정점이 자신의 자식 정점들보다 먼저 방문되도록 나열하는 것을 의미한다.방향 그래프(directed graph)는 간선을 한쪽 방향으로만 이동할 수 있는 그래프를 의미한다.또한 비순환 그래프(acyclic graph)는 순환(cycle)을 포함하지 않는 그래프를 의미한다.이는 하나 이상의 간선을 따라가서 출발한 정점으로 다시 돌아올 수 없는 구조를 말한다.이 두 정의를 합치면, 방향 비순환 그래프(directed acyclic graph, 줄여서 DAG)는 간선을 한쪽 방향으로만 이동할 수 있고 순환을 포함하지 않는 그래프이다.위상 정렬 (Topological Sort) - Course Schedule다음 문제를 풀어보자. C..

그래프에 간선을 추가하고 그래프의 두 정점이 연결되어 있는지 검사할 수 있게 해 주는 자료구조가 분리 집합(DSU, Union-Find) 이다.USACO.guide는 알고리즘의 원리와 정의보단 어떻게 이 정의를 떠올릴 수 있는지에 집중한다.알고리즘의 원리와 정의가 중요하지 않다는 뜻이 아니다.실제 Union-find의 원리와 관련된 내용은 다음 링크를 참고 바란다. CS Academy csacademy.com 구현(Implementation)import java.util.*;public class DisjointSets { int[] parents; int[] sizes; public DisjointSets(int size) { parents = new int[size]; ..

배낭(knapsack) 문제는 보통 제한된 용량의 컨테이너에 물건들의 부분집합을 넣되, 물건과 관련된 어떤 양을 세거나(카운트) 최적화하는 문제를 다룬다.거의 항상 각 물건은 양의 무게를 가지며, 우리가 선택한 물건들의 총 무게는 어떤 수로 주어지는 컨테이너의 용량을 초과해서는 안 된다. 배낭 유형 문제의 변형으로는 다음과 같은 것들이 있다.0/1 배낭 문제: 물건들의 부분집합을 골라 총 가치를 최대화하되, 총 무게가 컨테이너의 용량을 넘지 않도록 한다.가능한 총 무게 찾기: 컨테이너 용량을 넘지 않게 임의의 부분집합으로 만들 수 있는 모든 총 무게를 구한다.정확히 채우는 경우의 수 세기: 총 무게가 정확히 컨테이너 용량이 되도록 하는 물건의 순서열이 몇 개인지 센다(순서가 중요할 수도 있고 중요하지 않..

사실 '다이나믹'도 아니고, '프로그래밍'도 아닌 다이나믹 프로그래밍은 알고리즘 문제의 단골 요소이자 매우 효율적인 컴퓨터공학의 계산 효율화 방법이다.DP는 벨만-포드 알고리즘과 벨만 방정식, 강화학습의 토대를 마련한 미국의 응용수학자 리처드 E. 벨만이 발견했다. 이는 리액트의 렌더링 및 BFS, 캐싱, 비즈니스 로직 및 게임 엔진 최적화부터 심지어는 RL에까지 등장하고 있다. 이 DP에 대해, 지금부터 차근차근 알아보자.DP의 성질은 딱 두가지로 정리가 가능하다최적 부분구조중복 부분문제최적 부분구조최적 부분구조(Optimal Substructure)은 "경로에 관계없이" 다음 문제의 해답이 이전 부분문제의 최적화로 구해지는 구조를 의미한다.이를 다르게 표현하면, 뒷 문제의 정답을 구하는 과정이 앞 문..

모듈러 연산에서는 정수 그 자체로 계산하지 않고, 어떤 수를 m으로 나눈 나머지로 계산한다.이를 "모듈러 m을 취한다”라고 부른다. 예를 들어 m=23이라면, x=247 대신 x  mod  23=17을 사용한다.보통 m은 문제에서 주어지는 큰 소수(prime)이며, 가장 흔한 값은1000000007998 244 353=119⋅2^23+1이다.모듈러 산술은 내장 자료형의 범위를 넘는(오버플로) 큰 수를 다루지 않기 위해 사용되며, 다음 공식을 이용해 나머지를 취할 수 있다.Modular Exponentiation (모듈러 거듭제곱)거듭제곱 (Easy)https://cses.fi/problemset/task/1095 CSES - ExponentiationCSES - Exponentiation Time lim..

이와 같은 수학 문제는 코딩 테스트에는 잘 출제되지 않기 때문에 건너뛰는 사람들도 많지만,나는 시간복잡도 계산에 가장 강력한 인사이트를 부는 내용이 바로 이 수학 부분이라고 생각한다.그래서 이 수학 파트도 건너뛰지 않고 어느정도 설명을 진행하도록 하겠다.소인수분해 (Prime Factorization)양의 정수 a가 음이 아닌 정수 b의 약수(divisor) 또는 인수(factor)라고 불리는 것은, b가 a로 나누어떨어진다는 의미이다. 즉, 어떤 정수 k가 존재하여 b = ka가 되는 경우이다.정수 n > 1이 소수(prime)라는 것은 그 약수가 1과 n뿐일 때를 말한다.1보다 큰 정수 중 소수가 아닌 수는 합성수(composite)라고 한다. 모든 양의 정수는 유일한 소인수분해를 가진다. 즉, 소수..