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

우선순위가 2개 이상인 다익스트라 알고리즘 연습

1. 문제1 16167번: A Great Way (acmicpc.net) 16167번: A Great Way 첫 번째 줄에 거점의 수 N과 경로의 개수 R이 주어진다. (2 ≤ N ≤ 100, 1 ≤ R ≤ 200) 모든 거점에는 1부터 N까지 번호가 매겨져 있으며 중앙대학교는 1번, 숭실대학교는 N번이다. 두 번째 줄부터는 R www.acmicpc.net 2. 풀이 다익스트라 알고리즘으로 최단거리만을 요구하는 문제가 기본문제고, 최단거리면서, 그러한 거리가 여러개인 경우 거쳐가는 노드가 최소가 되는 경로를 찾으라고 한다면? 접근 방법은 distance 배열 설정을 조금만 바꿔주면 된다 distance[v]를 출발점에서 v까지 가는데 가는 [비용, 거친 노드 수]로 정의해주자 "비용이 먼저 최소가 되면서..

• format_list_bulleted 최단거리 알고리즘
• · 2023. 7. 18.
• textsms

다익스트라를 응용해서 minimum bottleneck path 문제 기본 배우기

1. 문제 23286번: 허들 넘기 (acmicpc.net) 23286번: 허들 넘기 첫째 줄에 세 정수 N, M, T가 주어진다. 다음 M개의 줄에 그래프 간선의 정보 u, v, h가 주어지고, u에서 v로 가는 간선이 있고, 높이가 h인 허들이 간선 중간에 놓여 있다는 의미이다. 마지막 T개의 www.acmicpc.net 2. 풀이 출발 정점에서 도착 정점으로 가는 길에 가중치가 가장 큰 간선의 가중치가 최소가 되는 경로를 찾는 문제 경로에서 가중치가 가장 큰 간선을 bottleneck path라고 부른다 이 bottleneck path의 가중치를 최소로 만드는 문제가 minimum bottleneck path problem 여러가지 방법이 있는것 같기는 한데.. 가장 기본은 다익스트라 알고리즘을 살..

• format_list_bulleted 최단거리 알고리즘
• · 2023. 7. 15.
• textsms