정수론 문제 - 나머지 연산을 꼭 기억하고 있어라

1. 문제 4375번: 1 (acmicpc.net) 4375번: 1 2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오. www.acmicpc.net 2. 풀이1 문제는 n의 배수인, 1로만 이루어진 수 중에서 자리수가 가장 작은 수를 찾는 문제 아주 단순하게는 n보다 큰 1로만 이루어진 수를 생성한 다음에.. 그 수가 n으로 나누어 떨어지는지 검사해보면 된다 n의 길이를 i라 한 다음에... 1로만 이루어진 길이 i인 수부터 시작해서.. n으로 나누어가지고 가장 먼저 나누어 떨어지는 수를 출력 from sys import stdin while 1: try: n = int(stdin.readline()) i = len..

• format_list_bulleted 정수론
• · 2023. 4. 24.
• textsms

라그랑주의 네 제곱수 정리를 이용한 알고리즘(다이나믹 프로그래밍, 브루트포스 연습)

1. 라그랑주의 네 제곱수 정리 모든 자연수 n은 많아야 음이 아닌 4개의 정수의 제곱수 합으로 표현할 수 있다. $$n = a^{2} + b^{2} + c^{2} + d^{2}$$ 을 만족하는 0 이상의 정수 a,b,c,d가 존재한다. 증명은 매우 까다롭다.. 너무 길어서 따라하기도 힘들다.. https://jjycjnmath.tistory.com/295 [퍼온글] 라그랑주의 네제곱수 정리(Four Square Theorem)와 그 증명 ※ 출처 - http://kevin0960.tistory.com/ 디오판토스의 저서 '산학'에는 '모든 양의 정수는 네 제곱수의 합으로 표현될 수 있다.' 라는 내용이 담겨 있다. 예를 들어, \[ \begin{aligned} 3 &= 1^2 + 1^2 + 1^2 + 0..

• format_list_bulleted 정수론
• · 2023. 4. 23.
• textsms

최대 비용을 가지는 신장 트리를 만드는 방법?

1. 문제 7044번: Bad Cowtractors (acmicpc.net) 7044번: Bad Cowtractors Bessie has been hired to build a cheap internet network among Farmer John's N (2

• format_list_bulleted 최소 스패닝 트리
• · 2023. 4. 20.
• textsms

최소 신장 트리를 구하는 프림 알고리즘, 크루스칼 알고리즘 재활하기1

1. 문제 16398번: 행성 연결 (acmicpc.net) 16398번: 행성 연결 홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다. 두 행성 간에 플로우를 설치하면 제국의 함 www.acmicpc.net 2. 풀이 최소 신장 트리의 비용을 구하는 알고리즘은 기본이 프림 알고리즘이랑 크루스칼 알고리즘 크루스칼 알고리즘이 간단해서 기억이 잘 난다.. 1) (가중치, 간선) 형태로 edges에 넣어 가중치 기준으로 오름차순 정렬하고 2) 가중치가 적은 간선부터 순회하여 정점 a와 정점 b가 서로 parent가 다르다면, union 시키고 해당 간선을 선택하고 간선의 가중치를 더해간다. 3) parent가 같다..

• format_list_bulleted 최소 스패닝 트리
• · 2023. 4. 18.
• textsms

다익스트라 알고리즘 조금 어려운 문제로 오랜만에 재활하기1

1. 문제 20007번: 떡 돌리기 (acmicpc.net) 20007번: 떡 돌리기 첫째줄에 N, M, X, Y가 공백으로 구분되어 입력된다. (2 ≤ N ≤ 1,000, 1 ≤ M ≤ 100,000, 1 ≤ X ≤ 10,000,000, 0 ≤ Y < N) 두번째 줄부터 M+1번째 줄까지 A와 B 그리고 A집과 B집 사이의 도로의 길이 C가 주 www.acmicpc.net 2. 풀이 다익스트라는 기본 구현 그대로.. 하면 되는데.. 문제 조건을 올바르게 생각해야한다 1) "하루에 x보다 먼 거리를 걷지 않고, 거리가 가까운 집부터 방문한다" 거리가 가까운 집부터 방문한다고 하니까, 그래서 다익스트라로 얻은 최단거리 배열을 오름차순으로 정렬해줘서, 작은 거리부터 방문해줘야한다. 2) "잠은 꼭 본인 집에..

• format_list_bulleted 최단거리 알고리즘
• · 2023. 4. 16.
• textsms

다익스트라 알고리즘 응용 - 다른 정점에서 목적지로 되돌아오는 최단거리 구하는 방법

1. 문제 1238번: 파티 (acmicpc.net) 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 2. 풀이 이 문제의 핵심은 x번 마을에서 다시 i = 1,2,...번 마을로 되돌아오는 최단 거리가 필요하다는 점이다. 다익스트라 알고리즘은 출발 정점 start에서 다른 정점 1,2,...,n번 까지 가는 최단 경로를 구해주는 알고리즘이지 1,2,...,n번 각각의 정점에서 start로 되돌아오는 최단 경로를 구해주는 알고리즘은 아니다 이걸 할려면 다익스트라를 n번 해야하는데..

• format_list_bulleted 최단거리 알고리즘
• · 2023. 4. 16.
• textsms