알고리즘 풀이(Problem Solving)/Dynamic Programming 검색 결과

해당 글 27건

알고리즘 풀이 - 백준 17404(RGB거리 2, DP)

관련글 Dynamic Programming 관련 포스팅은 여기를 참조 관련 문제인 1149(RGB 거리) 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 이 문제는 1~N번째 집이 놓여있을 때, 인접한 집이 색이 다르게 색칠하는 경우 가장 최소의 비용으로 칠할 때의 비용을 구하는 문제다. 주목할 점은 1번째와 N번째 또한 같은 색이어서는 안된다는 것이다. 2. 풀이 이 문제는 간단하게 DP로 해결이 가능하다. 인접한 위치의 집과 색상이 다르면 되기 때문에 이전 위치와 동일한 색상으로 칠하지 않는 색 중 가장 최소 비용인 것을 구해나가면 되기 때문이다. 이 문제에서 State는 N개의 집 중 몇 번째에 위치했느냐, 어떤 색으로 칠해졌느냐의 2가..
알고리즘 풀이(Problem Solving)/Dynamic Programming 2021. 1. 17. 01:31

알고리즘 풀이 - 백준 2133(타일 채우기, DP)

관련글 Dynamic Programming 관련 포스팅은 여기를 참조 관련 문제인 11726번(2xN 타일링) 포스팅은 여기를 참조 관련 문제인 11727번(2xN 타일링2) 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 더보기 이 문제는 3xN 크기의 타일을 2x1, 1x2 크기의 타일로 채우는 경우의 수를 구하는 문제이다. 2. 풀이 상단의 관련 문제 포스팅과 달리 이 문제는 3xN이라는 부분이 좀 어려운 부분이다. 3xN 타일을 기본적으로 채우는 방법은 아래와 같이 생각할 것이다. 3x2의 경우를 채우는 경우를 생각해보자. 위와 같은 3가지의 경우는 길이가 무조건 2이다. 이 문제는 타일을 옆으로 계속 채워나가는 방식이고 그 전체 경우의 수를 구하는 문제이기 때문에 이전에 채워진 상태인..
알고리즘 풀이(Problem Solving)/Dynamic Programming 2021. 1. 16. 21:36

알고리즘 풀이 - 백준 13398(연속합2, DP)

관련글 Dynamic Programming 관련 포스팅은 여기를 참조 관련 문제인 1912번(연속합) 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 더보기 이 문제는 배열의 연속합을 구하되 특정 값을 제거하거나 제거하지 않을 수 있는 옵션이 붙은 문제이다. 2. 풀이 우선 문제를 이해하자. 배열 내에서 단순히 값을 몇 개 뽑아서 더하는 것이 아니라 연속합 중 최대의 경우를 구해야 한다. 연속합은 1개만 있어도 연속합이 될 수 있다. 아래와 같은 배열이 있을 때를 예시로 조금만 알아보자. arr[i]는 원 배열이고, sum[i]는 연속합이 최대가 되는 경우의 배열이다. 인덱스 i 0 1 2 3 arr[i] 10 -12 30 -8 sum[i] 10 -2 30 22 sum[i]을 보며 왜 저..
알고리즘 풀이(Problem Solving)/Dynamic Programming 2021. 1. 16. 13:32

알고리즘 풀이 - 백준 11054(가장 긴 바이토닉 부분 수열 ,DP)

관련글 Dynamic Programming 관련 포스팅은 여기를 참조 LIS 관련 포스팅은 여기를 참조 관련 문제인 11053번(가장 긴 증가하는 부분 수열) 포스팅은 여기를 참조 관련 문제인 14002번(가장 긴 증가하는 부분 수열 4) 포스팅은 여기를 참조 관련 문제인 11055번(가장 큰 증가 부분 수열) 포스팅은 여기를 참조 관련 문제인 11722번(가장 긴 감소 하는 부분 수열) 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 더보기 이 문제는 가장 긴 바이토닉 부분 수열을 구하는 문제이다. 2. 풀이 바이토닉의 정의부터 알아보자. 바이토닉 수열은 수열에서 특정 위치의 하나의 값을 기준으로 왼쪽으로는 증가, 오른쪽으로는 감소하는 수열을 이루는 형태를 의미한다. 즉, 1, 2, 3, 2..
알고리즘 풀이(Problem Solving)/Dynamic Programming 2021. 1. 16. 11:32

