백준 알고리즘 강의 후기(코드플러스): 고급으로2 - 다이나믹 프로그래밍5 (DP5)
● 1330 - 다이나믹 프로그래밍 5
트리의 독립집합
그래프의 독립집합은 구할수 없지만, 트리의 독립집합은 다이나믹으로 구할수 있다.
D[V][0]:V가 포함되지않음
사회망서비스(SNS) 얼리어답터 문제
앞의 문제랑 비슷하다.
트리나라
???
1,2,3 더하기 2
k번째를 구하려면 우선 전체 방법의 수를 알아야 한다.
D[n-1]: 1로 시작하는 합의 개수
D[n-2]
D[n-3]: 3으로 시작하는..
K번째 괄호 문자열
D[N][L]: 길이가 N인 괄호 문자열의 개수
L:짝이 맞지 않은 여는 괄호의 개수
L의 값이 음수가 나오는 경우는 올바른 괄호 문자열이 아니다. 한번 짝이 맞지 않아버리면 그 뒤도 계속 짝이 맞지 않기 때문이다.
D[N][L]: 길이가 N인 괄호 문자열의 개수 -> 중에서 짝이 맞지 않은 문자열이 L개
Sequence
3차원으로 풀소도 있고, 2차원으로 풀수도 있다.
무한 수열
피보나치수 구하기랑 비슷하기때문에, 다이나믹으로 풀수있지만, N제한이 너무 커서 메모이제이션 할수가 없다.
꼭 탑다운 방식으로 풀어야 하고, 바텀업 방식으로는 구할수 없다. 왜냐면 위의 제한 때문이다.
재귀로 탑다운 하면서 메모이제이션을 동적으로 맵으로 만들어준다. 맵으로 할때는 맵의 크기가 0이이상이면, 이렇게 하면됨.
무한 수열 2
앞에 문제랑 식이 조금 다름.
큰수를 나누면 많이 작아지고, 작은수는 작아지면 적게 작아진다. 그래서 작은수에서는 중복이 많이 일어난다. 그래서 작은 수 일때만 메모이제이션 한다.
RPG
남는포인트가 매우 중요하다. 그래야 앞으로 올릴수있는지 없는지 알수있기 때문이다.
NP-hard
택배
우체국
가로등 끄기
몇개의 가로등을 껐냐 보다 어떤 가로등을 껐냐가 더 중요하다. 어떤 가로등은 두정수 LR로 표현할수있다.
이사람이 지금 어디에 있는지도 매우 중요한 정보이다.
시리얼 넘버
● 1331 - 다이나믹 프로그래밍 5 (연습)
이친수 찾기
이진수 찾기
괄호 문자열
ntopia
모노디지털 표현
가장 긴 증가하는 부분 수열 ks
● 1332 - 다이나믹 프로그래밍 5 (도전)
암호
워드똑똑
행렬 제곱의 합
채점
팰린드롬
팰린드롬 문장
백준 알고리즘 강의 후기(코드플러스): 기초1 - 다이나믹 프로그래밍1 (DP1)
백준 알고리즘 강의 후기(코드플러스): 중급2 - 다이나믹 프로그래밍2 (DP2)
백준 알고리즘 강의 후기(코드플러스): 중급3 - 다이나믹 프로그래밍3 (DP3)
