알고리즘
-
[백준 1992] - [분할정복] - 쿼드트리알고리즘/분할정복(Divide and conquer) 2018. 11. 29. 11:19
문제 링크 : https://www.acmicpc.net/problem/1992 이 문제는 백준 1780번 종이의 개수 문제와 같은 형식으로 푸는 문제이다. 1780 문제를 풀어봤으면 이문제는 쉽게 풀릴거고 또 이 문제를 풀면 1780 문제도 쉽게 풀릴것이다. 1780 문제 링크와 본인의 풀이 소스 링크도 첨부하겠다. 백준 1780번 종이의 개수 2018/11/28 - [알고리즘/분할정복(Divide and conquer)] - [백준 1780]-[분할정복]-종이의 개수 (JAVA) 이 문제를 접근하기전 사이즈의 입력 크기 N 부터 확인해야한다. 아무 수나 입력이 되는것이 아니라 2의 배수로 입력이 된다고 한다. 즉 N * N 의 쿼리가 전분 같은 수로 돼 있지 않으면 N/2 * N/2 * 4 만큼 다시..
-
[백준 2749] - [분할정복 수학] - 피보나치 3알고리즘/분할정복(Divide and conquer) 2018. 11. 28. 18:40
문제 링크 : https://www.acmicpc.net/problem/2749 이문제를 처음 보고 어떻게 10의 16승까지 풀지.. 하면서 멘붕에 이르렀고 정말 순수하게 10의 16승까지 계산을 하고 돌려보니 결과를 받아볼 수 없었다.즉.. 시간 초과에 걸리게 되는것.. 정말 멘붕이었고 자존심을 버리고 구글링을 하였다.이 문제는 피사노 주기 라는것을 이용해야 한다고 한다. 나중에 피사노 주기에 대한 문제를 포스팅 해야겠다. 피사노 주기에 대해서 간략하게 정리를 하면피보나치 수열을 N 의 값으로 나눈 나머지는 일정한 주기를 가진다. 라고 한다. 즉 m으로 나눈 나머지는 K(m) 개의 주기를 가지고 피보나치 수열을 K(m)개의 주기만큼만 구하면 된다는 것이다. 이 문제에서는 m이 1,000,000이다. 아..
-
[백준 2740] - [행렬]- 행렬 곱셈알고리즘/분할정복(Divide and conquer) 2018. 11. 28. 16:39
문제 링크 : https://www.acmicpc.net/problem/2740 이 문제는 행렬의 곱을 계산하면 되는 문제다. 음 이문제는 너무 수학이라 어떻게 셜명을 해야할지 모르겠다. 그냥 풀자. 소스123456789101112131415161718192021222324252627282930313233343536373839404142434445464748import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOExcep..
-
[백준 1780]-[분할정복]-종이의 개수 (JAVA)알고리즘/분할정복(Divide and conquer) 2018. 11. 28. 13:18
문제 링크 : https://www.acmicpc.net/problem/1780 이 문제는 분할정복으로 풀어야 한다. 입력받은 사이즈가 9 라면 총 9*9 개의 모든 좌표가 같아야 하나의 정사각형 종이가 완성된다. 그럼 9*9개의 수가 같지 않다면? 9등분을 한뒤에 다시 정사각형 종이가 나오는지 확인해야 된다.사이즈 9를 3으로 나눠 다시 확인하고 여기서도 정사각형 종이가 나오지 않는다면 3으로 다시 나눠서 확인해야한다. 이문제의 조건은 사이즈는 무조건 3의 배수로 입력 된다고 한다. 첫째 줄에 N(1≤N≤3^7, N은 3^k 꼴)이 주어진다. 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다. 3으로 나눠지지 않을 걱정은 안해도 되고 그럼 이 문제를 어떻게 푸는지 간단하게 정리하면 1) 사이즈만큼 하나..
-
[백준 9020]-[수학] - 골드바흐의 추측알고리즘/수학 2018. 11. 27. 15:14
문제링크 : https://www.acmicpc.net/problem/9020 이 문제는 에라토스테네스의 체의 확장 문제이다. 에라토스테네스의 체 문제는 이전글에서 확인하면 된다. 2018/11/27 - [알고리즘/수학] - [백준 1929]-[수학]-[에라토스테네스의 체] - 소수 구하기 (java) 이 문제를 접근하는 방법은 입력받은 수 N을 구성하는 두 소수의 합을 구하면 된다. 두 소수의 합이 여러가지가 있다면 두 수의 차가 제일 적을 수를 구하면 된다. 그럼 N 보다 작은 모든 소수들을 찾아서 합해야하나 하지만 그렇지 않아도 된다. N 의 절반인 수를 기준으로 하나의 수는 1씩 감소하고 다른 하나는 1씩 증가하면서 두 수가 실수 인경우를 찾으면 위의 조건을 모두 만족한다. 입력받은 수가 16인 ..
-
[백준 4948]-[수학] - 베르트랑 공준알고리즘/수학 2018. 11. 27. 14:34
문제링크 : https://www.acmicpc.net/problem/4948 이 문제는 에라토스테네스의 체를 이용해서 푸는 좀 심화 문제라고 생각하면 된다. 2018/11/27 - [알고리즘/수학] - [백준 1929]-[수학]-[에라토스테네스의 체] - 소수 구하기 (java) 먼저 이문제를 풀기전에 입력수의 크기는 12345 라고 하고 베르트랑의 공준이 어떤 내용인지 설명해주고 있다. n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오. 배열의 범위를 123456 로만 하면 인덱스가 초과되서 런타임에러가 발생한다.최소 범위 123456 * 2 값인 246912 + 1 을 해야한다. 문제를 푸는 순서는 다음 순서를 따른다.1) 에라토스테네스의 체로 2부터..
-
[백준 1929]-[수학]-[에라토스테네스의 체] - 소수 구하기 (java)알고리즘/수학 2018. 11. 27. 13:58
문제링크 : https://www.acmicpc.net/problem/1929 이 문제는 간단한 소수 구하기 소스로 구한다면 굉장히 오랜 시간이 걸리고 시간 초과가 발생하는 문제다. 이문제의 입력되는 수의 범위는 1 ~ 1,000,000 인데 기존 소수 구하는 방식은 2 ~ N-1 까지 반복하면서 나누어 지는 수가 있는지 판단하는 소스 였다. 그럼 최악의 상황에서 1에서 1,000,000 까지 구해야 한다면 상상할 수 없는 연산 수가 발생한다. 이렇게 큰 수들에도 소수가 있을거고 그럼 이 큰 수들을 소수인지 판별하는 방법도 있을것이다. 그게 바로 에라토스테네스의 체 라는 방식인데 노가다라 비효율적인 방식이라고는 하는데 지금 문제에는 제일 적합한 방식이다. 출처 : wiki 백과 에라토스테네스의 체를 구하..
-
[백준 2581] - [수학] - 소수알고리즘/수학 2018. 11. 27. 12:51
문제 링크 : https://www.acmicpc.net/problem/2581 이 문제는 소수이 먼저 확인하고 소수인 수를 합하고 최소값만 구하면 되는 문제이다. 입력받는 수의 최대값은 10000 이기 때문에 int 타입으로 처리가 가능하고 int 타입의 최대 수를 MIN 값으로 초기화 한 뒤에 풀면 소수일경우 최소값을 판단하는데 쉽게 판단 할 수 있다. 그리고 마지막에 결과를 반환할때 최소값의 값이 아직 int의 최대값이면 소수가 발견되지 않은거기 때문데 -1을 출력하면 된다. 소스123456789101112131415161718192021222324252627282930313233343536373839import java.io.BufferedReader;import java.io.IOExceptio..