Victoree's Blog

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..