점냥's Log

문제본문문제해설문제에서의 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시에 끝..

문제본문문제 해설수열 원소의 개수 N은 1이고, 크기가 양수인 부분 수열의 합으로 만들어야 하는 S는 |S| 입니다.부분 수열의 순서가 중요하지 않기 때문에 집합을 구성하는 방식을 N번에서 2번으로 줄일 수 있습니다. 그렇다면 시간복잡도는 O(2 ^ 20)이 되기 때문에 완전탐색으로도 풀 수 있습니다.재귀호출로 해당 원소를 포함한다와 안한다로 부분 집합을 구현하고 나서 S의 값이 맞다면 경우의 수 값을 증가시키면 됩니다.주의할 점크기가 양수인 부분 수열이기 때문에 S가 0일 경우 공집합은 제외 해주어야 합니다.전체 코드import java.util.Scanner;public class Main { static int answer = 0; public static void main(String[..

문제본문들어가기 전parametric search는 이분 탐색의 원리를 이용해서 최적의 해를 구하는 방법입니다. 공부하기 위해 참고한 사이트에서는 이렇게 설명하기도 합니다.최적화 문제를 결정 문제로 바꾸어 푸는 것이다.정렬된 리스트에서 탐색 기준을 정해놓고, 특정 위치에서 그 기준에 만족하지 않는 다면 나머지 위치들도 기준에 통과하지 못한다고 확신하여 문제를 해결하는 것입니다. O(logN + a)의 시간 복잡도를 가진 parametric search 알고리즘은 이분 탐색과 마찬가지로 정렬된 연속적인 값들에 대해서 탐색의 범위를 1/2 씩 줄여나가며 최적의 답을 찾는 알고리즘입니다. 알고리즘의 개념이 궁금하다면 참고 링크에 더 자세히 나와있습니다. 문제 해석탐색 범위 설정long start;long en..

문제 본문문제 해설곱셈이라는 문제는 A의 수를 B번 거듭제곱하여 C로 나눈 값을 반환하는 문제입니다.보통 N의 알고리즘인 재귀 호출로 구하는 방법이 가장 쉽지만 A, B, C의 입력 범위가 장난 아니게 큽니다.1 알고리즘의 수행시간 예측으로 1억 번의 연산이 1초 정도로 계산됩니다. 하지만 입력 범위가 최대 21억으로 N의 알고리즘을 수행한다면 문제에서 주어진 2초의 시간을 훨씬 넘을 것입니다. 이때 logN의 분할정복을 사용할 수 있습니다.분할 정복은 문제의 범위를 2개 이상으로 잘게 쪼개어 계산하고 필요하다면 합치는 알고리즘입니다. 문제에서 주어진 거듭제곱은 수학에서 다음과 같이 표현할 수 있습니다. 2^12 = 2^6 * 2^6 , 2^6 = 2^3 * 2^3 즉 매번 계산하고자 하는 거듭제곱의 수..

문제본문입력으로 들어오는 N! 의 결과 값에서 뒤에서부터 0이 아닌 숫자가 나올 때까지 0의 개수를 구하라문제에서 주어지는 N의 범위는 0 입니다. 팩토리얼 계산이라는 것을 가정하면 엄청 큰 정수를 나올 텐데요. 이때 자료형으로 표현할 수 있을지 판단해야 합니다. 결과적으로 N의 범위에서 계산되는 팩토리얼의 값을 int 또는 long 자료형에 담을 수 없습니다. 다만 BigInteger를 사용하시면 값을 담을 수 있습니다. BigInteger로 팩토리얼의 값을 계산 후 0의 수를 구하셔도 됩니다. 하지만 이번 글에서는 소인수 분해 성질을 이용해서 풀어보려고 합니다.첫 번째 방법 - 5와 2의 개수 구하기어떤 숫자 뒤에 0이 있다는 말은 10의 곱으로 이루어져 있다는 뜻일 겁니다. 320 = 32 x 1..

문제본문어떠한 수 V(i)에 대해서 몫이 a고 나머지가 r이라면 아래의 수식이 성립한다. V(i) = a(i) * m + r(i) 그리고 V(i)에서 V(i-1)을 빼면 아래와 같은 수식이 된다.V(i) - V(i-1) = (a(i) - a(i-1)) * m + (r(i) - r(i-1)) 문제에서 원하는 답은 N개의 수에 대해서 M으로 나누었을 때 나머지가 모두 동일하게 되는 M을 모두 찾는 것이다. 나머지가 모두 동일하다는 것을 위 수식에 적용해 보자. V(i) - V(i-1) = (a(i) - a(i-1)) * m + 0 r(i)와 r(i-1) 값이 같으니 나머지 부분이 0이 된다. a(i) - a(i-1)의 값을 A로 치환해서 다시 보자. V(i) - V(i-1) = A * m + 0어떤 수를 ..

문제 본문그리디 알고리즘, 탐욕법으로 불리는 알고리즘은 원하는 답을 구하기 위해 모든 경우를 탐색하는 것이 아니라 문제를 해결하는 과정에서 최적이라고 생각하는 과정만 선택하는 알고리즘입니다.문제 해석괄호를 집어넣어 최솟값을 만들어라. 이 문제를 풀기 위해 모든 곳에 괄호를 넣어서 계산하면 시간이 오버될 수 있습니다. 최대한 크게 빼도록 최적의 방법만 선택해야 합니다. char이 숫자면StringBuilder stringToNumberTemp = new StringBuilder(); if (c >= '0' && c 입력된 문자가 숫자인지 판단하는 방법은 유니코드의 값을 비교하여 알 수 있습니다. 올바른 피연산자를 구하기 위해 숫자 문자를 StringBuilder에 저장합니다. 입력에서 숫자가 0으로 시작..

문제본문입력 [물건의 개수] [최대 무게]4 7[물건 무게] [물건 가치]6 134 83 65 12________________출력[최대 가치]14동적프로그래밍의 대표 문제 불리는 Knapsack 알고리즘은 dp를 사용하여 최대 가치를 구하는 문제 유형이다.문제 해설동적프로그래밍은 dp를 어떻게 설계하는지가 중요하다. Knapsack은 이중 배열로 dp를 설정한다. dp [i][j]는 i번째까지 물건을 집어넣는다고 했을 때, 남아있는 무게가 j라면 얻을 수 있는 최대가치를 뜻한다. 무게1234567첫 번째 물건000001313두 번째 물건??????? 넣을 수 있는 무게는 1부터 최대 무게까지 잡아놓고 계산을 시작한다.무게 6, 가치 13인 첫 번째 물건부터 가방에 넣어본다. 넣을 수 있는 무게가 6이 ..

문제 본문동적 프로그래밍 방법은 이전에 구했던 값을 저장하여 재활용하는 방법이다. 불필요한 코드 실행을 줄여 시간을 단축시킬 수 있다. 하지만 값을 저장하게 되면서 O(n)의 메모리가 할당된다문제 해설전깃줄은 백준 사이트에서 LIS(Longest Increasing Subsequence)의 응용으로 분류된 문제입니다. N개의 전깃줄을 겹치지 않게 제거해야 하는 최소 개수의 전깃줄을 구해야 합니다. 최소 개수의 전깃줄을 제거하여 겹치지 않게 설치된 남은 전깃줄은 겹치지 않게 설치될 수 있는 최대 전깃줄입니다. 힌트에서는 랜덤으로 들어오는 전깃줄의 위치 중 한 곳을 정하여 오름 차순 정렬을 시도하라고 하지만, 해당 방법으로는 이중 배열 형태로 전깃줄의 값을 저장해야 할 것 같아 복잡해 보였습니다. 그래서 전..