본문 바로가기

알고리즘

 (117)
[백준] 2749 피보나치 수 3 문제링크: www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제에서 엄청 큰 n에 대하여 피보나치 수를 구하라 한다. 이 때 100만으로 나눈 나머지의 값이다. 100만으로 나눈 나머지라는 문장을 본 순간 100만으로 나눈 나머지 값이 어떤 연속된 두 수는 이전에 연속된 두 수와 같을 것이라 생각했다. 코드에서 보면 init 함수가 그러하고 그 싸이클 크기를 cycleLen이라는 변수에 저장했다. 출력 해보니 15만인가 150만인가 하는 수가 나온다. 기억은 안난다. 또, 그 주기의 시작 값이 (0,1)이라는 것도 알았다. 어쨌든 100만..
[백준] 10830 행렬 제곱 문제링크: www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 이전에 풀었던 행렬 곱셈과 분할정복을 활용했다. 그런데, 임시 배열을 써서 복사행위를 해서 코드가 길어졌다. 다른 분의 코드를 보니 배열을 인자로 넘겨서 하더라. 나중에 다시 풀어보고 활용 해볼 것이다. import java.io.*; import java.util.*; public class Main { public static int [][]A; public static int N; public static l..
[백준] 2740 행렬 곱셈 링크: www.acmicpc.net/problem/2740 2740번: 행렬 곱셈 첫째 줄에 행렬 A의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 순서대로 주어진다. 그 다음 줄에는 행렬 B의 크기 M과 K가 주어진다. 이어서 M개의 줄에 행렬 B의 원소 K개 www.acmicpc.net 배준 단계별 분류 분할정복을 풀던 중 브론즈 문제가 나왔는데, 다음 문제도 행렬 곱셈을 활용하기 때문에 먼저 풀어봤다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedRe..
[백준] 11401 이항계수3 문제링크: www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 예전에 들어본 적 있어서 페르마의 소정리로 풀어야 한다는 것은 기억했지만 정리가 기억나지 않았다. 적어두고 반복해봐야겠다. import java.io.*; import java.util.*; public class Main { public static final long MOD = 1000000007; public static long fac[]; public static long power(long num,long cnt..
[백준] 1629 곱셈 문제링크: www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net power import java.io.*; import java.util.*; public class Main { public static long N,M,K; public static long power(long num,long cnt) { if(cnt==0) return 1; long temp = power(num,cnt/2); temp = temp*temp % K; if(cnt%2==1) { temp*=num % K; } return temp % K; } pu..
[백준] 1992 쿼드트리 문제링크: www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1≤N ≤64의 범위를 가진다. 두 번째 줄부터는 길이 N 의 문자열이 N 개 들어온다. 각 문자열은 0 또는 www.acmicpc.net 문제를 읽는 순간 분할정복임을 알았다. import java.io.*; import java.util.*; public class Main { public static int N; public static char [][]board; public static void divide_q(int start_y, int start_x, int square_size) { if(square_size..
[백준] 1541 잃어버린 괄호 문제링크: www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 마이너스가 하나라도 존재하는 부분부터 다 음수가 가능하다는 것이 자명하기 때문에 마이너스 기준으로 나누었다. split 방법을 몰라서 검색했고 배웠다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception{ BufferedReader br = ne..
[백준] 11054 가장 긴 바이토닉 부분 수열 문제링크 : www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 지난번 LIS로 백준의 전깃줄이라는 문제를 풀었다. LIS를 안다면 전깃줄 문제보다 쉽게 직관적으로 LIS로 풀면 된다는 것을 알 수 있다. 그래서 이 문제가 골드3인게 이해는 안가지만 어쨌든 풀이는 LIS로 해결했다. 정방향,역방향으로 증가하는 가장 긴 부분수열을 구해서 그 합이 최대인 값이 증가하다가 감소하는 가장 긴 부분수열의 길이일 것이다. import java.io.*; import java.util.*; p..

티스토리툴바