zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
배열에서 최소한의 원소를 제거하여 mountain-array 가 하도록 하는 문제. mountain-array는 순서대로 원소가 커졌다가 작아지는 배열이다. 처음엔 LIS 안 쓰고 무식하게 DP를 돌렸는데 Wrong Answer 몇개 후 MLE 까지 떴다... 아래 discuss 느낌으로 구현했는데 top-down이라 메모리를 많이 먹은 듯.. ! 결국 L…
배열을 m개의 부분 배열로 나눌 때 각각 부분 배열의 합의 최대가 최소가 되도록 하는 문제. 처음에 딱 보면 뭔가 어려워 보이는데 잘 생각해보면 이분 탐색으로 꽤 간단히 풀린다. 또는 파라메트릭 서치라고 하는데.. 그냥 이분 탐색이긴 하다. 먼저 이분 탐색으로 타겟을 정한다. 그런 다음 부분 배열의 합이 타겟 값을 넘지 않도록 하면서 배열을 나눠볼 수 있다…
이진 트리가 있을 때 트리 상의 경로 중에 합이 가장 큰 경로를 구하는 문제. 어려워 보이지만 subproblem으로 나누면 의외로 간단하다 일단 현재 노드에서의 최대 합을 구한다면 왼쪽 -> 현재 노드 -> 오른쪽 서브트리의 최대가 최대 합이 될 것이다. 그런데 구현할 때 위의 값 그대로 리턴하면 안되는데 경로가 중복될 수 있기 때문이다. 따라서 함수에서…
의자와 식물이 있을 때 의자를 2개씩 묶을 수 있는 경우의 수를 구하는 문제. 딱 보니 DP 냄새가 나서 탑 다운으로 풀었는데 ... 메모리 초과가 난다. 바텀업으로 고치니 통과! 또, 2차원 DP를 1차원으로 줄이니 더 빨라지고 메모리도 적게 먹는다. 간단하게 설명하자면 로 정의하고 점화식을 만들 수 있다. 그리고 for문을 돌면서 덮어 씌워지므로 1차원…
n, k 가 입력으로 주어질 때 n개의 수의 곱으로 k를 만들 수 있는 방법의 수를 구하는 문제. 처음에 단순 DP로 하니 시간 초과가 난다... O(NKD) (F: 약수 개수) dicussion을 보니 Stars and bars 개념을 이용해서 풀 수 있다. Stars and bars를 간단하게 설명하면 별을 바로 나눌 수 있는 경우의 수를 구하는 문제이…
노동자의 품질과 최소 임금이 주어질 때 K 명의 노동자를 뽑아야 한다. K명의 노동자가 받는 임금과 품질의 비율은 모두 같아야 한다. 이때 K 명을 뽑을 수 있는 최소 임금을 구하는 문제. 처음부터 드는 생각은 가성비가 좋은 노동자를 뽑아보는 것이다. 즉, wage / quality 를 한 값이 작은 순서로 K명을 뽑아주면 가성비가 좋은 K 명을 뽑을 수 …
처음엔 1칸을 뛸 수 있고 k칸 뛴 다음엔 k-1, k, k+1 칸을 뛸 수 있을 때 끝까지 점프할 수 있는지 확인하는 문제. 그냥 DP. N 크기도 작아서 대충 돌려주면 된다. 하드 중에서 아주 쉬운 문제. DP[i, k]: i 인덱스에서 k칸 뛸 때의 가능 여부 위처럼 점화식 세우고 k-1,k,k+1 에 대해 돌려주면 된다. 위치가 아니라 인덱스로 저장…
n 이하의 수 중에서 2진법으로 했을 때 1이 연속으로 나오지 않는 수의 개수를 구하는 문제. DP로 풀 수 있다. 특정 자리 수에서 1이 연속으로 나오지 않는 수의 개수는 DP로 구하고 n보다 작은지 판단은 1이 나왔을 때 0으로 시작하는 나머지 수들을 더해주면 된다. 아래 디스커션이 이해하기 좋다.
많이 나온 원소부터 pop이 되는 스택을 구현하는 것이다. 하드 치고는 꽤 쉬운 문제. 문제 그대로 많이 나온 원소부터 pop이 되도록 구현하면 되는데 원소가 나온 카운트에 대한 맵을 하나 두고 스택도 카운트 별로 만들어 둔다. 예제에서 push, pop 쿼리가 최대 2만개 까지라고 했으므로 20001개의 스택을 만들어 두었다. push의 경우 원소의 개수…
2차원 배열에 수가 있고 써있는 수만큼의 시간이 지나야 다음 노드로 이동할 수 있다. n-1, n-1에 도착 가능한 최소 시간을 구하는 문제. 단순 완전 탐색 BFS로 하니 시간 안에 통과는 되지만 매우 느리다. 좀 더 생각을 해보면 시간은 최소 0, 최대 n^2 이므로 이분 탐색으로 가능한 최소 시간을 구한다면 n^2 log(n^2) 으로 구할 수 있다.…