스트링 편집 거리(string edit distance) 알고리즘이란 두 문자열의 유사도를 측정하기 위해 사용되는 알고리즘으로 Levenshtein distance(LD)라고도 합니다. 스트링 편집 거리 알고리즘은 논문, 보고서 등의 표절 검사, DNA 염기 서열의 유사도 검사 등에 사용되어지는데요. 두 문자열의 유사도는 S: 원래 스트링 T: 비교 스트링이라 했을 때 S -> T로 변환하는데 필요한 삽입, 삭제, 대치 연산의 최소 비용(최소 편집 횟수)을 구함으로써 판단합니다. (비용이 작게 나올수록 유사도가 큼) 만약 GUMBO라는 단어와 GAMBOL이라는 단어의 편집 거리를 구해보면, U -> A로 대치 (비용 +1), 맨 마지막에 L 추가 (비용 +1)로 편집 거리는 2가 되게 됩니다. (삽입, ..
오늘은 ARC 즉, Automatic Reference Counting에 대해 정리해보려 합니다. ARC란? - Swift는 ARC를 활용해 앱의 메모리 사용을 추적하고 관리합니다. 인스턴스가 더 이상 필요하지 않으면 메모리에서 해제합니다. 그렇기 때문에 우리는 메모리 관리에서 비교적 자유로워질 수 있죠 ㅎㅎ 하지만, 강한 참조로 순환이 이루어질 때는 메모리 누수가 발생할 수 있기 때문에 우리가 적절한 조치를 해줘야 합니다. 지금은 무슨 말인지 잘 모르겠어도 뒷부분에 설명할 예정이니 걱정 안 하셔도 됩니다! 작동 방식 - ARC는 각 인스턴스가 얼마나 참조되고 있는지를 추적하고 저장함으로써 메모리 관리를 합니다. 만약 참조 counting이 1 이상이면 인스턴스는 메모리에 계속 남아 있고 0이 되었을 때..
동적 계획법 - 주어진 문제를 여러 개의 소문제로 분할하여 각 소문제의 해결안을 바탕으로 주어진 문제를 해결, 이때 각 소문제는 다시 또 여러 개의 소문제로 분할 가능하다. 각 소문제는 원래 주어진 문제와 동일한 문제이지만 입력의 크기가 작다. 여러 개의 소문제로 분할하여...??? 응?? DP를 처음 공부하신다면 이게 무슨 말이지? 이해가 잘 안 가실 수 있으실 텐데요. 그래서 하나의 좋은 예시가 있습니다 ㅎㅎ 바로 피보나치 수열인데요. 피보나치 수는 1, 1, 2, 3, 5, 8... 로 다음과 같은 점화식으로 나타낼 수 있습니다. 이제 이런 피보나치 수열을 다음과 같이 분해해서 트리 형태로 나타내 보면, 소문제가 상위 문제를 해결하기 위해 사용되는 것을 볼 수 있습니다. 이 말이 즉, 위에서 설명한..