분류 전체보기 (644) 썸네일형 리스트형 백준 : 10830 https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 행렬을 2^n 제곱꼴로 미리 저장해둿다가 B 제곱을 구해야하면 B = 2^1 + 2^4 + 2^8 꼴로 분해해서 사용한다. package day0301; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class B1083.. 페르마의 소정리 , 확장 유클리드 페르마의 소정리 https://www.youtube.com/watch?v=uJAoaIeOXJM 확장 유클리드 Ax + By = GCD(A,B) 가 있을때 만족하는 정수 x, y를 찾는 방법 방법 두가지 있음. while 반복문을 이용한 방법. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 static void Uclede(long a, long b) { // Ax + By = 1 만족하는거 찾기 long s[] = new long[2]; long t[] = new long[2]; s[0] = 1; t[0] =0; s[1] = 0; t[1] = 1; while(a %b != 0) { long ss = s[0] - (a/b)*s[1]; lon.. 백준 : 11401 https://www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 페르마의 소정리와 확장 유클리드 알고리즘으로 값구하기. 확장 유클리드알고리즘은 Ax + By = GCD(A,B) 라고할때 맞는 정수 x y를 구하는 방법이다. 재귀 적인 방법이 있고 반복문을 통한 반복이 있는 반복문을 통한방법이 이해하기 쉬우므로 사용하였다. 아래는 재귀적으로 푸신분의 소스참조.. 이해할려고해도 이해잘안됨 https://onsil-thegreenhouse.github.io/programming/probl.. 백준 : 3197 https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 문제 두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다. 호수는 가로로 R, 세로로 C만큼의 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다. 호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다. 아래에는 세 가지 예가 있다. ...XXXXXX..XX.XXX ....XXXX.......XX www.acmicpc.net 단순 BFS탐색으로는 많은 시간이 걸린다. 줄일수 있는건 2가지가 있다. 얼음이 녹는 시간을 사전에 미리구한다. 현재위치가 X일때 상.. Sqrt Decomposition 평방분할 알고리즘 구간합을 구할때 쓰는 알고리즘이다. 구간을 √N 으로 나눠주고 그 구간의 합을 구하는 알고리즘이다. 만약 0~15 라면 크기가 4인 배열을 만든다음 0~3 , 4~7 , 8~11 ,12~15 합들을 배열에 넣어준다. 그리고 배열 4~7의 값을 구해라고하면 바로출력하면된다. 하지만 3~9처럼 걸쳐잇는 합을 출력해야할경우에는 left right를 만들어서 크기가 4식 나눳으므로 인덱스값이 4로나누엇을때 0이 되는애들이 될때가지 left를 더하거나 right를 빼면서 0이나오는 값으로 만들어준다. 안되는값들은 그냥 arr에서 직접 result에 더해준다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29.. 백준 : 1655 https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -10,000보다 크거나 같고, 10,000보다 작거나 같다. www.acmicpc.net 문제는 MaxHeap Minheap을 만들어서 중앙값 왼쪽 오른쪽을 관리하는 것이다. Maxheap mid Minheap 이런식으로 정렬은한다고 친다면 처음 받은 중앙값을 mid로 하고 관리하면된다. 이때 처음받은 값을 기준으로 그다음값이 mid 보다 크다면 Minheap에 넣어주고 작다면 Maxheap에 넣어준다. 이때 중.. JAVA : heap (삽입,삭제) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 package study; public class HeapTest { static int size =1; static int heap[] = new int[100]; static void insert(int item) { int i = ++size; while(i!=1 && heap[i/2] 백준 : 12865 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다. 입력으로 주어지는 모든 수는 정수이다. www.acmicpc.net 0 - 1 냅색 문제이다. dp[i][k] = max(dp[i-1][k],dp[i-1][k-Weight[i]]) 이다. 물건은 하나밖에없다 . 따라서 배낭에 하나넣으면 같은 물건은 더넣을수가 없는 전제이다. 그래서 0 - 1 냅색 dp는 1~N 까지의 물건들을 배낭에 넣을때 1. .. 이전 1 ··· 66 67 68 69 70 71 72 ··· 81 다음
