본문 바로가기
  • 실행력이 모든걸 결정한다
반응형

Algorithm/Dynamic28

[동적계획법] 스티커 모으기(2) - Summer/Winter Coding(~2018) 서로 인접한 요소를 선택하지 않으면서 합이 최댓값이 되는 요소들을 선택하는 유형의 문제다. 프로그래머즈의 도둑질 문제와 동일한 유형의 문제다. 물론 점화식도 같다. https://kimcoder.tistory.com/92 [동적계획법, 난이도 중상] 프로그래머즈, 도둑질 Programmers의 문제들은 난이도별로 다섯 레벨로 나뉘는데, 그 중 Level 4에 속하는 난이도 있는 문제이다. 그래도 백준에서 DP를 50문제 넘게 푼 짬이 있어서 그런지 크게 어렵지는 않았다. 집이 일렬 kimcoder.tistory.com 차이점이 있다면, 도둑질 문제는 입력 배열의 크기가 3 이상으로 정해져 있고, 이 문제는 입력 배열의 크기가 1, 2일 수도 있다는 것이다. 그래서 sticker.size() 값이 1 또는.. 2022. 4. 12.
[동적계획법, 난이도 중하] 백준 11054번, 가장 긴 바이토닉 부분 수열 백준 11053번 가장 긴 증가하는 수열 문제를 응용한 문제이다. [동적계획법, 난이도 중] 백준 11053번 가장 긴 증가하는 부분 수열 제한 시간은 1초며, N의 범위가 (1 ≤ N ≤ 1,000) 으로 좁은 편이기 때문에 O(N^2) 까지 쓸 수 있다. 그래도 이 문제는 1차원 배열의 DP로 풀 수 있다. 첫 INPUT에 대한 DP의 첫 인덱스 값을 1로 두며 시작�� kimcoder.tistory.com 가장 긴 증가하는 수열을 정방향, 역방향 2번 계산하여 해결할 수 있는데 계산 과정은 위 포스팅에 자세히 설명해놨으므로 이 포스팅에선 설명을 따로 하지 않을 것이다. 아래에 예제 입력1 계산표에서 Up행은 가장 긴 증가하는 수열을 적용한 DP이고, Down행은 가장 긴 감소하는 수열을 적용한 DP.. 2020. 10. 12.
동적계획법 고득점 kit 풀이 완료, 후기 코딩 테스트, 대회를 위해 대비해야 하는 필수 알고리즘중 하나이다. 동적계획법은 바로 해답을 구하는 것이 아니고, 이전에 계산했던 값을 활용하는 알고리즘이다. 동적계획법 문제는 대체로 코드가 짧지만 점화식을 세우기 어렵다는 특징이 있다. 백준에서 문제풀이를 제일 많이 했던 알고리즘인 만큼 레벨4(도둑질)에 해당하는 문제도 크게 어렵지 않게 풀었다. 프로그래머즈 문제들 뿐만 아니라 여러 동적계획법을 이용한 문제들도 포스팅 해두었으니 필요하면 참고해도 좋을 것이다. 모든 문제 [난이도 중상] 도둑질 kimcoder.tistory.com/92?category=879353 [난이도 중하] 등굣길 kimcoder.tistory.com/123?category=879353 [난이도 하] 정수 삼각형 kimcoder... 2020. 9. 28.
[동적계획법, 난이도 중하] 프로그래머즈, 등굣길 프로그래머즈의 효율성 테스트에서 숫자가 매우 커지면 실패를 출력한다는 것을 깨달았다. %1000000007을 하지 않았더라도 정확성은 만점이지만, 효율성은 0점이 나온다. 레벨3답지 않게 접근법은 매우 간단하다. dp[x][y] = (1,1) 부터 (x,y) 까지의 최단 경로의 수 맨 처음에는 dp[1][1]을 1로 두고 시작한다. 시작점=도착점이라면 경로의 경우의 수가 1이기 때문이다. 오른쪽과 아래쪽 영역을 탐색해가며 현재 영역의 dp값을 그대로 탐색중인 영역의 dp값에 더해주면 된다. 물론 탐색한 영역에 물이 있다면 더해주지 않으면 된다. 테스트 케이스 10개 정확성, 효율성 모두 만점 #include using namespace std; long long dp[101][101]; bool wate.. 2020. 9. 28.
[동적계획법, 난이도 중상] 프로그래머즈, 도둑질 Programmers의 문제들은 난이도별로 다섯 레벨로 나뉘는데, 그 중 Level 4에 속하는 난이도 있는 문제이다. 그래도 백준에서 DP를 50문제 넘게 푼 짬이 있어서 그런지 크게 어렵지는 않았다. 집이 일렬로 있는게 아니라 원형으로 배치 되어있기 때문에 접근법을 좀 다르게 생각해줘야 한다. 결론부터 말하자면 3가지 경우에 대해 DP를 수행하여 이들 중 최댓값을 구하면 된다. 3가지 경우는 이렇다. 0번째 집부터 터는 경우 1번째 집부터 터는 경우 2번째 집부터 터는 경우 3번째 집부터 터는 경우는 1번째 집을 털 수 있는 상황인데도 털지 않는 경우이므로 최대값이 나올 일이 없다. 케이스별로 DP수행 직전 상황을 그림으로 간략하게 표현하였는데, 회색은 털 수 없는 집이다. 1. 0번째 집부터 터는 .. 2020. 9. 8.
[동적계획법, 난이도 중] 백준 9251번 LCS 두 수열의 부분수열을 찾는 문제이므로 2차원 DP방식을 이용하였다. 예제 입력 1에서 주어진 입력은 ACAYKP CAPCAK 이다. 동적계획법을 이용하여 길이가 작은 문자열~긴 문자열들 순으로 수행해나가면 된다. 맨 처음, 2번째 문자열에서 길이가 1인 "C"를 1번째 문자열과 비교해 나갈 것이다. A 와 C -> 0 AC 와 C -> 1 ACA 와 C -> 1 ACAY 와 C -> 1 ACAYK 와 C -> 1 ACAYKP 와 C -> 1 그 다음, 2번째 문자열에서 길이가 2인 "CA"를 1번째 문자열과 비교해 나갈 것이다. A 와 CA -> 1 AC 와 CA -> 1 ACA 와 CA -> 2 ACAY 와 CA -> 2 ACAYK 와 CA -> 2 ACAYKP 와 CA -> 2 이 순서로 수행해 나간.. 2020. 9. 1.
[동적계획법, 난이도 중] 백준 1699번 제곱수의 합 n을 제곱수들의 합으로 나타낼 수 있는 경우가 여러개 있을 때, 가장 적은 제곱수들을 가지는 경우를 찾으면 된다. 정수 i보다 낮은 정수 j에 제곱수 하나를 더하여 i를 만들 수 있을 때, j값으로는 i-1^2, i-2^2, i-3^2.. 등이 올 수 있다. 각 j값들을 제곱수들의 합으로 표현할 수 있을 때, 이 제곱수 항의 각 최소 개수들의 최솟값에, 특정 제곱수를 의미하는 1을 더하면 이 문제의 답이 나온다. 여기서 특정 제곱수란 j에 어떤 제곱수를 더하여 i를 만드는 그 '어떤 제곱수'를 말한다. 예를 들어서 14를 만들고자 할때 14보다 낮은 정수에 제곱수를 하나 더하여 14를 만들 수 있는 경우는 13+1^2, 10+2^2, 5+3^2 이렇게 3가지 경우가 있다. 14를 제곱수의 합으로 표현 할.. 2020. 8. 31.
[동적계획법, 난이도 중] 백준 2293번 동전 1 동전 i(1≤i≤n)개를 쓰며, j(0≤j≤10) 원을 만드는 모든 경우에 대해 DP를 수행해주면 된다. 예제 입력1에 대해 표를 만들어 보았다. 먼저, 1원 동전으로 0원부터 10원을 만드는 경우의 수는 모두 1이다. 2원 동전으로 0,1원을 만들 수는 없으므로 갱신하지 않고 그대로 1을 따라간다. 2원 동전으로 2원 이상을 만들 때부턴 새로운 경우가 발생한다. 1,2원 동전으로 j-2원을 만드는 경우의 수를 현재 값에 더해주면 되는데, 1,2원 동전으로 j-2원을 만드는 경우들에 2원 동전 하나만 더 추가하면 j원이 완성되기 때문에 이 경우들을 추가해주는 것이다. 1,2,5원 동전을 모두 사용하는 경우에도 똑같이 이를 적용해보자. 5원 동전으로는 5원 이상을 만들 때부터 새로운 경우가 발생한다. 1,.. 2020. 8. 30.
[동적계획법, 난이도 중하] 백준 11057번 오르막 수 만약 끝 자리 수가 j이라면, 다음 자리 수는 j부터 9까지 될 수 있다는 원리를 이용해 DP를 수행하면 되는 문제이다. 오르막 수의 길이가 1인 경우에는, 0부터 9까지 총 10개의 경우의 수가 있다. 즉 길이가 2일 때부터 DP를 수행해주면 되는데, 아래 표에서 설명할 것이다. 아래 표에서 행요소는 자릿수, 열요소는 수의 길이이다. DP[i][j] = 길이가 i인 수에서 i번째 자리의 값이 j인 모든 경우의 수가 되는 것이다. 이 표를 이용하여 답을 구하려면, 각 열 안에 있는 모든 행 요소들을 전부 더하면 된다. 그 것을 아래 표에서는 SUM으로 표시하였다. 최종 출력을 SUM에서 10007로 나눈 나머지값으로 해줘야 하기 때문에 N=7일 경우에는 답으로 11440가 되면 안되고, 1433이 되어야.. 2020. 8. 30.

티스토리툴바