문제본문 문제 난이도를 제공해주는 것은 나에게 오히려 독이 되는 것 같다. 이 문제는 골드 1 문제로 시작부터.. 내가 풀 수 있을까? 하던 문제 그래서 조금 고민하다 힌트를 우선 보았었다 ㅜㅜ 재귀호출이 자주 쓰이는 분할정복 문제인 것을 알기 때문에 함수부터 작성했다. 2차원 배열인 board에서 불순물이 하나도 없고 결정이 오직 1개 존재하도록 매 재귀호출 마다 board를 탐색해야 한다. 그런데 문제는 쿼드 트리처럼 정사각형으로 잘리는 것이 아닌 불순물의 위치에 따라 잘리기 때문에 분할된 문제의 크기를 정수로 나타내기 어려워서 가로와 높이 모두 시작과 끝을 매개변수로 넘겨주었다. public int division(int startX, int endX, int startY, int endY, int..
풍선 터트리기 2020 월간 코드 챌린지 9월에 나왔던 문제로 1시간 동안 시간초과로 못 푼 문제 ㅜㅜ 대회 당일 작은 값을 가진 풍선을 터트릴 수 있는 기회는 1번이라는 조건을 잘 활용하지 못했다. // 삭제하고자 하는 위치 : index //재귀 호출 내 로직 if //풍선 하나 남은 경우 그 값을 저장 else /** index - 1과 비교하여 큰 값을 제거하고 재귀 호출 --- 1 만약 작은 값을 제거 할 수 있다면 작은 값을 제거하여 재귀호출 --- 2 //위와 로직 같음 index + 1과 비교하여 비교하여 큰 값을 제거하고 재귀 호출 --- 3 만약 작은 값을 제거 할 수 있다면 작은 값을 제거하여 재귀호출 --- 4 */ 로직을 보면 최대 4개의 재귀호출을 진행하므로 log(N^4) 인 ..
문제본문 문제해설 문제에서의 N의 범위는 100,000 이하입니다. 따라서 N^2 인 완전탐색으로는 시간초과가 발생할 수 있습니다. 분할 정복은 문제의 범위를 2이상으로 나누어 부분적으로 정복하여 푸는 방법입니다. 최대의 점수를 갖는 부분배열을 구하는 이 문제에 적용하여 중앙 값을 기준으로 3가지 경우에서 최대값을 구하면 됩니다. 1. 중앙값을 포함하는 부분 배열 이 경우는 중앙 값을 포함하는 부분 배열의 점수를 구하는 방법입니다. 히스토그램 풀이법과 유사하고 처음 중앙값하나 존재하는 배열에서 왼쪽, 또는 오른쪽으로 하나씩 요소들을 포함시키면서 최대값을 찾는 방법입니다. 왼쪽이나 오른쪽으로 이동하는 기준은 부분배열의 점수 공식을 참고하면 큰 요소를 포함하는 것이 무조건 최대 점수로 가는 길이 됩니다. 그..
문제본문 문제 해설 가능한 빨리 시작하는 강의를 우선으로 진행하고, 시작하는 시간이 같다면 끝나는 시간이 빠른 강의들을 우선적으로 강의실을 배정합니다. 위의 기준으로 입력으로 들어오는 배열을 정렬합니다. //O(nlong) Arrays.sort(room, new Comparator() { @Override public int compare(int[] o1, int[] o2) { int result = o1[0] - o2[0]; if (result != 0) return result; else return o1[1] - o2[1]; } }); 첫번째 강의가 3시에 끝나고, 두 번째 강의가 3시에 시작한다면 강의실을 새로 배정하지 않고 기존 강의실에서 수업을 진행할 수 있습니다. 따라서 정렬된 배열에 대해 ..
문제본문 들어가기 전 parametric search는 이진색의 원리를 이용해서 최적의 해를 구하는 방법입니다. 공부하기 위해 참고한 사이트에서는 이렇게 설명하기도 합니다. 최적화 문제를 결정 문제로 바꾸어 푸는 것이다. 정렬된 어떠한 리스트에서 탐색 기준을 결정해 놓고 특정 위치에서 기준에 만족하지 않는 다면 그 아래있는 위치들도 모두 기준에 통과하지 못할 것이라는 확신으로 문제를 해결하는 것입니다. O(logN + a)의 시간 복잡도를 가진 parametric search 알고리즘은 이진색과 마찬가지로 정렬된 연속적인 값들에 대해서 탐색의 범위를 1/2 씩 줄여나가며 최적의 답을 찾는 알고리즘입니다. 알고리즘의 개념이 궁금하다면 참고 링크에 더 자세히 나와있습니다. 문제 해석 탐색 범위 설정 long..
문제 본문 문제 해설 곱셈이라는 문제는 A의 수를 B번 거듭제곱하여 C로 나눈 값을 반환하는 문제입니다. 보통 N의 알고리즘인 재귀 호출로 구하는 방법이 가장 쉽지만 A, B, C의 입력 범위가 장난 아니게 큽니다. 1
문제본문 문제 해석 입력으로 들어오는 N!의 결과 값에서 뒤에서 부터 0이 아닌 숫자가 나올때까지 0의 개수를 구하라 문제를 이해하는 데 시간이 필요했다. 결론적으로 말하면 N!의 결과 값이 301200라고 한다면 뒤에서 부터 0이 2번 나오고 그 다음으로 2가 나온다. 따라서 0이 아닌 숫자가 나올 때까지 0의 개수는 2라고 답할 수 있다. 문제에서 주어지는 N의 범위는 0
문제본문 문제 해석 어떠한 수 V(i)에 대해서 몫이 a고 나머지가 r이라면 아래의 수식이 성립한다. V(i) = a(i) * m + r(i) 그리고 V(i-1) 수식을 V(i) 뺀다면 아래와 같은 수식이 된다. V(i) - V(i-1) = (a(i) - a(i-1)) * m + (r(i) - r(i-1)) 자! 문제에서 원하는 답은 N개의 수에 대해서 M으로 나누었을 때 나머지가 같게되는 M을 모두 찾는 것이다. 나머지가 같다는 것은 위 수식에 대입해보면 답은 V(i) - V(i-1)의 숫자를 나머지가 0으로 만드는 M을 찾는 것이다. N개의 수를 오름차순으로 정렬하기 long[] nums = new long[n]; for (int i = 0; i < nums.length; i++) { nums[i] ..
문제 본문 그리디 알고리즘, 탐욕법이라고 불리는 이 알고리즘은 원하는 답을 구하기 위해 모든 경우를 탐색하는 것이 아니라 문제를 해결하는 과정에서 최적이라고 생각하는 과정을 선택하는 알고리즘입니다. 문제 해석 Input: 55-50+40 output: -35 문제를 설명하자면 괄호가 생략된 수식에서 괄호를 집어넣어 최솟값을 만들어라!입니다. 예시로 주어진 입력으로 만들어 낼 수 있는 최솟값의 수식은 55-(50+40)입니다. 여기서 우리가 문제를 풀기위해 적용해야 하는 그리디 알고리즘 괄호를 수식에서 숫자를 제외한 모든 곳에 넣어서 결과를 계산한 후 최소 값을 찾는 것이 아니라 답을 구하기 위한 문제의 최적 방법을 찾는 것이죠. 최소 값을 구하기 위한 최적 방법은 최대한 크게 빼는 것입니다. Input:..
