본문 바로가기

알고리즘/백준

 (51)
[백준] 11286 절대값 힙 문제링크: www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 큐 두 개를 활용해서 해결했다. 코드가 긴 것 같아서 다른 사람의 풀이를 보니 우선순위 큐 하나로 담길 정보에 절대값, 원본값 두개를 같이 담아서 절대값으로 비교하고 원본값을 출력하는 방법을 사용하더라 그게 더 깔끔할 것 같다 import java.io.*; import java.util.*; public class Main { public static void main(Stri..
[백준] 1927 최소 힙 문제링크: www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int loop = Integer.parseI..
[백준] 11279 최대 힙 문제링크: www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net 자바의 priorityQueue는 기본적으로 최소힙으로 구현되어 있다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReade..
[백준] 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..

티스토리툴바