Algorithm

✨ 알고리즘 분류 : 다이나믹 프로그래 https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 🪡 문제에서 요구하는 조건 정리 - 2*1 , 1*2, 2*2 타일을 2*n 크기의 직사각형으로 채운다 - 출력은 10,007을 나눈 나머지로 출력. 🧶 풀이과정 저번에 했던 것과 유사하다. 2024.04.11 - [Algorithm] - [056] 11726. 2xn 타일링 [056] 11726. 2xn 타일링 ✨ 알고리즘 분류 : 다이나믹프로그래밍 https://www.acmicpc...

✨ 알고리즘 분류 : 다이나믹프로그래밍 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 🪡 문제에서 요구하는 조건 정리 - 직사각형 타일 1x2 와 2x1 이 채우는 방법의 수를 구하기 - 출력할 때는 10,007을 나눈 나머지를 출력 🧶 풀이과정 DP는 진짜 나는 어려워서 생각을 많이 해야 했다. 보통 이런 것은 그려보면서 생각을 하는데, 여기에서 같은 점과 계산할 수 있는 부분을 추론하면서 진행을 하게 된다. 이 문제 같은 경우에는 전까지 만들어놓은 타일에서 언..

✨ 알고리즘 분류 : 다이나믹 프로그래밍 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 🪡 문제에서 요구하는 조건 정리 - 세가지의 연산을 활용하면서 사용 횟수의 최소를 구하기 🧶 풀이과정 dp 기본 문제인데 역시 내가 dp는 약해서 끙끙대는 과정이 좀 있었다. 연산은 다음과 같이 처리할 수 있다 1. dp 배열을 만든다 2. dp 배열을 순회하면서 n까지의 계산값을 저장한다 3. n의 계산값을 출력한다 이것을 기본으로 두고, 이 연산을 수행하기 위한 방법을 채택하자. 여기에서 계산값은 셋 중 하나이다 1. 3으로 나누기 2. 2로 나누기 3. 1을 빼기 ..

✨ 알고리즘 분류 : 수학, 정수론 https://www.acmicpc.net/problem/2004 2004번: 조합 0의 개수 첫째 줄에 정수 $n$, $m$ ($0 \le m \le n \le 2,000,000,000$, $n \ne 0$)이 들어온다. www.acmicpc.net 🪡 문제에서 요구하는 조건 정리 - nCm 에서 끝자리 0의 개수를 출력 - 최대값은 2,000,000,000 🧶 풀이과정 이것같은 경우는 전의 팩토리얼과 비슷하다 2024.04.08 - [Algorithm] - [053] 1676. 팩토리얼 0의 개수 [053] 1676. 팩토리얼 0의 개수 ✨ 알고리즘 분류 : 수학 https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!..

✨ 알고리즘 분류 : 수학 https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 🪡 문제에서 요구하는 조건 정리 - N! 에서 맨 뒤의 연속되는 0의 개수 구하기 🧶 풀이과정 내가 팩토리얼을 잘 몰라서, 찾아보면서 알게 되었는데 뒤에 있는 0의 갯수는 결국 5x2의 갯수였다. 그러니까, 10의 배수가 들어갈 때 제일 뒤에 0이 붙는 구조라고 보면 된다. 2는 5보다 많이 등장하기 때문에 (5가 들어가면 무조건 앞에는 2가 있기 때문에 5를 센다는 건 결국 2*5를 세는 것과 같다) 들어가는 5의 배수를 찾으면 된다. 예를 들어서 10이..

✨ 알고리즘 분류 : 수학 / 구현 https://www.acmicpc.net/problem/10872 10872번: 팩토리얼 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. www.acmicpc.net 🪡 문제에서 요구하는 조건 정리 - 문제에서 주어지는 n의 팩토리얼을 구하시오 🧶 풀이과정 팩토리얼은 n까지 오는 모든 수의 곱이다. 팩토리얼이 뭐지? 했다가 검색하는 순간 아 맞다! 했다. 아주 쉽게 for문을 이용해 계속해서 곱을 해주면 되고, 여기서 예외가 되는 1과 0을 따로 빼서 1이라고 정의하면 된다. 쉬운 구현 문제라 편하게 했다. 🏹 제출코드 package data_structure_part_01; import java.io.*; public clas..

✨ 알고리즘 분류 : 수학 / 정수론 / 소수 판정 / 에라토스테네스의 제 https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 🪡 문제에서 요구하는 조건 정리 - 짝수를 두 개의 소수 합으로 계산해 출력한다. - b - a가 가장 큰 것을 출력한다 (a가 제일 작은 것을 출력한다) - 소수 합에서의 각각 소수는 홀수이다 - n은 6 이상 1,000,000 이하의 자연수이다. 🧶 풀이과정 이건 이전에 소수 구하기에서 내가 따악..

✨ 알고리즘 분류 : 수학 / 정수론 / 소수 판정 / 에라토스네스의 https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 🪡 문제에서 요구하는 조건 정리 - n 이상이고 m 이하인 소수를 모두 구한다 🧶 풀이과정 우선, 소수를 구하는 방법은 저번 글에서 말했듯, 6이라고 한다면 제곱근이 6보다 큰 3*3 이전의 수, 2를 곱하는 식으로 진행한다. 계속해서 반복하는 것이므로 static을 만들어서 호출하는 방식을 사용했고, 판별하여 맞으면 수를 출력, 아니면 다음 수로 가는 형식으..

✨ 알고리즘 분류 : 수학 / 정수론 / 소수 판정 https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 🪡 문제에서 요구하는 조건 정리 - 주어진 개수 중에 소수의 갯수를 출력한다 - 소수는 1000 이하의 자연수이다 🧶 풀이과정 처음에 문제를 반대로 이해해서 틀렸다 ^^; 반대로 이해해서 수 중 제일 큰 것이 100인 줄 알고 재귀로 만들었는데 왜 틀렸지? 하고 문제를 다시 보니까 반대로 이해했더라. 소수를 찾는 방법은 다음과 같다. 1. 해당하는 수의 루트값까지 하나씩 수를 올리면서 나누어본다. + a, b일 경..