최장 증가 부분 수열이란?최장 증가 부분 수열(LIS, Longest Increasing Subsequence)은 어떤 수열이 주어졌을 때, 그 안에서 순서를 유지하면서 증가하는 가장 긴 부분 수열을 찾는 알고리즘이다. 여기서 말하는 "부분 수열"은 연속일 필요는 없지만 순서는 유지되어야 한다. 예를 들어, 수열이 [10 20 10 30 20 50] 이라면 최장 증가 부분 수열은 [10 20 30 50]이다. 최장 증가 부분 수열은 여러 개가 존재할 수 있다. 최장 증가 부분 수열은 다음과 같이 두 개의 방법으로 구현할 수 있다.1. 동적 계획법(DP)각 위치에서 끝나는 LIS 길이를 계산해 나가는 방식이다. 즉, DP[i]는 다음과 같이 정의된다.dp[i] : arr[i]를 마지막 값으로 가지는 LIS..
Study/Algorithm
유니온 파인드 유니온 파인드는 일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성된다. union - 각 노드가 속한 집합을 1개로 합치는 연산이다. 노드 a, b가 a ∈ A, b ∈ B 일 때 union(a, b)는 A ∪ B를 말한다. find - 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산이다.노드 a가 a ∈ A 일 때 find(a)는 A 집합의 대표 노드를 반환한다. 구현 방법 일반적으로 1차원 배열을 이용해 각 노드가 속한 집합에서의 대표 노드를 저장한다. 1~6의 값을 가지고 있는 노드들이 있다. 현재 연결된 노드가 없으므로 모든 집합의 대표 노드는 자기..
분할 정복 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 해결하는 방법 대표적인 예: Quick Sort, Merge Sort 재귀함수를 사용해 구현 분할 정복의 단점 재귀함수를 사용하기 때문에 오버헤드가 발생하며, 스택에 다양한 데이터를 보관하고 있어야 하므로 스택 오버플로우가 발생하거나 과도한 메모리 사용을 하게된다. Merge Sort 정렬해야 할 리스트가 주어지면 해당 리스트를 최대한 작게 쪼갠 후, 인접한 원소들끼리 비교하며 정렬해 합치는 방법이다. 위 gif는 merge sort 과정에서 업데이트 되는 정렬 리스트를 보여주는 것이기 때문에 정렬 과정을 이해하기엔 어려우니 아래 그림을 통해 이해해보자. 이해가 쉽도록 리스트 원소의 개수를 8개로 하였다. 더이상 쪼갤 수 없을 때까지 쪼갠 후..
인덱스 트리 인덱스 트리는 값이 계속 변경되는 구간의 대표값을 구할 때 쓰이는 자료구조이다. 여기서 대표값이란 구간의 합, 최솟값, 최댓값 등을 말한다. 이번 글에서는 구간의 합을 예시로 들어 설명하겠다. 인덱스 트리의 구조 인덱스 트리에서 부모 노드는 자식 노드의 대표값을 가진다. 아래와 같은 노드가 있다고 해보자. 이 노드들의 부모는 어떤 값을 가질까? 루트 노드까지 트리를 채워보자. 부모 노드는 자식 노드의 합이라는 것을 볼 수 있다. 여기서 주의해야 하는 점은 이진 트리의 각 계층은 2의 제곱수만큼 노드를 가져야 하는데, 우리 예시는 노드가 5개 뿐이다. 즉, 5보다 큰 2의 제곱수인 8보다 3개 모자르다. 따라서 현재 우리는 구간의 합을 구하는 문제이기 때문에 합에 영향을 끼치지 않는 0으로 채..
이분탐색을 응용한 알고리즘이므로 이분탐색을 먼저 공부하고 오자. Lower bound찾고자 하는 값 이상이 처음 나타나는 위치이다.Lower bound 과정Lower bound를 찾는 과정은 아래와 같다.1. 데이터셋의 중간 값을 가져온다.2. 중간 값과 찾고자 하는 값을 비교한다. 2-1. 중간 값이 찾고자 하는 값보다 작다면 left를 mid + 1로 변경한다. 2-2. 중간 값이 찾고자 하는 값보다 크거나 같다면 right를 mid로 변경한다.3. left 4. 반복이 끝나면 right가 Lower bound가 된다. 그림을 통해 살펴보자. 아래와 같은 데이터셋이 있고, target = 13라고 가정한다. 즉, 13보다 크거나 같은 값이 처음 나타나는 위치를 찾는다.모든 원소가 targe..
이분 탐색데이터가 정렬되어 있는 상태에서 원하는 값을 찾아내는 알고리즘데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 범위를 절반씩 줄이면서 대상을 찾는다.시간 복잡도: $O(logN)$ 이분 탐색 과정이분 탐색을 위해서는 데이터셋이 정렬되어 있어야 한다. 데이터 셋은 아래와 같다. 찾고자 하는 데이터(target)는 100이라고 가정하고 설명한다. 1. 현재 데이터 셋의 중앙값을 선택한다. left는 데이터 셋의 시작 인덱스, right는 데이터 셋의 마지막 인덱스이다. 중앙값의 인덱스는 (left + right) / 2 를 통해 알아낸다.중앙값인 30은 우리가 찾고자하는 100보다 작다. 따라서 30보다 작은 index 중 100은 절대 존재할 수 없으므로 데이터셋의 길이를 줄여준다. 100의 ..
