다이나믹프로그래밍

[python] 백준 - 11722. 가장 긴 감소하는 부분 수열

🤔문제 해결 S2 | DP 참고(비슷한 유형) : deok2kim.tistory.com/173 [python] 백준 - 11055. 가장 큰 증가 부분 수열 🤔문제 해결 S2 | 다이나믹프로그래밍 역시 이런 문제는 DP문제이다. dp 리스트를 만든다.(1차원, 인풋값으로 받은 수열과 똑같은 값으로 만든다.) 수열에서 자신보다 앞 쪽에 있는 값 중에서 자신 deok2kim.tistory.com numbers에는 수열이 들어있다. dp라는 1차원 리스트를 만든다. (1초 초기화, 감소하는 부분 수열의 길이가 들어갈 것이다.) 1로 초기화한 이유는 혼자만 가능할 때는 길이가 1이므로 numbers를 하나씩 돌면서 자신보다 앞쪽의 숫자와 비교한다. 자신보다 앞쪽의 숫자가 클 경우 - 나와 그 숫자는 감소하는 부..

[python] 백준 - 2410. 2의 멱수의 합

🤔문제 해결 S1 | 다이나믹프로그래밍 유사한 문제 [python] 백준 - 9084. 동전 🤔문제 해결 1. S1 | 다이나믹 프로그래밍 2. target(만들어야 하는 금액)의 길이만큼의 리스트를 만든다. 3. 내가 가진 동전을 하나하나 꺼내서 리스트의 인덱스(내가 만들 수 있는 금액)과 비교하�� deok2kim.tistory.com 동전 문제와 다른 점은 동전은 처음부터 사용할 값이 정해져 있지만 이 문제는 N의 크기에 따라 사용할 수 있는 값이 늘어난다. N이 7이면 1,2,4 이지만 N이 8이면 1,2,4,8 을 사용할 수 있다. 💨 💻소스 코드 def solution(N): nums = [2 ** x for x in range(21)] dp = [0] * (N + 1) dp[0] = 1 fo..

[python] 백준 - 4883. 삼각 그래프

🤔문제 해결 S1 | 다이나믹프로그래밍 최소가중치? 라고 생각해서 별 생각없이 다익스트라로 풀었더니 바로 시간초과 다시 읽어보니 경로가 각 지점마다 단순해서 다이나믹프로그래밍으로 푸는 문제였다. 문제에서 주어진 삼각그래프와 똑같은 크기의 2차원리스트를 만든다. 리스트의 각 요소는 i,j에 도달 할 때의 가장 최솟값을 저장한다. 이제 dp 값을 저장하는 방법을 설명하면 먼저 1행까지는 직접 값을 채워 넣고, 나머지는 for문을 돌린다. (1,0): (0,1)에서 오는 값 (1,1): (0,1), (1,0)에서 오는 값 (1,2): (0,1), (1,1), (0,1)+(0,2) 에서 오는 값 여기서 중요한건 노란색으로 표시한 저 부분이다. 문제에서 각 노드의 가중치는 정수이다. 다시 말해서 음수가 포함되어 ..

[python] 프로그래머스 - 3 x n 타일링

🤔문제 해결 Lv4 | dp 2 x n 타일링 문제와 마찬가지로 dp 문제. 완전 탐색으로 초반 몇 가지 경우의 수를 구한다.(손이나 코드로...) 몇 가지 경우의 수를 가지고 점화식을 세운다. 나는 1번 부분을 하다가 수가 너무 커져 시간이 오래걸릴까봐... 다른데서 가져왔다 나같은 사람을 위해 이제 위의 경우의 수를 가지고 식을 세우면 된다. 규칙성은 무조건 있다 💨 💻소스 코드 def solution(n): answer = 0 dp = [0] * (n + 1) dp[0] = 1 # 아무것도 두지 않는 경우도 1가지 sub = 0 for i in range(2, n + 1, 2): dp[i] = dp[i - 2] * 3 + sub * 2 sub += dp[i - 2] answer = dp[n] % 1..

[python] 백준 - 9658. 돌 게임4

🤔문제 해결 S1 | 다이나믹 프로그래밍 이게임은 거의 선빵필승 구조이다. 특별한 경우만 빼고! 먼저 손쉽게 1~4개일 때의 경우를 구할 수 있다. 돌 1개: 선 - 후공 승 돌 2개: 선, 후 - 선공 승 돌 3개: 선, 후, 선 - 후공 승 돌 4개: 선선선, 후 - 선공 승 다음 5개부터는 점화식으로 구해보자. 돌이 5개일 때 상영이가 돌을 둘 수 있는 경우의 수는 1개, 3개, 4개이다 - 3가지 경우 먼저 상영이가 돌을 1개 뒀다고 하자 그럼 남은 돌은 4개이고 창근이는 선공이 된다. 위의 4가지 경우를 봤을 때 돌 4개에서는 선공이 무조건 이긴다. - 창근 승 다음 상영이가 돌을 3개 뒀다고 하자 남은 돌은 2개이고 창근이는 선공이 된다. 위의 4가지 경우를 봤을 때 돌 2개에서는 선공이 무조..

[python] 프로그래머스 - 단어 퍼즐(2017 팁스타운)

🤔문제 해결 Lv4 | 다이나믹 프로그래밍 풀이 방법은 앞에서 부터 문자 하나하나 선택한다. 'b', 'a', 'n', ... 그 문자로 끝나는 단어가 strs에 들어있는지 확인한다. 있으면 현재까지 썼던 단어 개수(dp[i])와 그 문자를 사용했을 때의 단어 개수를 비교해서 최솟값으로 갱신 (말이 너무 어렵다...) ["ba", "na", "n", "a"] 와 "banana"로 테스트 해보면 맨처음 "b"로 끝나는 단어는 없으므로 pass 다음 "a"로 끝나는 단어는 "a"와 "ba"가 있다. - "na"는 조건에 맞지 않음 "a"를 선택했을 때는 아무일도 없다. why? 처음에 b로 끝나는 단어가 없어서 값이 무한대인 상태 "ba"를 선택하면 1로 갱신해준다. - (단어 하나만으로 "ba"를 만들었다..