알고리즘/Dynamic Programming15 [DP] 백준 6603번 로또 (Python) 생각하기 처음 이 문제를 보고서는 브루트포스 문제라고 생각하고 for문을 중첩하여 풀어야겠다고 생각했다 12345678 이면 678을 67, 68, 78 이렇게 for문으로 처리해야지! 하지만 For문으로 처리하려다 보니까 난리도 아니었다.. 너무 코드가 더러워졌다 더러워지면 질수록 이건 틀린거다..! 그래서 다시 뒤엎고 생각을 했다. 다시한번 잘 보니 이 문제는 DFS 문제였다 사실 어떻게보면 DFS도 모든 경우의 수를 들여다 보는 것이기 때문에 크게 보면 브루트포스에 속하긴한다 브루트포스라고 해서 다 for문 돌리는건 아니다! 구현하기 input으로 들어온 각 수를 돌면서 dfs를 하면 된다 depth : 총 여섯자리까지 구하면 되는 것이기 때문에 Dfs에서 깊이는 6까지만 찍고 올라오면 된다 out.. 2021. 10. 16. [DP] 백준 20500번 - Ezreal 여눈부터 가네 - Python 파이썬 생각하기 처음에는 일차원 배열의 DP로 접근을 했었다. N=1,2,3일떄를 써놓고 규칙을 찾아보려해도 아무런 답이 나오지 않았다... 결국 검색을 통해 아이디어를 얻어낼 수 있었다... (아이디어만 봤다.. 아직 실력이 많이 부족.. ㅠ) 1과 5만 사용하기 때문에 기존 숫자에 맨 앞에 1혹은 5를 조합하는 방식이다 예를 들어 1의 자리라면 1, 5가 있을 텐데 앞에 11, 15, 51, 55가 되는 방식! 그렇게 되면 10과 50을 더해주는 것인데 15의 나머지는 10의 나머지 더하기 5의 나머지를 더한 15가 된다 -> 그래서 15는 15의 배수인것이다 (당연한 얘기지만 나머지 관점에서 봤을 떄 15잖아) 두수를 더할 때 두수의 나머지를 더한값과 더한 값의 나머지는 같다 -> 나머지 더한값이 15를 .. 2021. 10. 15. [DP] 프로그래머스 고득점킷 N으로 표현 - Python 파이썬 생각하기 N을 사용한 횟수에 따라 단계를 나눌 수 있다 N을 사용한 횟수에 따라 단계를 나누게 된다면 N을 구하기 위해서는 이전에 구했던 것들을 사용해야 한다. 예를 들어 N을 3번 사용했다면 N을 1번 사용한 경우의 수와 N을 2번 사용한 경우의 수를 합치면 된다 따라서 이 문제는 DP를 통해 풀어보는 것으로 한다 구체화하기 dp[i] 는 N을 i번 사용했을 때 만들 수 있는 수의 집합 ex ) N= 3일 때, dp[1] = { 3 } dp[2] = {33, 6, 0, 9, 1} 따라서 dp[i]를 만들기 위해서는 이전까지의 모든 결과들을 조합하여 dp[i]를 만들어야 함 dp[k] = dp[i] 사칙연산 dp[k-i] (i=1 ~ k-1) 이런식으로 점화식 구성이 가능하지 않을까 싶다 1. 33, 3.. 2021. 10. 10. [DP] Dynamic Programming 동적계획법 이란? 컴퓨터의 연산 속도는 한계가 있고, 메모리 공간도 한계가 있으니 최대한 돌려쓸 수 있는 방법이 없을까? 다음의 조건이 만족하면 DP로 접근해야 한다. 완전탐색으로 답을 찾으려는데 너무 많은 시간이 걸린다 재귀로 진행했을 시에 오버헤드가 났을 경우 DP로 접근해야 하는지 최종적으로 다음 조건을 판단한다 큰 문제가 작은 문제로 나누어진다 작은 문제에서 구해지는 답들이 큰 문제들의 정답 구하는데에 영향을 준다 DP에는 두가지 방식이 있는데 Top-Down (하향식)과 Down-Top (상향식)이 있다 트리 형식으로 생각하고 Top-Down 피보나치 수열을 통해 한번 정리해본다 피보나치 수열 n번째 수는 n-1 번째 수와 n-2 번째 수의 합 1번째와 2번째 수는 1 Top-Down 하향식 방식 구해야할 답을 .. 2021. 9. 27. 이전 1 2 3 4 다음
