프로그래밍나무

개념 세그먼트 트리는 간격에 대한 정보를 저장하는 자료구조입니다. 이를 이용하면 구간 합, 구간 최댓값/최솟값 들을 빠르게 구할 수 있습니다. 보통 구간 합을 구하는 방법은 해당 구간을 전부 탐색하면서 합을 구하는 방식입니다. 이 방법은 O(N)의 시간이 걸립니다. 하지만 세그먼트 트리의 경우 구간을 탐색하는데 O(lgN)의 시간밖에 걸리지 않습니다. 해당 글은 구간의 최솟값들을 구하는 방법으로 설명하겠습니다. https://www.acmicpc.net/problem/14438 14438번: 수열과 쿼리 17 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 i..

개념 서로 중복되지 않는 부분 집합들을 표현할 때 사용하는 알고리즘 해당 알고리즘에 필요한 연산은 부분 집합들을 서로 묶는 연산(Union), 해당 원소가 어느 집합에 속해있는지 찾는 연산(Find)이 있습니다. 부분 집합들을 표현하는 방법 배열 해당 원소가 몇 번째 집합에 속해 있는지 각각의 원소마다 표시합니다. 1번째 부분 집합 : {0, 1, 2} 0 -> 1, 1 -> 1, 2 -> 1 Union 연산: 모든 원소에 대해서 몇 번째 집합에 속해 있는지에 대한 수정이 일어납니다.( O(N) ) Find 연산: 해당 원소가 몇 번째 집합에 속해있는지 바로 찾을 수 있습니다.( O(1) ) 트리 부분집합마다 트리를 생성하여 각 원소가 부모 원소를 표시하고 있습니다(루트 원소는 자기 자신을 표시) 1번째..

개념 오름차순으로 정렬된 리스트에서 특정한 값을 찾는 알고리즘입니다 의사코드 BinarySearch(A[0..N-1], value, low, high) { if (high value) return BinarySearch(A, value, low, mid-1) else if (A[mid] < value) return BinarySearch(A, value, mid+1, high) else return mid // found } BinarySearch(정렬된 배열, 찾을 값, 배열의 첫 인덱스, 배열의 마지막 인덱스) 를 통해 이진 탐색을 수행할 수 있습니다 활용 그러면 해당 알고리즘을 코테 문제에 어떻게 적용할 수 있는지 생각해 보겠습니다. https://www.acmicpc.net/problem/1300..

배낭 문제는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법입니다. 이 배낭 문제는 두 가지로 나누어집니다. 짐을 쪼갤 수 있는 경우인 분할 가능 배낭(Fractional Knapsack) 짐을 쪼갤 수 없는 경우인 0-1 배낭(0-1 Knapsack) 분할 가능 배낭 이 문제는 그리디 알고리즘을 적용하면 다항 시간 안에 풀 수 있습니다. 짐을 쪼갤 수 있는 경우에는 무게당 가치가 제일 높은 물건이 먼저 들어가야 하므로 각 물건의 가치/무게를 구한 다음 가장 높은 물건부터 무게의 최댓값까지 넣습니다. 0-1 배낭 이 문제는 백준 12865번의 예제를 참고하여 설명하겠습니다. 물건을 담았을 때의 가치를 계산할..

LIS 개념 증가하는 부분 수열에 대해서 먼저 설명하자면 한 배열에서 어떤 원소들을 지웠을 때 나머지 모든 원소들이 증가하는 형태를 나타내는 것을 말합니다. [1, 3, 2, 4]라는 배열이 있다고 가정하겠습니다. 그럼 증가하는 부분 수열은 [1, 3], [1, 3, 4], [1, 2, 4] 등이 나올 수 있습니다. 이런 부분 수열 중에서 가장 긴 수열을 LIS라고 합니다. LIS 알고리즘 LIS를 구현하는 알고리즘은 다음과 같습니다. 다른 모든 원소들을 비교하는 O(N^2) 알고리즘 이진 탐색으로 원소들을 비교하는 O(NlogN) 알고리즘 N^2 알고리즘 이 알고리즘은 각 원소마다 해당 원소를 마지막 원소로 가진 LIS 길이를 구합니다. 이 길이중에서 가장 긴 길이가 전체 LIS길이가 됩니다. 각 원소..

유클리드 호제법(최대공약수) GCD(A, B)=GCD(B, A% B)이다. 계속하다가 A%B가 0이 될 때 B가 원래 A, B의 최대 공약수가 된다. EX) (6,4)->(4,2)->(2,0) 6,4의 최대 공약수는 2 최소공배수는 A*B/GCD(A, B)이다. 소수 구하기 제일 좋은 방법은 에라토스테네스의 체이다. 시간 복잡도는 N개의 수에 대한 소수를 구할 때 NlglgN이다. 2에서부터 N까지 수에서 제일 작은 수로 나누어지는 수를 삭제한다. 그럼 처음에는 4, 6, 8... 이 없어진다. 다음에는 제일 작은 수인 3으로 나누어지는 수를 삭제한다. 삭제되는 것을 잘 보다 보면 2를 삭제할 때는 삭제되는 처음 수가 2*2이고 3을 삭제할 때는 삭제되는 처음 수가 3*3인 것처럼 처음 삭제되는 수는 i..

힙 정렬 알고리즘 개념 과정 설명 오름차순을 구성하기 위해서는 배열을 최대힙으로 구성 최대 힙의 가장 첫번째 원소(배열에서 가장 큰 원소)를 하나씩 빼면서 정렬 힙의 원소가 하나 남을 때까지 반복 과정 상세 설명 정렬할 요소들을 가지고 배열에 하나씩 요소들을 넣으면서 최대 힙 구성 정렬할 요소 (4, 3, 2, 5, 1, 6) 맨 처음 원소 삽입 과정을 따로 처리할 과정이 없으므로 생략 인덱스 1 2 3 4 5 6 4 3 2 3 삽입 인덱스 2의 부모인 1과 비교, 인덱스 1의 원소가 더 크므로 pass 2 삽입시에도 동일 인덱스 1 2 3 4 5 6 4 3 2 5 ↓ 인덱스 1 2 3 4 5 6 4 5 2 3 ↓ 인덱스 1 2 3 4 5 6 5 4 2 3 5 삽입 인덱스 4의 부모인 인덱스 2의 원소와..