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..
최대 부분합을 구할 때 O(log n)의 시간 복잡도로 계산할 수 있는 알고리즘이다. 최대 부분합이란 배열의 연속 부분 집합 중 그 합이 가장 큰 것을 의미한다. 예를 들어, [-2, 1, 3, -1, 2, -6, 3, 1]의 배열에서 최대 부분합은 [1, 3, -1, 2]이다. Kadene's algorithm은 특정 index를 포함하는 그것까지의 부분합이 두 가지 방법으로 계산될 수 있음을 이용한 것이다. index - 1 까지의 부분 합이 양수인 경우: 이전 부분 합 + 현재 값 index - 1 까지의 부분 합이 음수인 경우: 현재 값. 위 예시의 배열로 각 index에서의 부분합을 구해보자. (prev: 이전 부분 합 배열, cur: 현재 부분 합 배열, sum: 현재 부분 합) [ -2, ..
# Binary Search Tree 번역하자면 이진탐색트리이며 줄여서 BST라고 부른다. BST는 말 그대로 binary search를 더 효율적으로 하기 위한 트리 자료 구조이다. 삽입, 삭제, 조회의 시간 복잡도는 모두 O(log n)이다. BST의 특징 1. 각 노드는 0 ~ 2개의 child node를 가진다. 2. 노드의 왼쪽 서브 트리의 값들은 항상 노드보다 작다. 3. 노드의 오른쪽 서브 트리의 값들은 항상 노드보다 크다. 4. 트리 내 중복되는 값은 없다. 삽입 삽입할 값을 root node부터 순차적으로 비교하며 삽입 값이 더 작은 경우에는 왼쪽, 큰 경우에는 오른쪽으로 이동한다. 이동 중 빈 자리를 발견하면 그 곳에 삽입한다. 아래 트리에 '3'을 삽입한다고 해보자. 1. root n..
이제 문제를 풀어보자. https://school.programmers.co.kr/learn/courses/30/lessons/92344 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 앞선 글에서 언급했듯이 brute force로 풀어서는 효율성 테스트를 통과하지 못한다. 이 문제를 푸는데 핵심이 되는 아이디어는 크게 2가지로, 1. 공격/회복을 전부 적용한 최종 결과를 한 번에 board에 적용한다. (공격/회복 하나씩 처리하면 안된다.) 2. 공격/회복 계산 시에는 역 누적합 배열을 이용한다. 1번은 쉽게 수긍이 되지만 2번은 저게 뭔 소린가 싶다. ..
https://school.programmers.co.kr/learn/courses/30/lessons/92344 위 문제를 풀어보려다 보니 brute force로 풀면 정확도까지는 쉽게 통과가 되나 1,000 x 1,000 2차원 배열에 250,000개의 배열 업데이트를 해야 하니 효율성 테스트를 통과할 여지가 없다. 해설을 찾아보니 누적 합을 사용해서 풀어야 한다는데, 이번 기회에 해당 내용을 정리하고 문제 풀이를 해보려 한다. # 1차원 누적 합 1차원 배열에서의 누적 합을 구하는 함수를 'f(x)'라 할 때 다음과 같이 정의된다. (구현 시 편의 상 i = 0부터 시작하는 것으로 하였다.) 이 때 x = a에서 x = b까지의 부분합을 구하고 싶다면, 다음과 같이 나타낼 수 있다. 이를 JavaS..
# 위상 정렬 (Topology Sort) 위상 정렬은 순서가 정해져 있는 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다. 비순환 유향 그래프에서 사용할 수 있다. 진입 차수(indegree), 즉 자신으로 들어오는 간선의 수가 0인 노드부터 차례대로 제거해나가며 순서를 정한다. # Process 진입 차수가 0인 노드를 큐에 담는다. 큐가 빌 때까지 큐에서 원소를 꺼내고 해당 노드에 연결된 간선을 제거한다. 새롭게 진입 차수가 0이 된 노드를 큐에 담는다. Ex. 대표적인 예시로 선수과목 있는 수강 계획 순서를 정할 때 사용할 수 있다. 0 ~ 5번의 과목이 있고 각 과목은 자신을 가리키는 선수 과목을 모두 들은 후에야 수강할 수 있다고 하자. 예를 들어 4번 과목은 1, 2번 과목을 모..
