분할정복
-
[백준 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 -> ..
-
[백준 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) 사이즈만큼 하나..