[Python-이론/python-인공지능] - 레벤슈타인 거리를 이용해서 두 문장 비교하기 레벤슈타인 거리를 이용해서 두 문장 비교하기 레벤슈타인 거리를 이용해서 두 문장 비교하기 레벤슈타인 거리는 독일의 레벤슈타인이라는 사람이 고안한 알고리즘이다. 레벤슈타인 거리란 두개의 문장을 2차원 배열로 나타내어서 각 문장 hoony-gunputer.tistory.com 예전에 이런 글을 적은 적이 있는데 까먹고 잊고 살다가 최근 문제에서 만나면서 다시 풀어보게 되었다. 저 당시에는 dp도 몰랐는데 문제를보고 정리한거 같다. 레벤 슈타인 거리의 경우는 두개의 문자열을 어떻게 변형해주면(삭제, 교환, 덧셈) 등을 진행해줄 때 최소한 몇개의 변화를 통해서 만들 수 있는지 구하는 것이다. dp의 값은 해당 위치의 문자..

이번 문제의 경우에는 배열안에 있는 여러 개의 숫자를 이용해서 목표하는 값을 만들 수 있는 방법 개수를 구하는 문제입니다. 만약 목표하는 숫자가 6이고 이를 만드는데 사용할 수 있는 숫자가 [1, 5]라고 하면 구할 수 있는 방법 은 1 * 6, 1 + 5 가 될 수 있습니다. 1을 6개를 사용하거나 1과 5를 더해서 구하는 것이죠. 이번 Dp가 의미하는 것은 해당 돈(인덱스)을 만들 수 있는 방법입니다. 얘를 들어서 dp[1] = 1원일 때 만들 수 있는 방법 dp[2] = 2원일 때 만들 수 있는 방법 dp[3] = 3원일 때 만들 수 있는 방법입니다. 이 때 지정해준 동전을 사용해서 돈을 만들어야 하니 dp[i] += dp[i-지정해준 동전]이 됩니다. 즉 dp[6] += dp[6-1] 1원은 한개..

한 배열안에 있는 인접하지 않는 숫자들의 최대합을 구하는 문제를 풀어보겠습니다. 여기서 인접하지 않는 가장 큰 최대합은 75, 120, 135입니다. 이를 구하기 위해서는 dp를 활용해야하는데 이전의 정보를 활용하면 편하게 진행할 수 있습니다. array = [75, 105, 120, 75, 90, 135]; dp[i] = max(dp[i-1], dp[i-2] + array[i]); 각 dp의 배열은 현재 위치의 최대 값을 의미한다. i는 현재의 위치를 의미하고 i-1은 이전의 최대값그리고 i-2는 한칸 띄어있는 위치의 최대 값이고 한칸 띄어져 있기 때문에 현재 위치의 배열 값을 더할 수 있다. 이전의 값은 붙어 있기 때문에 현재의 값을 더할 수 없기 때문에 위의 점화식을 사용하면 인접하지 않는 수를 더..