기록방

👉 문제링크 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 🔸 문제 분석 🔸 소수를 구한 후 오름차순으로 팰린드롬을 찾아 출력한다. 🔸 문제 풀이 🔸 N이 100만까지 입력되는데, 여유있게 1000만까지 소수를 구한다. 팰린드롬은 수를 char배열로 변환한 뒤 투포인터로 판단한다. 🔸 코드 🔸 import java.io.*; public class Main { public static void main(String[] args) throws IOException { Bu..

👉 문제링크 1456번: 거의 소수 어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다. www.acmicpc.net 🔸 문제 분석 🔸 어떤 소수의 N제곱 (N>2)의 수를 거의 소수라고 한다. A이상 B이하의 거의 소수의 개수를 출력한다. (1

👉 문제링크 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 🔸 문제 분석 🔸 피보나치 수열을 구현하는데 n이 1,000,000,000,000,000,000 으로 매우 큰 수가 주어진다. 🔸 문제 풀이 🔸 피보나치 수열을 구현하는데 반복문, 재귀, 동적 계획법을 사용할 수 있지만, 매우 큰 n에 대해서는 분할 정복을 이용한 거듭제곱을 이용해야한다. 행렬 곱셈을 이용한다. n번째 피보나치수는 (n/2-1)번째 피보나치 수[k1]와 (n/2)번째 피보나치 수[k2], (n/2+1)번째 피보나치 수[k3], (n/2+2)번째 피보나치 수[k4]로 나타낼 수 있다. EX ) 0, 1, 1, 2,..

👉 문제링크 1418번: K-세준수 첫째 줄에 N, 둘째 줄에 K가 주어진다. N은 100,000보다 작거나 같은 자연수이고, K는 100보다 작거나 같은 자연수이다. www.acmicpc.net 🔸 문제 분석 🔸 어떤 자연수의 소인수중 최대값이 K보다 크지 않으면 K-세준수이다. N이하의 자연수 중에 K-세준수의 개수를 구한다. 🔸 문제 풀이 🔸 1부터 N까지의 자연수들 각각 최대 소인수를 구하고, 그 값이 K를 넘는지 확인해야 한다. 소인수 인지 확인하기 위해 자연수를 N까지 키워간다. 현재 수가 소인수이면 그 수의 N보다 작은 배수들은 현재 수를 소인수 최대값으로 저장한다.(에라토스테네스의 체) 만약 현재 수가 이전에 배수로 소인수를 구했으면 그 수와 K를 비교하고, 이전에 구한 값이 없으면 현재 ..

👉 문제링크 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 🔸 문제 분석 🔸 N개의 서쪽 지점에서 M개의 오른쪽 지점으로 다리를 연결 하는 경우의 수를 구한다. 다리는 서로 겹칠 수 없다. 한 지점은 하나의 다리만 놓일 수 있다. 조합으로 접근할 수 있다. N