전체 글
A log of my development (and other various stuff)2024.02.10
취준 CV 및 경력기술서 업데이트 각 채용 사이트에 변경 내용 반영 B사, D사 지원 인프런 '습관부터 바꿔주는 Node.js & Express 기초' 수강 0/81 -> 25/81
Levenshtein distance
Levenshtein distance, 혹은 Edit distance로 불리는 알고리즘은 하나의 string을 다른 string으로 바꾸는데 필요한 최소 연산 횟수를 구하는 알고리즘이다. 이 때 연산이란 삽입(add), 삭제(delete), 수정(replace) 세 가지의 종류를 의미한다. Levenshtein distance의 점화식은 다음과 같다. a, b는 각 string을 의미하며 leva,b(i, j)는 a의 [0, i] substring에서 b의 [0, j] substring까지의 최소 연산 회수 계산 값을 의미한다. 위 수식을 이해하기 위해 몇 가지 케이스에서 점화식에 어떻게 적용되는지 살펴보자. 1. i = 0이거나 j = 0인 경우 간단하게 i=0인 경우를 살펴보자. [0, 0] subs..
2024.02.09
Leetcode Top Interview 150 Multi dimensional DP 앞 6문제 DP 문제에서 메모이제이션을 할 때 가능하면 Map보단 Array를 사용하는게 시간 측면에서 좋다. Levenshtein distance 정리 푼 문제 리스트 120. Triangle 64. Minimum Path Sum 63. Unique Paths II 5. Longest Palindromic Substring 97. Interleaving String 72. Edit Distance
2024.02.08
Leetcode Top Interview 150 1D DP top-down보단 bottom-up을 사용하자. 시간 면에서 우위에 있다. 푼 문제 리스트 70. Climbing Stairs 198. House Robber 139. Word Break 322. Coin Change 300. Longest Increasing Subsequence
2024.02.07
Playground Project 홈 화면 스타일링 완료 사이트에 대한 간단한 설명 추가 개인 링크 추가 자잘한 오류 수정 Leetcode Top Interview 150 Math 문제 자체는 간단해 보일지라도 계산 수가 많아 시간 복잡도에서 문제가 되는 경우가 있으므로 항상 주의 수식을 직관적으로 풀어내려면 부동소수점 오류로 인해 등호가 성립 안되는 경우가 있다. 혹시 모르니 직접적으로 값이 같은지 비교하는 것은 조심하자. 푼 문제 리스트 9. Palindrome Number 66. Plus One 172. Factorial Trailing Zeroes 69. Sqrt(x) 50. Pow(x, n) 149. Max Points on a Line