TIL_20230226

오늘 할 일

• LeetCode 데일리 문제 풀기
• OAuth2 적용해보자!

오늘 배운 것

LeetCode 데일리 문제 풀기

• 오늘의 문제: 72. Edit Distance(https://leetcode.com/problems/edit-distance/)
• 문제 조건
  • word1에서 word2를 만든다고 할 때, 최소 수행 횟수를 찾는 것입니다.
  • 단, 문자를 삽입하거나, 삭제하거나, 대체하는 연산만 가능합니다. (Insert, Delete, Replace)​
• 문제 해결
  • LCS(Longest Common Substring/Subsequence) 응용 문제입니다.
  • LCS는 두 문자열 또는 수열에서 공통적으로 만들 수 있는 문자열 또는 수열을 구하는 알고리즘입니다.
  • LCS의 경우, 공통 문자열/수열이 나오면 값을 1만큼 증가시켜주고 다른 문자열/수열의 경우는 dp 테이블에서 위, 왼쪽에 있는 값 중 최댓값을 가져옵니다. 최댓값인 이유는 현재 비교하고 있는 값 이전에 만들어 놓은 공통 문자열/수열의 개수를 정확히 체크하기 위해서입니다.
  • 이 문제에서는 LCS와는 정 반대로 생각할 수 있습니다.
  • 공통 문자열이 나오는 경우에는 이전에 생긴 공통 문자열을 그대로 삽입합니다. dp[i][j] == dp[i - 1][j - 1]
  • 값이 다른 경우에는 문제에서 제시한 연산 중 하나를 사용한다고 할 때, 최소 연산 횟수를 구하고 있으므로 dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1] 중에서 가장 작은 값을 1만큼 증가시켜줍니다. 최솟값을 사용하는 이유는 공통 문자열에서 최소한의 연산만을 수행해야 하기 때문입니다.

OAuth2...

• 오늘 반 정도는 해놓으려고 했는데, LeetCode 문제가 생각보다 많이 어려워서 시간을 다 뺐겼습니다.. ㅠㅠ 약속도 있어서 오늘 못했습니다. 내일 하루 종일 하려고 합니다!

느낀점

• LCS라는 알고리즘에 대해 알게된 날이었습니다. dp를 제대로 사용한 적이 없어서 이해하는 데에 더 오래 걸렸습니다.
• 기본적으로 코딩테스트에 나오는 알고리즘은 꼭 다시 공부해서 여러 방법으로 익숙해져야겠습니다!!
• 내일은 OAuth2 구현을 위한 하루가 되겠습니다...!

내일 할 일

• LeetCode 데일리 문제 풀기
• OAuth2 구현