Victoree's Blog

Concept & Idea 처음에는 굳이 DP로 풀어야하나?라는 의문이 들어서 그냥 생각대로 풀었다. 수학문제 해결하듯이 풀어낸 코드는 다음과 같다. #include #include using namespace std; int n; int main() { cin>>n; int cnt=0; while(n!=0) { int t=int(sqrt(n)); n-=t*t; cnt+=1; } cout

Concept & Idea 연속합이라고해서 투포인터 개념을 이용해 문제를 해결하려 했는데, 그냥 간단한 이중 포문으로 해결하였다. 처음엔 아무 조건없이 이중포문으로만 해결하니, 시간초과를 마주하였는데 간단한 res>n; for(int i=1; i>map[i]; dp[i]=map[i]; } for(int i=1; i

Concept & Idea 조건은 생각보다 간단하다. 우선 증가하는지 보면되고, dp배열에 여태까지 기록한 가장 큰 증가 부분 수열의 값을 저장해놓으면 된다. 가장 큰 증가 부분 수열을 찾으면, 그 값에 자기 자신을 더한 값을 DP[i]에 저장하면 된다. Code #include using namespace std; int n; int map[1001]; int dp[1001]; int res=0; int main() { cin>>n; for(int i=1; i>map[i]; } for(int i=1; i

Concept & Idea 문제 접근을 어떻게 할까 하다가 앞에 요소를 체크하려 했는데, 결국 과거의 값을 되돌아 생각해보는 것으로 생각해보니 해결되었다. row가 0일 경우에, row가 1이고 && col이 자기 자신보다 -1,-2인 값중 큰 값을 누적하여 더한다.row가 1일 경우에, row가 0이고 && col이 자기 자신보다 -1,-2인 값중 큰 값을 누적하여 더한다. DP배열에는 누적으로 최대값을 쌓아가고, 최종적으로 마지막 col의 최댓값을 출력하면 해결되는 문제였다. Code #include using namespace std; int t; int map[2][100001]; int cnt=0; int dp[2][100001]; int main() { cin>>t; for(int i=0; i..

Concept & Idea 어려운 문제는 아니었다. 우선 이차원 dp[i][j]배열의 첫번째 요소 [i]값은 n자리수를 뜻한다. 또한 두번째 요소 [j]값은 마지막 자리가 0으로 끝나는 수의 갯수, 1로 끝나는 수의 갯수 로 설정해두었다.마지막 자리가 0으로 끝나는 수는 다음자리 수를 만들 때, 0과 1로 두 가지를 더 만들 수 있다.반면, 마지막 자리가 1로 끝나는 수는 11의 문자열을 가질 수 없기 때문에 0만 붙여서 만들 수있다. dp[i][0]=dp[i-1][0]+dp[i-1][1]; dp[i][1]=dp[i-1][0]; 이런 점화식을 만들어낼 수 있던 간단한 문제였다. 배열을 long long 으로 설정해두어야 한다. Code #include using namespace std; long lon..

Concept & Idea 팰린드롬을 다이나믹 프로그래밍을 이용하여 푸는 문제였다. 또한 제한시간이 0.5초로 엄청 빡센 문제였다. 팰린드롬 체크를 단순히 떠오르는 방법으로 하게되면, 양쪽에서 체크하는 N^2만큼의 시간복잡도를 가진다. 그럼 이 문제를 다이나믹 프로그래밍을 이용하여 푸는 법은 무엇일까? 다이나믹 프로그래밍에서 가장 중요한 개념은 메모제이션이다. 또한 메모제이션을 어떻게 할 지 n에 대한 일반식으로 나타내는 것이 중요한 것 같다. 팰린드롬을 이전의 기록을 이용하여 체크할 때, ‘XXX라는 문자열이 팰린드롬이다’ && ‘_XXX_좌우에 붙는 문자들이 같다’ 라면 이 문자열 역시 팰린드롬이 된다. 이 Idea를 이용하여 다음 순서를 생각할 수 있다. 길이가 1인 문자열은 무조건 팰린드롬이다. ..

Concept & Idea 이전에 풀었던 팰린드롬? 의 문제의 코드를 이용해서 문제를 해결할 수 있었다. DP를 두 번에 걸쳐서 이용해야 했다. 일단 DP를 이용해서 i부터 j까지 팰린드롬인지 아닌지를 체크했다. 두번째는 약간 팰린드롬을 체크한 DP배열을 이용해서 분할의 최소값을 구하는 것이었다. D[i] = min(D[j-1]) + 1 이 공식을 생각하는 것이 어려웠다. 이 문제를 풀때 런타임 에러를 두 번이나 실수했다. 우선 팰린드롬? 문제를 풀 때는 인덱스를 1부터 시작했는데, 이 문자열을 0부터 시작하려고 하니까 계속 실수를 하게 되었다. 1. 두번쩨 for문으로 두 글자 팰린드롬을 체크할 때, 문자열 길이만큼 도는데 i와 i+1을 비교해서 실수를 했다. 2. 32번째 줄에 pel[i]>pel[j..