알고리즘/분할정복(Divide and conquer)
-
[백준 1074] - [분할정복] - Z (JAVA)알고리즘/분할정복(Divide and conquer) 2018. 11. 30. 12:04
문제 링크 : https://www.acmicpc.net/problem/1074 이 문제는 분할정복으로 쉽게 풀 수 있는 문제이다. 그리고 배열을 만들필요가 없다. 굳이 만들겠다면 확인해 보자 heap 메모리가 부족하다고 에러가 발생할것이다. 입력값이 최대 값이 15 이다 이 15가 15 X 15 가 아니라 2의 15승이다 2의 15승은 32,768이다. 그럼 32,768 * 32,768 = 1,073,741,824 10억개 정도 나온다. 그럼 이것또한 무식하게 재귀로 풀것인가?? 그것또한 미친짓이다. 이 문제의 정답 비율은 굉장히 높다.그럼 쉽게 접근 할 수 있다는것이다. 배열의 크기를 최소 사이즈인 2가 될때까지 계속 4등분을 하면서 입력받은 좌표가 범위 안에 있는 것들만 계산을 했다. 8*8 배열에..
-
[백준 2309] - [분할정복] 일곱 난쟁이 - JAVA알고리즘/분할정복(Divide and conquer) 2018. 11. 30. 10:56
문제 링크 : https://www.acmicpc.net/problem/2309 이문제는 의도하는바만 잘 파악하면 어렵지 않게 문제를 풀 수 있다. 입력은 무조건 9명의 난쟁이애 대한 키 정보이고 두명을 제외한 나머지의 키의 합이 무조건 100이 된다고 한다. 가능한 답이 여러가지일 경우 아무거나 출력하면 된다고하는데 이럴때는 100이 이루어지면 바로 종료시키고 출력시키면 된다. 문제를 푸는 방법은 두 난쟁이의 키를 전체 아홉 난쟁이 키의 총합에서 뺀 값이 100이면 두 난쟁이의 값을 최소 값으로 변경 시킨 후 정렬하고 출력시키면 된다. 일곱 난장이들의 키를 합하는 것보다 전체 합에서 두명의 키만 뺴는것이 더 바람직할것이기떄문에 두 난쟁이의 키만 빼면 된다. 소스12345678910111213141516..
-
[백준 2263] - [분할정복] - 트리의 순회(java)알고리즘/분할정복(Divide and conquer) 2018. 11. 29. 15:38
문제 링크 : https://www.acmicpc.net/problem/2263 이 문제는 좀 변태적인 문제라 확신한다. 중위 순회(In-order) 가 주어지고 후위 순회(Post-order)가 주어졌을때 전위순회(Pre-order)를 구하라는 문제이다. 예제 입 출력은 아래와 같다. 입력3 1 2 3 1 3 2출력2 1 3 하지만 예제 입출력에는 노드가 3개여서 예제 입출력을 기준으로 풀면 구하기 힘들다.그래서 예제로 트리하나를 만들었고 전위, 중위, 후위 순회의 값을 먼저 구한뒤 이 값이 나오도록 유도해봤다. 위의 트리를 만들어 보았고 각각 전위, 중위, 후위 순회를 구해봤다. 전위 순회 : 1 -> 2 -> 4 -> 7 -> 8 -> 5 -> 3 -> 6 -> 9 중위 순회 : 7 -> 4 -> ..
-
[백준 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) 사이즈만큼 하나..