anozanami의 PS 블로그 anozanami의 PS 블로그

접근 : 배열의 원소끼리 관계가 있을거라고 생각했다. 앞의 원소까지의 값에 따라서 그 다음 원소의 값이 결정된다. 전형적인 DP문제이다. 풀이 : DP라는 것을 알고 접근했을 때는 테이블을 현재까지의 연속된 가장 긴/짧은 구간, 점화식을 긴/짧은 것 각각 d1[i+1] = d1[i] + 1, if(arr[i] = arr[i+1]) 로 했다. 초깃값은 d1, d2를 전부 1로 초기화하고 d1[1] && d2[1] == 1, d1[2] && d2[2] == 2 이다. void Solution() { int Answer = 1; int Len = 1; int Len2 = 1; for (int i = 1; i < N; i++) { if (Arr[i] = Arr[i + 1]) Len2++; else Len2 = ..

정의 : DP(Dynamic Programming) 한글로 동적 계획법, 프로그래밍이다. 최적화 이론의 한 기술으로써 특정 범위까지의 값을 구하기 위해 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법이다. 말을 조금 친절하게 하면 기억하며 풀기로 기억해주면 조금 더 좋겠다. (라임 맞춘거 맞다.) 구현 : 문제를 해결하기 위한 점화식을 찾아낸 후 점화식의 항을 밑에서부터 차례로 구해나가서 답을 구한다. 잠시 바킹독의 실전 알고리즘 (DP)편을 인용한다. DP를 푸는 과정은 1. 테이블 정의하기 2. 점화식 찾기 3. 초기값 정하기 로 이뤄져 있다. 코딩테스트에 나올 수준의 DP 문제는 일단 점화식만 찾고나면 그 뒤는 초기 값을 채워넣은 후에 반복문을 돌면서 배열을 채우면 ..