알고리즘 풀이 - 백준 11722(가장 긴 감소하는 부분 수열, DP)

관련글 Dynamic Programming 관련 포스팅은 여기를 참조 LIS 관련 포스팅은 여기를 참조 관련 문제인 11053번(가장 긴 증가하는 부분 수열) 포스팅은 여기를 참조 관련 문제인 14002번(가장 긴 증가하는 부분 수열 4) 포스팅은 여기를 참조 관련 문제인 11055번(가장 큰 증가 부분 수열) 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 더보기 이 문제는 LIS의 반대로 LDS의 길이를 구하는 문제이다. 2. 풀이 이 문제는 상단의 관련글에서 표기한 LIS 포스팅을 참고하면 쉽다. LIS의 반대인 LDS의 길이를 구하는 문제이지만 단순한 응용이기 때문이다. 이 문제는 기본적으로 DP로 풀 수 있고, 그 보다 더 개선된 시간복잡도를 갖는 방식으로 풀어내는 것도 가능하다. 해..
알고리즘 풀이(Problem Solving)/Dynamic Programming 2021. 1. 16. 01:26

알고리즘 풀이 - 백준 11055(가장 큰 증가 부분 수열, DP)

관련글 Dynamic Programming 관련 포스팅은 여기를 참조 LIS 관련 포스팅은 여기를 참조 관련 문제인 11053번(가장 긴 증가하는 부분 수열) 포스팅은 여기를 참조 관련 문제인 14002번(가장 긴 증가하는 부분 수열 4) 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 더보기 이 문제는 LIS를 구하고 그 배열의 합을 구하는 문제이다. 2. 풀이 이 문제는 상단의 관련글에서 표기한 LIS 포스팅을 보는 것이 더 낫다. 간단히 이야기하여 순차적으로 저장된 데이터가 있는 배열의 부분 배열 중 증가하면서 가장 긴 부분 배열을 구하는 문제이다. 이 문제는 기본적으로 DP로 풀 수 있고, 그 보다 더 개선된 시간복잡도를 갖는 방식으로 풀어내는 것도 가능하다. 해당 내용 또한 상단의 L..
알고리즘 풀이(Problem Solving)/Dynamic Programming 2021. 1. 16. 00:48

알고리즘 풀이 - 백준 1932(정수 삼각형, DP)

관련글 Dynamic Programming 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 더보기 이 문제는 삼각형의 형태로 이루어진 숫자의 배열을 위층 부터 아래층으로 합하면서 내려올 때, 가장 큰 값이 되는 경로의 결과값을 구하는 문제이다 2. 풀이 이 문제는 삼각형의 형태이기 때문에 위층에서 아래층으로 내려오며 선택할 수 있는 경로가 일정하다. 아래의 그림을 보자. 위와 같이 배치를 한다고 하면, 위층에서 아래층으로 영향을 미치는 수는 결국 일정한 규칙을 가진다는 것을 알 수 있다. 여기서 가로 위치를 살펴보면 현재 값에 영향을 미치는 경우는 다음의 경우와 같다. ① 제일 좌측 노드의 경우 같은 가로 위치의 바로 위층의 수에만 영향을 받는다. ② 중간 노드의 경우 같은 가로 위치와 ..
알고리즘 풀이(Problem Solving)/Dynamic Programming 2021. 1. 15. 21:33

알고리즘 풀이 - 백준 2156(포도주 시식, DP)

관련글 Dynamic Programming 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 더보기 이 문제는 N개의 일렬로 놓인 포도주가 각각 양이 같거나 다르게 놓여 있을 때 연속하여 3잔을 마시지 않고 가장 많이 마실 수 있는 경우의 양을 구하는 문제이다. 2. 풀이 이 문제는 기본적으로 DP 문제이다. 포도주를 마시는 경우의 수는 어떤 것일까? 연속해서 3잔을 마시지 말아야 하기 때문에 이전에 어디를 마셨던 것인가를 알고 있어야 한다. 즉, 좌측 부터 마신다는 가정을 할 때, 어디를 마셨는지를 알고 있어야 한다는 의미이다. 그것을 하나의 State라고 볼 수 있을 것이다. 포도주가 총 6잔이 놓여 있다고 가정해보자. 중간에 있는 내역들을 통해 어떤걸 마시는 경우가 있을 지 추측해보자..
알고리즘 풀이(Problem Solving)/Dynamic Programming 2021. 1. 15. 20:45