다이나믹프로그래밍26 [leetcode 91] Decode Ways A message containing letters from A-Z is being encoded to numbers using the following mapping:'A' -> 1 'B' -> 2 ... 'Z' -> 26 Given a non-empty string containing only digits, determine the total number of ways to decode it. The answer is guaranteed to fit in a 32-bit integer. Example 1: Input: s = "12" Output: 2 Explanation: It could be decoded as "AB" (1 2) or "L" (12). Example 2: Input: s = "2.. 2020. 11. 15. [백준 2193] 이친수 www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net dp 사용 문제 규칙에 따라 11은 올 수 없고 0으로 시작하는 숫자도 올 수 없다. n = 1일 경우 1 n = 2일 경우 10 n = 3일 경우 101 100 n = 4일 경우 1010 1000 1001 이전 단계에서 0과 1의 개수에 따라 다음 단계에서 만들 수 있는 숫자의 수가 정해지는 걸 확인할 수 있다. 그래서 zero를 저장하는 dp와 one을 저장하는 dp를 따로 만들어줬다. one[i.. 2020. 11. 14. [leetcode 72] Edit Distance Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2. You have the following 3 operations permitted on a word: Insert a character Delete a character Replace a character Example 1: Input: word1 = "horse", word2 = "ros" Output: 3 Explanation: horse -> rorse (replace 'h' with 'r') rorse -> rose (remove 'r') rose -> ros (remove 'e') Example 2: Inp.. 2020. 10. 28. [알고리즘] 최소편집거리 알고리즘 edit distance, Levenshtien distance - 동적프로그래밍을 사용한다. - 서로 다른 문자열 str1과 str2이 같아지기 위해 몇 번의 과정을 거쳐야 하는지 이다. (두 문자열 사이 유사도 측정) - 과정에서 할 수 있는 동작은 insert, delete, replace 아래 3가지이다. 예를 들어 abcdeg를 azcde로 바꾼다면 1. 문자 지우기 : g를 지운다. 2. 문자 삽입 3. 문자 바꿔치기(replace): b를 z로 바꾼다. 가 될 수 있다. 접근방법: 이차원 배열을 사용한다. dp[i][j] dp[i][j]가 의미하는 바는 str1.substr(0,i)와 str2.substr(0,j)사이의 거리를 의미한다. dp[0][0]은 공문자열 사이에서 비교하는 것이기 때문에 거리가 0이다. dp[0][i]는 공문자열과 str.subs.. 2020. 10. 28. 이전 1 2 3 4 5 ··· 7 다음
