돌이 코딩하는 방

문제 링크 : https://www.acmicpc.net/problem/17613 문제 풀이 일단 문제를 한 번 보자. "만일 점프간격을 2배씩 계속 증가시켜 마지막 점프에서 목표 수 x를 지나칠 것 같으면, 필요한 경우 언제든지 점프 간격을 다시 처음 상태인 간격 1로 되돌아 갈 수 있다. 이것을 재시작이라고 부른다." 라는 문구가 굉장히 중요한 부분이다. 굳이 이 문구를 통해서 유추를 할 필요는 없지만, 풀이를 생각하는 과정에서 이 문장은 풀이의 일부에 확신을 주게 된다. Phase 1 현재 개구리가 $2^i$ 까지 한 번에 뛰었다. 그리고 $2^{i+1}$을 뛸 수 있는 상황이다. 그런데 안 뛸 이유가 있을까? $2^{i+1}$은 1부터 $2^i$까지의 합보다 크다. 1번의 점프로 i번의 점프의 효..

문제 링크 : https://www.acmicpc.net/problem/9446 문제 태그 더보기 DP,정렬 문제 소개 모든 물건을 각 가격에 살 수 있다. 하지만, 조합식에 따라서 두 물건을 합쳐 새로운 물건을 만들 수도 있다. 이때 1번물건을 만들기 위해서 필요한 최소가격을 구하자. 문제 풀이 문제를 보고 DP가 생각이 났다. DP table 정의도 바로 DP[i]=i번째 물건을 얻는 데 필요한 최소 비용. 또한 식은 i,j로 k를 만들 때 $DP[k]=min(DP[k],DP[i]+DP[j])$로 업데이트를 할 수 있다. 여기서 DP의 필요조건을 생각해보자. 어떤 DP table을 채울 때 사용되어진 값들이 있다면 그 사용되어진 값들은 확정된 상태여야 한다. 즉, 위의 식으로 따지면 DP[k]의 최종..

문제 링크 : https://www.acmicpc.net/problem/14870 문제 태그 DP, Two pointer, Segment Tree 문제 풀이 일단 기존 상태의 상황을 구하는 것은 매우 쉬울 것이다. 당연히 DP로 구할 수 있고, 이때의 식은 다음과 같다. $DP[i][j]=max(DP[i-1][j],DP[i][j-1])+arr[i][j]$ 여기서 특정위치의 arr값을 1을 올리거나 내리는 값을 했을 때 DP 테이블이 어떤식으로 바뀌는지 구해야 하는 문제이다. 만약 $DP[i-1][j]$와 $DP[i][j-1]$이 둘 다 바뀌었으면 $DP[i][j]$도 바뀌었을 것이다. 혹은 둘 중에 더 큰 값, 즉 영향을 받는 값이 바뀌면 바뀔 것이다. 여기서 한가지 관찰을 해야한다. 한 가로줄에 대해서..

문제 링크 : https://www.acmicpc.net/problem/14869 문제 태그 DP, deque, Segment Tree 문제 풀이 (의식의 흐름) 기본적으로 난이도가 있는문제이다. 일단 이 문제를 보자마자 이 문제가 DP라는 사실을 깨닫지 못했다면, 앞으로의 관찰은 거의 불가능한 난이도라고 생각해도 좋다. 그럼 DP 테이블을 정의해보려고 해보자. 일단 몇번째 강좌인지가 중요할 것이고, 어느 학원에서 듣는지가 중요할 것이다. 그렇게 $DP[i][j]$를 i번째 강좌를 j번 학원에서 수강할 때, 이때까지의 비용의 최솟값이라고 설정하자. 이러면 문제는 문제의 조건인, 한 학원에서 s~e 개를 연속해서 듣기를 만족할 수 없다. 그렇다고 $DP[i][j][k]$를 설정해서 k를 j번째 학원에서 현..

사실 Technique라고 하기도 뭐하지만... 최근에 여러문제들을 풀면서 느낀 점이 있어서 간단하게 적어 놓으려고 한다. Prefix Sum 이란? Prefix = 접미사 sum = 합. 그니까 앞에서 부터의 합을 의미한다. 어떠한 값이 들어있는 기존의 배열 arr이 존재한다고 하면 $pre[x]=\sum_{i=1}^{x} arr[i]$ 로 표현되는 값들이 prefix sum들이라는 것이다. How? prefix sum 배열을 채우는 것은 $O(N)$만에 정말 간단하게 할 수 있다. $pre[i]=pre[i-1]+arr[i]$ 로 할 수 있다. 어떤 식으로 활용해야 할지에 대해서 고민을 해봐야 한다. prefix sum은 구간 합을 구할 때 주로 사용되어진다. i부터 j까지의 구간합은 $pre[j]-p..

