문제본문 문제 난이도를 제공해주는 것은 나에게 오히려 독이 되는 것 같다. 이 문제는 골드 1 문제로 시작부터.. 내가 풀 수 있을까? 하던 문제 그래서 조금 고민하다 힌트를 우선 보았었다 ㅜㅜ 재귀호출이 자주 쓰이는 분할정복 문제인 것을 알기 때문에 함수부터 작성했다. 2차원 배열인 board에서 불순물이 하나도 없고 결정이 오직 1개 존재하도록 매 재귀호출 마다 board를 탐색해야 한다. 그런데 문제는 쿼드 트리처럼 정사각형으로 잘리는 것이 아닌 불순물의 위치에 따라 잘리기 때문에 분할된 문제의 크기를 정수로 나타내기 어려워서 가로와 높이 모두 시작과 끝을 매개변수로 넘겨주었다. public int division(int startX, int endX, int startY, int endY, int..
문제본문 문제해설 문제에서의 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시에 시작한다면 강의실을 새로 배정하지 않고 기존 강의실에서 수업을 진행할 수 있습니다. 따라서 정렬된 배열에 대해 ..
문제 본문 문제 해설 곱셈이라는 문제는 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:..
문제본문 입력 [물건의 개수] [최대 무게] 4 7 [물건 무게] [물건 가치] 6 13 4 8 3 6 5 12 ________________ 출력 [최대 가치] 14 동적프로그래밍의 대표 문제 불리는 Knapsack 알고리즘은 dp를 사용하여 무게와 가치 두 가지 요소로 가질 수 있는 최대 가치를 구하는 문제 유형이다. 문제 해설 동적프로그래밍은 dp를 어느 부분으로 잡는 지가 관건 인듯하다. Knapsack은 이중 배열로 dp를 설정한다. dp[i][j]라고 가정하면, i번째까지 물건을 집어 넣는 다고 했을 때, 남아있는 무게가 j라면 얻을 수 있는 최대가치를 뜻한다. 해당 알고리즘은 테이블로 과정을 묘사하면 이해가 더 쉽다. 무게 1 2 3 4 5 6 7 1번째 물건 0 0 0 0 0 13 13 2..
문제 본문 동적 프로그래밍이란 동적 프로그래밍 방법은 문제의 해결 과정에서 이전에 구했던 과정을 또 다시 반복하여 실행되는 것을 방지하는 방법으로, 불필요한 코드 실행이 줄어 시간을 단축시킬 수 있습니다. 하지만 O(n)의 메모리가 할당 되어야 합니다. 문제 해설 전깃줄은 백준 사이트에서 LIS(Longest Increasing Subsequence)의 응용으로 분류된 문제입니다. N개의 전깃줄을 겹치지 않게 제거해야 하는 최소 개수의 전깃줄을 구해야 합니다. 문제 설명 그대로 풀려고 해서 방법이 도저히 생각나지 않다가 사람들의 힌트를 보고 깨달았습니다. ㅎ.. 해답은 제거가 아니고 설치입니다. 최소 개수의 전깃줄을 제거하여 겹치지 않게 설치된 남은 전깃줄은 겹치지 않게 설치될 수 있는 최대 전깃줄 입니..
