Beelog

https://programmers.co.kr/learn/courses/30/lessons/12978 코딩테스트 연습 - 배달 5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4 programmers.co.kr 이 문제는 처음에 dfs로 시도를 했으나... 생각보다 실패가 많았다... 그러던 중 플로이드 와샬(Floyd Warshall) 알고리즘이라는 것을 알게되었다. 최단 거리를 구하는 알고리즘으로 start에서 end까지 바로 가는 경로와 (start에서 K(지나가는 어떤 점)까지의 거리 + K부터 end까지 거리) 경로 중 더 짧은 거리를..

블로그 내에 작성된 알고리즘 풀이의 링크를 모았습니다. 😊 2021년 06월 2839 설탕 배달 10757 큰 수 A+B 1011 Fly me to the Alpha Centauri 1978 소수 찾기 2581 소수 11653 소인수분해 1929 소수 구하기 4948 베르트랑 공준 9020 골드바흐의 추측 2021년 05월 15650 N과 M (2) 15651 N과 M (3) 15652 N과 M (4) 15654 N과 M (5) 15655 N과 M (6) 15656 N과 M (7) 15657 N과 M (8) 15663 N과 M (9) 15664 N과 M (10) 15665 N과 M (11) 15666 N과 M (12) 1065 한수 1152 단어의 개수 2908 상수 5622 다이얼 2941 크로아티아 ..

https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 이 문제는 먼저 10,000 이하의 소수를 구한 뒤, 주어진 숫자를 소수의 합으로 구할 수 있는 경우 그 소수들을 출력하는 방식으로 해결할 수 있는 문제입니다. 만약 가능한 n의 골드바흐 파티션(주어진 수를 이루는 소수의 조합)이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다고 했기 때문에 소수를 구할 때 주어진 수 n을 반으로 나눈 뒤, 한쪽을 줄여가면서 맞..

https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 문제는 위와 같으면 이 문제는 다른 소수 문제들과 마찬가지로 먼저 에라토스테네스의 체를 통해 123456 * 2 수까지의 소수를 구한 다음, 0이 입력될 때까지 반복문을 돌면서 (주어진 숫자 + 1)부터 (주어진 숫자 * 2)까지 수 중 소수가 있는지 확인하여 소수인 경우 개수를 증가시키고 이 개수를 나중에 출력하는 방식으로 해결할 수 있습니다. 자바 코드는 다음과 같습니다. import ..

https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 문제는 위와 같으며 에라토스테네스의 체를 통해 소수를 판별한 boolean 타입 배열을 먼저 구한 뒤, 주어진 m과 n 사이의 소수를 찾아 출력하는 문제입니다. 자바 코드는 다음과 같습니다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Mai..