Victoree's Blog

Concept & Idea 나무자르기 문제를 내가 직접 풀어냈다는 느낌이 약해서 리뷰를 쓰지 않았다. 이 문제는 이분탐색으로 가장 인접한 두 공유기의 최댓값을 찾는 문제였다. 처음에는 이분탐색으로 설치를 하는 방식을 짜야한다고 생각했고, 어떻게 적절한 위치에 설치를 할지 우선순위를 잡아야하나 고민하였다. 하지만 그 어떤 우선순위에도 확실한 과정이 없어서, 질문검색을 통해 아이디어를 찾았다. 중요한 점은 내가 직접 구간을 설정해서 이 구간이 가능한지 여부를 판단하고, 이분탐색으로 이 구간을 정해나가는 것이다. mid라는 구간만큼 공유기를 설치했을 때, 설치가 가능하면 mid값을 더 키우고 불가능하면 더 줄여서 최적의 값을 이분탐색으로 찾아나가는 것이다. 여기서 가능한지의 여부는 그냥 count를 세면 됬었..

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