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

특정 값을 이루는데 가장 적은 동전의 개수(Min Number Of Coins For Change) 이번에는 특정 값을 이루는데 가장 적게 사용된 동전의 개수를 구하는 문제를 풀어보겠습니다. 만약 7의 숫자를 구성하는데 이용하는 값들이 [1, 5, 10]이 있다고 치면 만들 수 있는 방법은 1*7, 2 * 5등이 있을 수 있습니다. 1원의 경우 1원의 동전들을 7개 사용해야하니깐 이보다는 2원과 5원을 1개씩 사용하여 답을 구하는 방식이 훨씬 적은 동전을 사용합니다. dp의 의미는 현재 동전을 만드는데 가장 적게 사용 되는 동전의 개수입니다. dp[7] = dp[7-2] + [2]; 위와 같이 dp식을 이루게 해주면 5원을 구성하는 방식, 2원을 구성하는 방식으로 문제를 해결할 수 있습니다. 더보기 #i..

이번 문제의 경우에는 배열안에 있는 여러 개의 숫자를 이용해서 목표하는 값을 만들 수 있는 방법 개수를 구하는 문제입니다. 만약 목표하는 숫자가 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는 한칸 띄어있는 위치의 최대 값이고 한칸 띄어져 있기 때문에 현재 위치의 배열 값을 더할 수 있다. 이전의 값은 붙어 있기 때문에 현재의 값을 더할 수 없기 때문에 위의 점화식을 사용하면 인접하지 않는 수를 더..

팰린드롬이란 앞뒤가 똑같은 문자열인데 이번 문제는 하나의 문자열에서 가장 긴 팰린드롬을 구하는 문제이다. 2번째 문자부터 문자열의 길이가 홀수일 때, 짝수일 때의 인덱스 길이를 비교하여 가장 큰 길이를 구하고 string의 함수인 substr을 사용해서 문자열을 출력해준다. 여기서 홀수일때와 짝수일 때라는 말은 vector oddVector = getPalindorimDorim(str, index-1, index+1); vector evenVector = getPalindorimDorim(str, index-1, index); 팰린들롬을 구하는 부분 문자열의 길이를 짝수로 하나 홀수로 하나의 뜻이다. 예를 들어서 abbbbsserasers 위와 같은 문자열이 있다면 2번째 문자열을 시작으로 ab, abb..

이 문제는 AlgoExpert is the best!의 각 문자를 순서를 유지하며 뒤집는 문제이다. 각 문자의 시작을 체크해서 변수로 저장하고 다음 공백의 점의 인덱스를 저장해서 문자의 시작 인덱스부터 공백의 변수까지의 문자열을 넣어주면 된다. 그리고 양 옆의 각 요소들을 바꾸어 주면서 실행하면 된다. 더보기 using namespace std; void reverseList(vector &list); string reverseWordsInString(string str) { vector words; int startOfWord = 0; for(int idx = 0; idx < str.size(); idx++){ char character = str[idx]; if(character == ' '){ wo..