[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는 한칸 띄어있는 위치의 최대 값이고 한칸 띄어져 있기 때문에 현재 위치의 배열 값을 더할 수 있다. 이전의 값은 붙어 있기 때문에 현재의 값을 더할 수 없기 때문에 위의 점화식을 사용하면 인접하지 않는 수를 더..

www.acmicpc.net/problem/13707 13707번: 합분해 2 첫째 줄에 두 정수 N(1 ≤ N ≤ 5,000), K(1 ≤ K ≤ 5,000)가 주어진다. www.acmicpc.net 합분해 2 합분해는 몇개의 수 중에 몇개를 선택하여 N의 값을 만드는 문제이다. 여기서 골치아팠던 점은 앞뒤가 바뀌거나 중복되는 숫자가 나와도 되는 점이었다. 배열의 경우 의미하는 값은 dp[만들어야 하는 값][선택 개수]로 생각하고 풀었다. 여기서 dp 점화식을 어떻게 만들 수 있을까? 점화식에 앞서 N 까지의 수 중 선택하여 N을 만들 수 있는 방법은 몇개일까? 우선 dp[1][K]의 경우 K개가 된다. dp[1][1] = {1, } dp[1][2] = { {0, 1}, {1, 0} } dp[1][3..

www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 욕심쟁이 판다 문제는 dfs와 dp를 활용하여 해결하는 문제이다. 한번도 방문하지 않은 점에서만 시작하여 다시 되돌아가며 dp의 value를 업데이트 해준다. 또한 dfs상 모든 정점을 돌게 되면 시간 초과가 발생하기 때문에 dp를 활용하여 중복되는 점이면 바로 return 시켜주저야한다. dp 값을 -1로 초기화 후 다음 정점으로 갈때 마다 1씩 더해준다. 한번도 방문한 적이 없는 값이 면 0을 반환..

www.acmicpc.net/problem/1695 1695번: 팰린드롬 만들기 앞에서 뒤로 보나, 뒤에서 앞으로 보나 같은 수열을 팰린드롬 이라고 한다. 예를 들어 {1}, {1, 2, 1}, {1, 2, 2, 1}과 같은 수열은 팰린드롬 이지만, {1, 2, 3}, {1, 2, 3, 2} 등은 팰린드롬이 아니다. 한 수열 www.acmicpc.net 백준 1695 팰린드롬 만들기 팰린드롬이란 광고의 문구 앞뒤가 똑같은 전화번호와 똑같이 앞과 뒤가 같은 문자열을 뜻한다. 비슷한 문제로 이 문자열이 팰린드롬인지 판단하는 문제는 있었지만 이 문제의 경우 몇개의 숫자를 끼워 넣어야 팰린드롬이 되는지 맞추는 것이다. 우선 팰린드롬이 되는 규칙을 찾아야한다. 1 2 3 4 2 1, 2, 3, 4, 2의 경우 2..