1. 페리 수열의 길이 n번째 페리 수열은 분모가 n 이하인 0과 1 사이의 모든 기약분수를 오름차순으로 나열한 것이다. 기약분수가 무엇인가? $\frac{a}{b}$가 기약분수라면 a와 b가 서로소라는 뜻이다. 이때, 0과 1 사이에 존재하는 기약분수이므로 a < b이다. 그러므로 n번째 페리수열에 존재하는 기약분수들은 다음과 같이 만들수도 있다. "양 끝에는 $\frac{0}{1}, \frac{1}{1}$이 있고, 분모가 b = 2,3,4,5,..,n에 대하여 분자는 k보다 작으면서 서로소인 모든 정수 a에 대해 $\frac{a}{b}$를 나열한 것이다." 예를 들어, 5번째 페리 수열을 보자. 분모가 2이면 2와 서로소인 1에 대해 $\frac{1}{2}$ 분모가 3이면 3과 서로소인 1,2에 대해..
1. 방향 비순환 그래프(Directed acyclic graph) 사이클이 존재하지 않는 방향 그래프 정점 u에서 출발했을때, u로 돌아오는 방법이 없다. 다음과 같은 그래프는 방향 비순환 그래프(DAG)이다. 2. 한 정점에서 다른 정점까지 가장 긴 경로의 길이 정점 v에 대하여 DP[v]를 v에서 출발할때 도달할 수 있는 가장 긴 경로의 길이라고 정의한다면... 다음과 같이 v에서 c1,c2,c3,...로 갈 수 있을텐데, c1,c2,c3,...에서 출발하여 도달할 수 있는 가장 긴 경로의 길이 DP[c1],DP[c2],...가 이미 구해져있다면... DP[v] = max(wi + DP[ci])으로 구할 수 있을 것이다. 다이나믹 프로그래밍은 이미 해결한 작은 문제를 이용해서 더 큰 문제를 해결하는..
1. 문제 D - Erase Leaves (atcoder.jp) D - Erase Leaves AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 2. 풀이 리프 노드부터 차례대로 지울 수 있을때, 1번 노드를 지우기 위해서 최소로 지워야하는 노드의 개수는 몇개인가? 평소에 골드3정도 트리 DP 문제를 연습했더니.. 해법이 보이긴 하더라 리프 노드라는 것은 자식이 없는 노드인데, 목표로 하는 노드가 1번 노드니까, 1번 노드를 루트라고 생각한다면.. 다음과 같은 트리는 다음과 같이 바꿀 수 있는데, 이런 경우에 리프 노드부터..
1. 그래프와 트리 그래프(graph)란 정점들과 정점 둘을 잇는 간선들로 이루어진 집합 위는 9개의 정점(원)과 10개의 간선(실선)들로 이루어진 그래프이다. 각 원의 내부에 쓰여 있는 숫자는 편의상 정점에 매긴 번호를 의미한다. 간선(edge)은 항상 두 정점을 잇게 된다. 그래프의 간선에는 가중치가 있을 수 있다. 특별한 언급이 없다면 간선의 가중치는 1로 간주할 수 있다. 가중치가 존재한다면, 예를 들어 1-3 간선의 가중치가 3이라면 1번 정점에서 3번 정점으로 가기 위해선 길이 3인 간선을 지나야한다고 표현한다. 그래프의 간선에는 방향성이 있을 수 있다. 예를 들어 1번 정점과 3번 정점사이 놓인 1-3 간선의 경우 1 > 3 또는 3 > 1 방향성을 가지는 것이 가능하다. 방향성 간선을 갖고..
1. 문제 1750번: 서로소의 개수 (acmicpc.net) 1750번: 서로소의 개수 예제 1의 경우 가능한 경우의 수는 (2, 3), (4, 3), (2, 4, 3)이다. www.acmicpc.net 2. 풀이 수열에서 어떤 원소는 선택하고 어떤 원소는 선택하지 않아 만든 부분집합의 원소들의 최대공약수가 1이 되는 부분집합의 개수를 구하는 문제 안풀어보면 대단히 어렵다. dp[i][j]를 배열의 i번째 수까지 사용했을때, 최대공약수가 j가 되는 부분집합의 개수라고 정의 원소의 크기는 10만까지니까 최대공약수도 당연히 10만까지 가능할거고 여기서 중요한건 자기 자신만 사용하면 최대공약수는 자기 자신이다 초기화할때는 모든 i = 0,1,2,...,n-1에 대하여 dp[i][s[i]] = 1 이게 무슨말..
1. 문제 11660번: 구간 합 구하기 5 (acmicpc.net) 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 2. 풀이 좌상단이 (0,0)이고 우하단이 (x,y)인 직사각형내의 모든 원소 합을 dp[y][x]라고 정의한다. 예를 들어 다음 그림을 보면... dp[3][4]는?? dp[3][4] = 1+2+3+4+2+3+4+5+3+4+5+6을 뜻하게 된다. 어떻게 하면 이전에 구해놓은 합을 이용해서 쉽게 구할 수 있을까? 다음과 같이 x = 0 ~ n, y = ..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
