알고리즘74 [DP] 백준 1757번 - 달려달려 DP를 안 쓴다면) 매분 달릴지 말지를 결정하는 완전 탐색을 진행해야 한다. 2^N이 되는데 N DP? DP를 쓴다면) 상태 3가지 존재 1. 몇분 2. 지침 지수 3. 달리는 상태 dis[n] -> 각 시간에서의 갈 수 있는 거리 dp[x][y][z] -> '최대한 갈 수 있는 거리'로 dp를 설정 x : 분 y : 지침 지수 z : 달리는 상태 (1:달림 0:쉼) M은 2라고 가정 지침지수 0인 경우 y=0) dp[x][y][0] = max( dp[x-1][y+1][0], dp[x-1][y+1][1], dp[x-1][y][0] ) 지침지수 1인 경우 y=1) dp[x][y][0] = max( dp[x-1][y+1][0], dp[x-1][y+1][1] ) y-1에서 값을 가져올 수 없는 이유 >> y-.. 2021. 2. 5. [DP] 백준 15988번 - 1, 2, 3 더하기 3 생각하기 20을 나타내는 방법의 수 = 4를 나타내는 방법의 수 x 16을 나타내는 방법의 수 각 숫자 나타내는 방법의 수 구하는 방법 = 백트레킹? 하짐나 DP로 풀어야 하는 문제이기 때문에 DP적으로 생각! dp[num] = dp[num-1] + dp[num-2] + dp[num-3] 마지막에 각 단계에서 부족했던 숫자들만 더해서 값을 뽑을 수 있다 1을 구하는 방법에서 2을 더하는 방법 2를 구하는 방법에서 1을 더하는 방법 이미 구해 놓은 값들을 통해 구해낸다 * 각 숫자 때마다 dp값을 도출하기 #include #include #include #include #include #include #include #include #include using namespace std; #define end.. 2021. 1. 28. [DP] 백준 2748번 - 피보나치 수 2 case1) n이 0 혹은 1일 때, 0 / 1을 출력 case2) n이 2이상 일 때, memoizate해 놓은 이전 두개의 수를 더한 수를 출력 하지만 이런식으로 진행한다면 시간초과가 발생한다 memoization을 사용하여 연산을 최대한 줄여야 한다 #include #include #include #include #include #include #include #include #include using namespace std; #define endl '\n' int N; long long fib[100]; long long pibo(int n) { if(n==0){ return 0; } if(n==1){ return 1; } if(fib[n]!=-1) return fib[n]; else{ fib[.. 2021. 1. 25. [Back Tracking] 백준 9663번 - N Queen 완전탐색을 한다면? N = 14일때, 14x14의 요소중에서 14개를 뽑는 것이기 때문에 256^14가 된다 제한 시간은 10초(10^9)이기 때문에 초과한다 -> Back Tracking 으로 풀어야 한다 2차원 배열에서 알아두면 좋은 점 col이 i, row가 j라고 할 때 생각 처음에는 15*15 배열을 만들어 놓고 아래의 규칙에 따라 퀸이 배치된 칸 퀸이 배치된 칸의 모든 아래 칸들 퀸이 배치된 칸의 왼쪽 대각선 아래 칸들 퀸이 배치된 칸의 오른쪽 대각선 아래 칸들을 모두 false 처리 했다 하지만 이렇게 하는 경우 문제가 있다 빨간색이 파란선과 겹치면서 파란색을 원상복귀 시켜놓는다. 이러한 경우를 방지하기 위해서는 각 케이스를 독립적이게 분리할 필요가 있다. 2차원 배열에서의 인덱스들의 특징을.. 2021. 1. 25. 이전 1 ··· 14 15 16 17 18 19 다음
