https://www.acmicpc.net/problem/154831.알고리즘 수업 시간에 배운 근사문자열매칭과 거리함수겠구나2.DP로 해결할 수 있는 문제겠구나근사문자열매칭을 이해하는 데에는 화려한 미사여구 따위는 필요없이, 이 표 하나로 충분하다고 생각한다
오랜만에 돌아온 블로그 포스팅,, 요즘들어 PS를 하면서 느끼는게, 내가 이전에 공부하고 완전히 이해했던 자료구조 / 알고리즘들이 몇개월 지나면 기억이 휘발되어 다시 포스팅들을 찾아보고 있는 내 모습이 너무 바보같았다. 그래서 이왕이면 내가 쓴 글을 보고 다시 떠올리자
지난 포스팅에 이어, 다시 한 번 세그먼트 트리로 돌아왔다. 세그먼트 트리는 특정 구간의 합, 곱, 최솟값, 최댓값을 찾을 때 일반적인 배열에서 찾을 때보다 훨씬 빠른 O(logN)의 시간복잡도를 가진다고 하였다. 그렇다면 세그 트리는 무적이고 나는 신인가? 물론 아니다. 세그트리에도 치명적인 단점이 존재하는데, 바로 값의 업데이트가 느리다는 것이다. 다...