문제 링크 : https://www.acmicpc.net/problem/10067 문제 소개 길이 n의 수열을 k번 자른다. 자를 때 마다, 자른 후 양쪽 수열의 값의 각각의 합을 곱한 것만큼 점수를 얻는다. 이때 얻을 수 있는 최대 점수와 자르는 방법을 구하시오. 문제 풀이 우리는 이 문제를 최종 시점관점에서 보면서 점수에 어떤 값을 이 추가되었는지를 살펴보아야 한다. (a,b,c,d)를 (a,b),(c,d)로 잘랐다고 하자. 이러면 우리는 (a+b)*(c+d)의 점수를 얻게 된다. 이를 다른 식으로 풀어쓰면 ac+ad+bc+bd 만큼의 점수를 얻게 된다는 것이다. 이는 서로 다른 그룹에 속하는 임의의 두 값을 곱해서 더한 값이다. 결국 그전에 어떤 순서로 어떻게 잘랐건 간에, 마지막에 다른 그룹에 있..

문제 링크 : https://www.acmicpc.net/problem/1226 문제 소개 어떤 당이 빠져도 합이 과반수가 안되는 집합을 깔끔한 연합이라고 한다. 가장 큰 크기의 깔끔한 연합을 구하여라. 문제 풀이 가장 큰 크기의 깔끔한 연합을 구하는 것이 아니라 관점을 바꾸어서 크기가 K인 깔끔한 연합이 존재하는 지에 대해서 구해도 된다. 모든 값에 대해서 다 가능성을 구해주면 된다. 일단 기본적으로 몇 개의 값의 합이 K가 되어야 한다. 합이 K가 되는 여러가지 방법중 깔끔한 연합이 될 확률이 가장 높은 것은 것은 연합내의 가장 작은 값이 커야 한다는 것이다. 가장 작은 값만 빼더라도 과반수가 안되면 깔끔한 연합이라고 할 수 있고, 그러기 위해서는 연합내 가장 작은 값이 커야한다. 따라서 N개의 숫자..

문제 태그 : https://www.acmicpc.net/problem/11001 문제 소개 각 날 별로 넣을 때의 가치와 꺼낼 때의 온도가 주어진다. 어떤 김치의 맛은 (숙성 시간)*(김치를 꺼낼 때의 온도)+(김치를 넣은 날 가치)로 정의된다. 만들 수 있는 가장 맛있는 김치의 맛을 구하여라. 문제 풀이 이 문제를 봤을 때는 이 문제가 DnC Optimization을 쓰는 문제인지 모르고 봤다. (DnC Optimization에 대한 설명글) 그리고 풀이를 들었기 때문에 상세한 의식의 흐름과정은 설명할 수가 없다. 그대신 식을 전개해 나가면서 왜 DnC 적용이 되는지를 살펴보려고 한다. 넣은 날의 가치를 $V_i$라고 하고, 꺼낼 때의 온도는 $T_i$라고 하자. 나는 j일때 넣은 김치가 제일 맛있을..

DP 문제에서 $O(N)$의 시간복잡도를 $O(lgN)$으로 줄여주는 또 다른 테크닉이다. DP에 DnC는 굉장히 안어울릴 것 같다. 사실 그렇긴 하다. 사용되어질 조건이 까다롭고, 이 문제에서 DnC를 사용할 수 있는 조건을 만족하는지 알기도 굉장히 어렵다. DnC Opmization을 사용하는 문제는 대체로 굉장히 까다롭고 어렵다. DnC Optimization이란? Divide and Couquer Optimization의 약자로 한글로 해석하면 분할정복 최적화 기법이다. 말 그대로 분할 정복을 사용해서 최적화를 시키는 기법이다. When? $DP[i]=\underset{1\leq j\leq N}{min}F(i,j)$ 에서 $DP[i]=F(i,j)$를 만족하는 $j$를$A[i]$라고 할 때, $If..

문제 태그 : https://www.acmicpc.net/problem/3998 문제 소개 N개의 질량조건이 주어진다. 이 중 가장 큰 값과 단백질의 전체 질량이 똑같은 단백질 구조 중 주어진 질량조건에 단백질의 prefix 질량과 suffix 질량이 가장 많이 포함되어있는 단백질 구조를 출력하시오. 예제) 353.16992는 가장 큰 값으로 단백질이 P하나와 Q두개로 이루어져 있다는 것을 알려준다. 이때 구조를 PQQ또는 QQP로 배치하게 되면 P=97.05276 Q=128.05858 PQ=225.11134 PQQ=353.16992 4개로 가장 많은 질량조건을 만족시킬 수 있다. 문제 풀이 일단 몇 가지 관찰을 하는 것이 중요하다. 정말 단순하고 간단한 것 일수 있지만, 하나하나가 정말 강력하게 작용하..