본문 바로가기

알고리즘 풀이56

[BOJ] 1676. 팩토리얼 0의 개수 - JAVA 🔗 문제 https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 🧩 풀이 및 코드 문제 유형 : 수학, 임의 정밀도 / 큰 수 연산 풀이 일단 뒤에 0이 붙는다는 건 2 x 5 가 곱해져 있을 떄다. 즉, 소인수분해를 해서 2 x 5 쌍의 갯수만큼 뒤에 0이 붙는다는 의미이다. 예를 들어, 30은 30 = 2×3×5 로 2와 5의 쌍이 1 개 이므로 0이 1개 붙는다. 조금 더 큰 수로 예를 들면 231400 의 경우 2와 5의 쌍이 2개 이므로 0이 2개가 붙는다. (231400) 팩토리얼과 소인수분해를 쭉 나열해 보면 다음과 같다. .. 2023. 1. 27.
[BOJ] 2981. 검문 - JAVA 🔗 문제 https://www.acmicpc.net/problem/2981 2981번: 검문 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간 www.acmicpc.net 🧩 풀이 및 코드 문제 유형 : 수학, 정수론, 유클리드호제법 헤맸던 문제다.. 풀이 방법을 보면 어떻게 저런 생각을 해내는지 신기하다. 문제에 나온 임의의 정수를 나타내면 다음과 같다. (M : 나눈수, r : 나머지) A1 = M * a1 + r1 A2 = M * a2 + r2 여기서 찾아내야 하는게 가능한 모든 M 이 되고, 나머지가 같기 때문에 r1 과 r2 가 같다. 따라서 여기서 A1 과 A2.. 2023. 1. 24.
[BOJ] 3036. 링 - JAVA 🔗 문제 https://www.acmicpc.net/problem/3036 3036번: 링 출력은 총 N-1줄을 해야 한다. 첫 번째 링을 제외한 각각의 링에 대해서, 첫 번째 링을 한 바퀴 돌리면 그 링은 몇 바퀴 도는지 기약 분수 형태 A/B로 출력한다. www.acmicpc.net 🧩 풀이 및 코드 문제 유형 : 정수론, 유클리드 호제법 유클리드 호제법 유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하.. 2023. 1. 20.
[BOJ] 1004. 어린왕자 - JAVA 🔗 문제 https://www.acmicpc.net/problem/1004 1004번: 어린 왕자 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 첫째 줄에 출발점 (x1, y1)과 도착점 (x2, y2)이 주어진다. 두 번째 줄에는 행성계의 개수 n이 주 www.acmicpc.net 🧩 풀이 및 코드 문제 유형 : 수학, 기하학 그림에 겁먹을 것 없이 풀이과정은 은근 단순했다. 진입/이탈의 최소 횟수를 구하는 것이기 때문에 출발점과 도착점이 원 밖에 있다면, 진입/이탈 없이 돌아서 가면 된다. 출발점과 도착점이 둘 다 원 내부에 있다면 진입/이탈이 없기 때문에 횟수로 치지 않는다. 즉, 출발점 또는 도착점 중 하나가 원 내부에 있다면 무조건 진입/이탈을.. 2023. 1. 19.
[BOJ] 2448. 별 찍기 - 11 - JAVA 🔗 문제 https://www.acmicpc.net/problem/2448 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net 🧩 풀이 및 코드 문제 유형 : 재귀 재귀 연습 많이 해야 겠다... k = 0 ( 즉, N = 3) 일 떄는 기본 블록 * * * ***** 규칙을 찾으면 크게 2줄로 구분된다. 첫 번째 줄은 중앙에 한 개의 블록, 두 번째 줄은 빈칸을 사이에 둔 두 개의 블록 * * * ***** * * * * * * ***** ***** 두 번째 줄은 블록을 한 개 삽입하고, 빈칸 삽입하고, 블록 한 개 삽입 첫 번쨰 줄은 블록을 중앙에 놓기 위해 블.. 2022. 12. 16.
[BOJ] 1976. 여행 가자 - JAVA 🔗 문제 https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 🧩 풀이 및 코드 문제 유형 : 자료 구조, 그래프 이론, 그래프 탐색, 분리 집합 내가 푼 방법은 Floyd 를 사용한 것이었는데, 출발지와 도착지가 같다면 여행할 수 있다는 것을 생각해내지 못해서 틀렸다. 검색을 하다가 Floyd는 시간 복잡도가 O(N^3) 이고 대부분 Union-Find 를 사용해서 푼 것 같아 2가지 방법으로 풀었다. Floyd (메모리, 시간, 코드 길이 순서).. 2022. 12. 15.

티스토리툴바