목록2024/10 (8)
미소를뿌리는감자의 코딩
1. 문제https://www.acmicpc.net/problem/10844 2. 접근 방법이번 문제의 경우, 처음에 dfs와 memoization으로 접근하였다.하지만, 약점인 dp를 극복하기 위해 고른 문제인 만큼 다시 dp로 접근하려고 노력 하였다.dfs의 길이 보이니, 역으로 dp를 생각하는 것이 까다로웠다. 점화식을 세워보았다.f(i-1, n) + f(i+1, n) = f(i, n+1) 1 -> 0, 2가 올 수 있고, 2 -> 1, 33 -> 2, 44 -> 3, 55 -> 4, 66 -> 5, 77 -> 6, 8 즉 앞 뒤로 값이 올 수 있으므로, 위와 같은 점화식을 세워주었다. 이제 n이 1일 때의 식을 세워주었다.2차원 배열로 보았을 때, 아래와 같은 모양을 나타낸다. 0 1 ..
1. 문제https://www.acmicpc.net/problem/11055 2. 접근 방법처음에는 위와 같이 구상하였다.현재 idx에서 이전 idx를 비교를 하면서 0번 idx까지 내려간다. 만약 값이 현재 idx value 보다 작다면, max(inc[idx], inc[idx] + arr[i])를 진행해준다. max를 이용하는 이유는 더 앞에서 현재 값보다 더 큰 값을 지니고 있는 증가하는 수열이 있을 수 있기 때문이다. 처음에는 현재 idx보다 작은 값을 찾으면 바로 값을 더해주고 break를 해주었다.하지만[10, 22, 9, 33, 21, 50, 41, 60, 80][1, 2, 1, 2 ### 3 이 들어가야 함.증가하는 수열의 길이를 파악하는 과정을 보면, 만약, 현재 idx보다 작을 시, b..
1. 문제https://www.acmicpc.net/problem/2098 2. 접근 방법https://www.geeksforgeeks.org/travelling-salesman-problem-using-dynamic-programming/ Travelling Salesman Problem using Dynamic Programming - GeeksforGeeksTravelling Salesman Problem (TSP): Given a set of cities and distance between every pair of cities, the problem is to find the shortest p ossible route thatwww.geeksforgeeks.org 내가 사랑하는 긱스 뽈 긱스,..
1. 문제https://www.acmicpc.net/problem/11049 2. 접근 방법https://www.youtube.com/watch?v=Tdl6VP4bS90 이 문제는 행렬의 계산 횟수를 구하는 문제이다. 위 영상이 이해에 큰 도움을 주었다.그림으로 설명하기 위해 아래 그려 보았다.(ABC)(DEFGH) 로 묶었다고 가정하였을 때, 계산 횟수는 z * c* h 가 된다. 즉, 이를 list를 이용해서 표현해 보면, row[x] * column[k] * column[y] 이다. 이후, 재귀적으로 ABC에 대해서, 그리고 (DEFGH)에 대해서 탐색해야 하므로이를 다시 dfs에 범위를 재설정하여 넣어준다. 탈출 조건은 x와 y가 같은 값을 지닐 때, 이다.또한 memoization을 사용해 주어..