integer partition 문제 2 - m개 이하의 수만 사용해서 합이 k가 되도록 만드는 경우의 수 구하는 다이나믹 프로그래밍

1. 문제 15992번: 1, 2, 3 더하기 7 (acmicpc.net) 15992번: 1, 2, 3 더하기 7 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. 단, 사용한 수의 개수는 m개 이어야 한다. www.acmicpc.net 2. 풀이 저번엔 사용 개수의 제한 없이 합을 n으로 만드는 방법을 배웠다면.. https://deepdata.tistory.com/951 합이 k가 되는 경우의 수 구하는 다이나믹 프로그래밍 익히기(구성이 같은데 순서가 다르면 같은 1. 문제 9095번: 1, 2, 3 더하기 (acmicpc.net) 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 ..

• format_list_bulleted 다이나믹 프로그래밍
• · 2023. 8. 2.
• textsms

최단거리가 k의 배수가 되는 경로를 찾는 다익스트라 알고리즘

1. 문제 28131번: K-지폐 (acmicpc.net) 28131번: K-지폐 첫째 줄에 $N$, $M$, $K$가 주어진다. $(2\leq N\leq 10\,000; 1\leq M\leq \min\left(100\,000, N(N-1)\right); 1\leq K\leq 50)$ 둘째 줄에 $S$와 $T$가 공백으로 구분되어 주어진다. $(1\leq S,T\leq N;S\neq T)$ 셋째 줄부터 $M$개의 www.acmicpc.net 2. 풀이 문제 자체는 간단하다 s에서 t로 이동하는데 가중치의 합이 k의 배수가 되는 최단 경로를 찾는 문제 어떤 수가 k의 배수라는 것은, k로 나눈 나머지가 0이라는 사실을 이용해서 찾는다. D[i][j]를 s에서 출발해서 i 정점으로 가는 경로의 가중치 합을 ..

• format_list_bulleted 최단거리 알고리즘
• · 2023. 8. 2.
• textsms

3개 이상의 연속된 자연수의 합은 반드시 소수가 아니다

1. 연속된 자연수의 합 2개의 연속된 자연수를 합해보면.. 1+2 = 3 2+3 = 5 3+4 = 7 4+5 = 9 ... 소수가 나올 수 있는데 3개 이상의 연속된 자연수를 합해보면.. 1+2+3 = 6 2+3+4 = 9 3+4+5 = 12 4+5+6 = 15 ... 일단 소수가 보이질 않는다.. 이게 우연일까? 자연수 x에 대하여 n개의 연속된 자연수의 합은 다음과 같이 나타난다. $$S = x + (x+1) + (x+2) + ... + (x+n-1) = nx + \frac{(n-1)n}{2}$$ 여기서 n이 3이상의 자연수일때, S가 반드시 합성수임을 보이고자 한다. 1) 만약 n이 짝수라면 $n = 2k$ 여기서 k는 2이상의 자연수이다. $$S = 2kx + k(2k-1) = k(2x + 2k..

• format_list_bulleted 정수론
• · 2023. 8. 2.
• textsms

integer partition 문제1 - 합이 k가 되는 경우의 수 구하는 다이나믹 프로그래밍 익히기(구성이 같은데 순서가 다르면 같은 경우로 세는 방법, 다른 경우로 세는 방법)

1. 문제 9095번: 1, 2, 3 더하기 (acmicpc.net) 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 2. 풀이 정수 n을 1,2,3만 사용해서 만드는 방법의 수를 구하는 문제 1) 여기서 1,2,3은 중복해서 사용 가능하다 2) 동일하게 사용해도 순서가 다르면 다르다고 취급한다. 즉 1+1+2와 1+2+1은 다른 경우이다. dp[n]을 n을 만드는 방법의 수로 정의하고, 일단 n이 11보다 작기 때문에 dp의 크기를 11까지 잡아준다. n을 만들려면 어떻게 해야할까? 1,2,3만 사용할 수 있기 때문에 3가지 경우가 가능하다. 1) n-1에서 1을 더하면 n n-1을 만드는 방법의 수 dp..

• format_list_bulleted 다이나믹 프로그래밍
• · 2023. 7. 31.
• textsms

최소 스패닝 트리를 이용해서 그래프를 두 집합으로 분리하기(크루스칼 알고리즘 미세팁)

1. 문제 1647번: 도시 분할 계획 (acmicpc.net) 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 2. 풀이 입력 자체가 "임의의 두 집 사이에 경로가 항상 존재하는 입력이 주어진다"라고 되어있는데 맨 처음에는 모든 정점에 대하여 서로 연결된 하나의 그래프 집합이 주어지는데.. 여기서 몇개의 간선을 선택해서 두 집합으로 분리하라는 문제 이 때 선택된 간선의 가중치 합이 최소가 되도록 만들어야한다 최소 스패닝 트리 이전에 그냥 진짜 단순하게 생각해보면, 초기에..

• format_list_bulleted 최소 스패닝 트리
• · 2023. 7. 27.
• textsms

자기 것을 다시 갖지 않고 나눠주는 경우의 수 교란순열(완전순열) 배우기

1. 문제 1947번: 선물 전달 (acmicpc.net) 1947번: 선물 전달 경우의 수를 1,000,000,000으로 나눈 나머지를 첫째 줄에 출력한다. www.acmicpc.net 2. 풀이 PS를 위한 수학 - 교란 순열(완전순열) - 와 이게 에러가 뜨네 (mjstudio.net) PS를 위한 수학 - 교란 순열(완전순열) 교란 순열 ps.mjstudio.net 비가 오는 날에 n명의 사람이 자기의 우산을 쓰고 한 건물에 모여있다. 모두 동시에 집에 가려고 다시 우산을 쓰고 나가려는데, 자신의 우산을 사용하지 않는 경우의 수는? n개의 물건을 n명의 사람에게 다시 분배하는데, 자기 물건을 다시 갖지 않는 경우의 수를 교란순열(완전순열, derangement)라고 부른다 점화식이 유명한데 (고등..

• format_list_bulleted 조합론
• · 2023. 7. 18.
• textsms