Victoree's Blog

Concept & Idea 어찌됫든 수열이다. 어떻게든 풀어보려고 규칙을 찾으려 했더니 간단한 문제였다. 원래는 dp배열을 2차원으로 만들어서, 변을 공유했는지 안했는지 체크하는 3개의 col을 만드려했는데, 규칙이 보이지 않아서 바로 문제를 다시 읽어보았다. 그랬더니 새로 생성되는 수가 그냥, i-2와 i-3의 합으로 해결된다는 것을 알게 되었다. 왜 범위가 int를 넘어가는지 이해가 잘 안간다. 100밖에 안되는데.. 질문검색에도 어느 순간부터 int를 넘어간다는 대답밖에 없었다. 앞으로 dp문제를 풀고 틀리면 그냥 배열 범위를 바꾸어 봐야겠다… Code #include using namespace std; int t; long long p[101]; int main() { cin>>t; p[1]=1..

Concept & Idea 처음 주어진 32의 타일의 경우의 수가 3개이다. 하나 하나 쪼개서 생각해보면, 맨 처음 타일이 왔을 때 뒤에 3개를 다시 붙이면 다른 경우의 수를 만들 수 있다. 그래서 바로 생각할 수 있는 예시가, 3dp[i-2]이다. 그런데 이 3개만으로 끝나지 않고, 새로운 경우의 수가 2개씩 더 생겨난다. 그래서 2dp[i-4]+ 2dp[i-6]등등을 더해가는 것으로 문제를 해결 할 수 있었다. dp[0]을 1로 초기화해 둠으로 해결할 수 있었다. Code #include using namespace std; int n; int dp[31]; int main() { cin>>n; dp[0]=1; dp[2]=3; for(int i=4; i

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