JINWOOJUNG

접근법 처음에는 0번째 부터 수열의 값을 체크 해 가면서 Max값을 다른 변수에 저장하고 해당 변수보다 큰 값이 있다면 Count를 1개씩 증가시키면서 변수를 Update하는 식으로 구현하였다. 너무 쉬운 감이 있었지만 역시 틀렸다. 10 20 5 12 17 30 다음과 같이 순열이 있다고 하자. 그러면 처음 접근법처럼 시도하면 Max = 10, Cnt =1일 것이다.하나씩 주어진 순열과 비교 해 나가면, Max = 20, Cnt = 1이고 그 뒤로 5,12,17은 전부 20보다 작아서 Count 하지 않고, 마지막 30만 Count 되어서 Max = 30, Cnt = 3으로 가장 긴 증가하는 부분 수열의 길이는 3이 된다. 하지만 5, 12, 17, 30 이 더 긴 증가하는 부분 수열로, 길이는 4가 ..

접근법 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 여기서 부분 열은 상대적인 순서를 유지해야 하는데, 예를들어 ACAYKP의 부분 수열은 ACA, ACP, CYK, CAP 등 순서를 유지한 부분 수열이다. DP의 대표적인 문제 중 하나로, 스트링 편집 거리와 유사하게 접근해 볼 수 있다. 위에서 주어진 예시를 이용하면 "ACAYKP", "CAPCAK"의 LCS를 찾아야 한다. 스트링 편집 거리와 같이 한 문자열은 고정시켜 두고, 나머지 하나의 문자열 중 하나씩 증가시키면서 비교 해 보자.  ACAYKPC0  "C"와 "A"의 LCS는 없다. 따라서 0이다. ACAYKPC01..

금일은 다익스트라 알고리즘에 대하여 자세히 알아보자. 다익스트라 알고리즘은 Dynamic Programming을 활용한 최단 경로 탐색 알고리즘이다. 다익스트라를 DP를 활용하여 접근할 수 있는 이유는 최단 경로는 각각의 최단 경로를 포함하고 있기 때문이다. 따라서 이전까지 계산해 둔 최단 경로를 사용하여 하나의 최단 거리를 구한다. 기본적은 다익스트라 알고리즘의 프로세스는 다음과 같다. 1. 출발 노드 설정 2. 출발 노드를 기준으로 각 노드의 최소 비용 저장3. 방문하지 않은 노드 중 최소 비용 노드 설정4. 해당 노드를 경유해서 특정한 노드로 가는 경우를 고려해 최소 비용 갱신5. 2~4번 과정 반복  위와 같은 그래프가 주어졌다고 하자. 각 노드사이로 연결 된 간선은 비용을 의미한다. 각 문제에 ..

문제를 먼저 해석 해 보자. 3XN 테이블에는 양 또는 음의 정수가 주어진다. 각 열에는 적어도 1개의 조약돌을 놓아야 하며, 가로나 세로로 인접한 두 칸에 동시에 조약돌을 놓을 수 없다. 구해야 하는 것은 돌이 놓은 자리에 있는 수의 합을 최대가 되로고 하는 것이다.  결국 최대 비용 문제이다. 그리고, 이전 $i$번째 열에 놓을 수 있는 조약돌의 위치는 이전 열에 영향을 받기 때문에 Dynamic Programming으로 접근하여 재귀식을 도출해야 한다.  그렇다면 각 열에 놓을 수 있는 조약돌의 경우의 수는 뭘까?  위와 같이 총 4가지 경우의 수가 있다. 이를 각가 C1,2,3,4라 하자. 그렇다면 각 경우가 인접할 수 있는 경우의 수는 어떻게 될까? 2가지 제약조건을 고려한 인접 가능한 경우의 ..

접근법 최단경로 찾기에 적용 가능한 Dynamic Programming Algorithm이 바로 Floyd(플로이드)이다. 문제를 보면 특정 도시에서 다른 도시로 가는 서로다른 비용을 가지는 버스가 존재하고, 특정 도시에서 다른 도시로 가는 최소 비용을 구하는 문제이다. 따라서 주어진 문제(경로에 따른 비용)에 대하여 하나 이상의 많은 해가 존재할 때, 최적의 해답을 찾아야 하는 최적화 문제이다.  우리는 주어진 정보 중 출발 도시와 도착 도시 사이의 최소 cost를 원소로 가지는 인접 행렬식 $W$를 포현할 수 있다. 예를들어, $W[i][j]& 는 $i$에서 $j$로 가는 최소 비용을 의미한다. 만약 $i$에서 $j$로 가는 버스가 없다면, 구해야 하는 것은 최소 비용이기 때문에 무한대로 표현하고, ..

접근법또 다시 DP 문제이다. 각 물품에는 Weight, Value가 존재하고, 배낭이 버틸수 있는 Limit Weight는 K로 제한되어 있다. 따라서 목표는 Weight Sum이 K 이하인 최대한의 가치합을 가지는 물건들을 선택해야 한다. 최적성의 원리를 적용하여 해당 문제를 Dynamic Programming으로 해결할 수 있는지 살펴보자.  우리는 위와 같은 Table을 생각할 수 있다. 제한되는 무게에 따라서 각 물품을 담을 수 있는지가 결정되고, 그에 따라서 Value의 최대 합이 달라지기 때문이다. 따라서 해당 Table의 각 원소는 Limit Weight보다 작은 범위에서 고려되는 물품들의의 개수에 따른, 담을 수 있는 물품들의 가치 최대합이 들어가게 된다. 따라서 각 물품들의 Weight..

접근법 연쇄적인 행렬의 곱셈 순서를 결정하는 것은 DP 문제 중 하나로, 효율적은 행렬 곱셈 순서를 결정하는 문제이다. 문제에서 언급 되었듯이 행렬의 곱셈 순서에 따라서 요구되는 계산량이 달라지기 때문에, 곱셈 연산을 최소로 하는 순서를 결정해야 한다. 가장 기본적인 행렬 곱셈의 규칙을 생각 해 보자. $A$ 행렬은 $ i by j $, $B$ 행렬은 $k by l$이라 하면, 행렬 $A,B$의 곱셈 연산이 성립하기 위해서는 $j == k$여야 하며, 계산된 행렬을 $C$라 하면, $C$의 크기는 $ i by l $이 된다.  이러한 규칙을 고려하여, 연쇄 행렬곱셈을 DP를 이용하여 해결하기 위해서 재귀 관계식을 구축하면 다음과 같다. $$d_k = 행렬 A_k의 열의 수  /to  A_k의 행의 수는 ..

문제 접근법 DP 문제이다 직접 해보자. 1 -> 1 -> 1 2 -> 1 + 1 -> 2 3 -> 1 + 1 + 1 -> 3 4 -> $2^2$ -> 1 5 -> $2^2 + 1$ -> 2 = 1 + DP[5- $2^2$ ] 6 -> $2^2 + 1 + 1$ -> 3 = 1 + DP[6-$2^2$] 약간 규칙이 보일 것이다. 자연수 N의 제곱으로 표현되는 1,4,9 등은 1개가 최소이다. N의 제곱으로 표현되지 않으면, 나와 가장 가까운 자연수 N의 제곱을 뺀 DP[] 값에 1을 더해주면 된다. 하지만 예외사항이 발생한다. 23의 경우 위 논리데로 수행하면 DP[23] = DP[7] + 1, DP[7] = DP[3] + 1 = 4이므로 DP[23]은 5이 된다. 이는 넷 혹은 그 이하의 자연수의 제곱의..