DP10

• 

  [c++] 백준 - 도로 네트워크(lca) 1. 문제 2. 입 출력 3. 예제 4. 문제 해설 이 문제는 lca를 이용한 문제였다. 문제 자체에서 가장 root노드가 무엇인지 주진 않았지만 1번 노드를 root로 삼아 (왜냐하면 1번 노드는 항상 나오기 때문이다.) 트리를 구성하고 그 후 효율적인 lca풀이를 이용하면 충분히 구할 수 있는 문제이다. 이 문제는 또한 lca를 구성하는 과정에서 구간의 최댓값과 최솟 값을 저장하며 가야하는 문제이다. 따라서 dp문제의 성향이 강하다고 할 수 있겠다. 우선 효율적인 lca 풀이를 위해 tree를 구성해준다. 나는 bfs를 통해 트리를 만들어주었다. void makeTree() { depth[1] = 1; q.push({ 1 }); while (q.size()) { int curr = q.front();.. c++/알고리즘 2023. 3. 3.

• 

  [c++] 백준 - 케이크 자르기2 10714 1. 문제 2. 입 출력 3. 예제 입출력 4. 문제 해설 dp의 문제이다. 백준 - 카드게임 문제와 비슷하다. 이 문제는 직접 게임의 형태를 구현하는 방향으로 dp를 구성해야했다. 우선 문제를 읽어보면 ioi와 joi가 번갈아가면서 케이크를 가져간다. 하지만 ioi의 경우에는 둘 중 더 큰 조각만을 가져간다. 무조건 정해져있는 것이다. 하지만 이 경우 greedy처럼 더 큰 것만을 가져간다고 더 최적의 결과가 보장되는 것은 아니다. 따라서 joi가 가져갈 때는 dp값을 통해 더 좋은 결과를 가져가야한다. 또한 재귀를 이용해 dp를 구성해야한다. 우선 환형태를 어떻게 구현해야하는 지에 대해 고민을 해보았다. 2가지 방법이 떠올랐었는데 하나는 2 5 7 8 10의 조각이 있을 경우 2 5 7 8 10 2 .. c++/알고리즘 2023. 2. 27.

• 

  [c++] 백준 - 11066 파일 합치기 (dp) 1. 문제 2. 예제 입출력 3. 문제 해설 다이나믹 프로그래밍 문제이다. 나는 한 번 최소의 값을 구하는 과정을 생각해보았다. 내가 풀어본 대부분의 dp문제 중 이 문제는 dp[x][y]를 x번째에서 y번째까지의 파일 합치기의 최소값을 기억해두는 문제였다. (백준-전구)에서 사용한 dp배열과 비슷하다. 대부분 이렇게 x ~ y에서의 최소 값을 dp배열에 저장하면 중간에 k라는 구간을 두어 for문을 반복하며 최소 값을 찾아내는 형태로 많이 나온다. 이 문제 또한 동일했다. dp문제 정의 dp배열 정의 : dp[x][y] : x번째 파일에서 y번째 파일까지 합치기의 최소 값 점화식 : dp[i][i+j] = min(dp[i][j] , dp[i][k] + dp[k+1][i+j]) k 는 i부터 i+j-1까.. c++/알고리즘 2023. 2. 14.

• 

  [c++] 백준 - 1520 내리막길 (DFS + DP) 1. 문제 2. 입출력 및 예제 3. 문제 해설 상하좌우가모두 탐색이 가능하다. 그리고 제약조건이 존재한다. 바로 현재 위치보다 낮은 수로만 이동할 수 있다는 점이다. 기본적으로는 dfs탐색을 해야할 거 같았다. 결국 자신의 네 방향 중 자신보다 낮은 수가 존재한다면 이동 횟수는 상관없이 이동할 수 있는 것이고 결국 오른쪽 맨 아래 칸에 도달할 수 있는 지에 대한 여부가 중요했기 때문이다. 따라서 나는 상태를 3가지로 나누었다. -1 : 아직 방문하지 않은 곳이다. 0 : 방문한 경우이다. 0보다 큰 수 : 현재 지점에서 목적지까지 도달 할 수 있는 경우의 수가 존재하는 곳이다. 처음에는 이 문제를 백트래킹으로 접근했는데 시간초과가 났다. 물론 4가지 방향 ^ (500 * 500)이 최악의 경우라 당연히.. c++/알고리즘 2023. 2. 14.

• 

  [c++] 백준-행렬곱셈순서 (dynamic programming) 1. 문제 2. 입출력 및 예제 3. 문제 해설 dp문제이다. 그리고 여태까지 dp배열을 채우던 방식과는 조금 다른 형태이다. 대부분의 dp문제에서는 가로 방향으로 dp배열을 채우거나 세로 방향으로 dp배열을 채워갔다. 하지만 이 문제는 대각선으로 채워가야하는 문제이다. dp문제를 풀 때는 세 가지 과정을 거쳐야한다고 했다. dp 배열의 정의 점화식 찾기 초기값 설정 나는 dp[i][i]를 i번째 배열에서 j번째 배열까지의 곱셈 연산 최소 횟수로 정의했다. 내가 생각한 점화식은 다음과 같다. 우선 행렬곱셈에 대해 알아보면 5 * 3 , 3 * 2, 2 * 6과 같이 세 행렬이 존재할 때 1번째로 가능한 곱셈의 경우는 앞의 두 행렬을 먼저 계산하고 마지막 행렬을 계산하는 것이다. 2번째로 가능한 곱셈의 경.. c++/알고리즘 2023. 2. 9.

• 

  [c++] 백준-LCA2 (Least Common Ancestor) 1. 문제 2. 입출력 및 예제 3. 문제 해설 백준 - lca와 문제는 같다. 그러나 달라진 점이 있다면 노드의 개수가 10000개로 늘었다. 그리고 알아내야하는 노드의 쌍의 수도 늘었다. 이 문제는 그러면 이전 lca문제처럼 bfs나 dfs로 tree의 depth를 알아낸다. depth가 더 큰 쪽을 parent배열을 이용해 작은쪽과 depth를 맞춘다. 한칸 씩 올리다가 만나는 것이 lca에 해당한다. 위의 알고리즘을 사용하면 시간초과가 나게 된다. 그래서 이 문제는 dp를 적용해 lca + dp를 사용해야한다.... 어떤 문제건 두 가지 알고리즘이 섞이면 어렵지만 이 두개는 어려운 것이 두 개가 섞여 더 어려웠다. 한 번에 풀지는 못하고 이 문제의 핵심 아이디어를 찾아 본 후 구현할 수 있었다. .. c++/알고리즘 2023. 2. 8.

• 

  [c++] 백준-퇴사2 (dynamic programming) 1. 문제 2. 입출력 3. 문제 해설 이 문제는 그냥 퇴사와 퇴사2가 존재한다. 두 문제는 완전 같은데 다른 점이 하나 있다. 바로 N의 범위가 1000에서 1500000으로 늘어났다는 점이다. 이는 완전탐색으로 O(N^2) 시간 복잡도가 가능했었는데 N이 증가함에 따라 완전탐색 알고리즘은 사용하지 못한다는 뜻이다. N의 범위가 1500000으로 늘어났으니 가능한 알고리즘 시간 복잡도는 O(N) or O(NlogN)정도가 되겠다. 그러면 가자 대표적인 것이 dp-> dynamic programming을 이용해보기로 했다. 위와 같이 dp를 사용해보기로 한 것은 이전 값의 입력들이 그 다음 입력에 영향을 미치는 관계가 있다고 생각이 들었기 때문이다. 1일차의 상담을 선택하거나 선택하지 않을 수 있는데 이.. c++/알고리즘 2023. 2. 1.

• 

  [C++] 백준 - 전구 문제 2. 입출력 3. 문제 해설 문제를 읽어보면 최대 K가지의 서로 다른 색을 표현할 수 있는 전구들이 존재하고 이 전구 N개를 한 줄로 배치한다. 한 줄로 배치한다는 것은 고리 형태가 아닌 자신의 양 옆의 전구만이 자신에게 영향을 줄 수 있다는 뜻이다. 또한 임의의 전구를 하나 잡아 색을 바꾼다. 그런데 이 임의의 전구와 인접한 전구가 같은 색이라면 이 전구 또한 색상이 변한다. 그러면 이 문제는 최소 문제로 쪼갤 수 있다. 바로 옆의 전구가 변했을 때 색이 같다면 변하고 색이 다르다면 변하지 않는 것이다. 그러면 이 문제는 dp를 적용해 memoization 해 가면서 풀 수 있을 거 같다고 생각했다. 이 문제에서 제일 까다로운 점은 임의의 전구부터 시작할 수 있다는 점이다. 또한 dp를 이용하려면.. c++/알고리즘 2023. 1. 30.

• 

  [c++] 백준-제단 5626 문제 입력과 출력 사실 이 문제를 풀 때 DP를 이용해서 푸는 문제라는 것을 알고 있었기 때문에 쉽게 접근할 수 있었다. (물론 난이도 자체는 어렵다 매우) DP는 점화식을 세우면 끝나는 문제다. 문제를 파악해보면 다음과 같다. 문제 해설 우선 제단을 세울 수 있는 경우를 생각해보았다. x 가능 가능 x x 가능 가능 가능 가능 x 점화식은 대부분 memoization된 이전 상태에서 현재의 값을 찾아낼 수 있기에 두 가지의 경우만을 고려해보았다. 2층의 가능한 경우는 1층의 경우에 따라 가능할 수도 불가능할 수도 있다. 따라서 이는 현재 상태가 이전 관계에 영향을 받는 점화식으로 풀 수 있는 DP문제이다. 그렇다면 현재 상태는 이전 상태의 어떠한 영향을 받을까? 다음 세 가지 경우가 있을 수 있다. 현.. c++/알고리즘 2023. 1. 25.

• 

  [c++] Floyd의 알고리즘 - 가중치가 다른 길찾기 문제는 다음과 같다. 가중치가 같은 최단 경로의 알고리즘으로는 BFS를 사용할 수 있지만 이 같은 경우에서는 경로마다 가중치가 다르기 때문에 BFS로 접근하면 안된다. 대신 DP 다이나믹 프로그래밍을 사용하여 부분 최적해를 구해가며 진행할 수 있겠다. 1. map만들기 우선 배열에 map을 만들어주어야 한다. 이 때 중요한 것은 갈 수 없는 방향에 대해서는 infinite한 값- 매우 큰 값으로 이루어져야 한다는 것이다. 따라서 위의 그래프를 이용해 map을 만들면 다음과 같다. int w[6][6] = { {0,0,0,0,0,0}, {0,0,1,1000,1,5}, {0,9,0,3,2,1000}, {0,1000,1000,0,4,1000}, {0,1000,1000,2,0,3}, {0,3,1000,1000,.. c++/알고리즘 2022. 5. 25.