Algorithm8 유니온-파인드(Union-Find), 서로소 집합(Disjoint Set) Union Find와 Disjoint Set은 동일한 의미를 가지며, 여러 서로소 집합의 정보를 저장하고 있는 자료구조를 의미합니다. 트리 형태로 구현되며, 보통 자신의 root 노드를 집합을 구분하는 ID처럼 사용된다. 이 자료구조는 두 가지 연산을 지원한다. 1. find(p): p의 root 노드의 값을 가져옴 2. union(p, q): p와 q의 집합을 합친다. (코드 구성 시에는 union이라는 예약어가 있어 merge로 대체) 맨 처음에는 모든 노드가 자기 스스로를 root 노드로 가지게 된다. find 함수는 현재 자기의 parent 노드가 자신이면 자기를 반환하고, 아니면 자신의 parent 노드의 parent노드를 반환한다. 이러한 방식으로 자신의 root 노드를 찾게 된다. union.. 2020. 4. 14. 가장 긴 증가하는 부분 수열, LIS(Longest Increasing Subsequence) LIS는 어떠한 수열에서 증가하는 부분 수열중 길이가 가장 긴 수열를 뜻합니다. LIS를 찾는 알고리즘은 다이나믹 프로그래밍을 이용한 O(N^2) 알고리즘과 이보다는 좀 더 복잡한 O(N log N) 알고리즘이 있습니다. 부분 수열이란 어떠한 수열에서 일부 숫자를 지워서 만들 수 있는 새로운 수열을 의미합니다. O(N^2) O(N^2) 알고리즘은 비교적 간단하게 구현할 수 있습니다. dp[i] = i 번째 원소를 마지막으로 하는 LIS의 길이 dp[i]를 구하는 법은 1 ~ (i - 1)까지의 원소들 중 i번째 원소보다 값이 작은 것들 중 dp의 값이 가장 큰 것에 1을 더하면 된다. 즉, j = 1 ~ (i - 1)을 순회할 때, a[i]보다 a[j]가 작다면, dp[i] = max(dp[i], dp[.. 2020. 4. 7. Lower Bound & Upper Bound Lower Bound & Upper Bound은 이분 탐색에서 파생된 알고리즘으로 Lower Bound는 "찾는 값 T 이상이 처음 나오는 위치를 찾는" 알고리즘이고, Upper Bound는 "찾는 값 T 초과한 값이 처음 나오는 위치를 찾는" 알고리즘이고, Lower Bound 알고리즘 자체는 이분 탐색과 매우 유사하다. 중간 값이 작으면 시작 위치를 중간 다음 위치로, 크거나 같으면 끝 위치를 중간 위치로 이동시킨다. 이분 탐색과는 다르게 끝 위치를 중간 이전 위치가 아닌 중간 위치로 움직인다. 간단하게 생각해보면 값이 작다는 건 중간 위치까지는 원하는 값 이상이 절대 없기에 다음 위치로 이동시키지만, 크거나 같다면 중간 위치의 값이 찾는 값 이상인 처음 위치일 수도 있기에 중간 위치로 설정한다. #.. 2020. 4. 3. 이분 탐색(Binary Search) 이분 탐색(Binary Search)이란 특정 값을 비교적 빠르게 찾는 알고리즘입니다. 선형 탐색의 경우 N개 값 중에 T라는 값을 찾는다면 최악의 경우 O(N)의 시간 복잡도를 가집니다. 하지만 이분 탐색은 최악의 경우 O(logN)의 시간 복잡도를 가집니다. 이분 탐색은 1가지 조건이 필요합니다. 입력받은 값들이 정렬되어 있어야합니다. 이분 탐색은 특정 값을 찾을 때 탐색 범위를 절반씩 나눠가며 값을 찾는데, 이때 절반으로 나누는 기준이 값의 크기입니다. 크기에 따라 나누어진 절반의 오른쪽 범위인지, 왼쪽 범위인지를 구별합니다. 이분 탐색의 기본 로직은 처음에 Left, Right 값을 인덱스의 시작, 끝으로 초기화한다. Left, Right의 중간 위치의 값이 찾는 값 T보다 크면 Left를 중간 .. 2020. 4. 3. [정렬] 선택 정렬 (Selection Sort) 원소를 넣을 위치를 정해놓고 어떤 원소를 넣을지 찾아서 정렬한다. 오름차순의 경우, 가장 작은 값을 찾아서 왼쪽부터 정렬을 하거나, 가장 큰 값을 찾아 오른쪽부터 정렬을 하는 방식이다. 1. i = ( 1 ~ (n - 1) )인덱스까지 탐색 2. j = ( (i + 1) ~ n ) 인덱스까지 탐색 3. j의 값 중에 가장 작은 값을 찾아 i번째의 값과 위치를 바꾼다. 4. 위 과정 반복 코드 구현 #include void PrintArray(int* arr, int size) { for (int i = 0; i < size; i++) { printf("%d ", arr[i]); } printf("\n"); } void Selection(int* arr, int size) { int min, tmp; fo.. 2020. 1. 20. [정렬] 삽입 정렬 (Insertion Sort) 두 번째 자료부터 시작하여 앞에 자료들과 비교하여 알맞은 위치에 자료를 넣는 형식의 정렬이다. 비교를 하는 앞의 배열은 이미 정렬이 되어있다. 즉, n번째 자료를 비교할 때 0 ~ (n - 1) 번째 자료는 정렬이 되어있다. 손에 카드를 들고 정렬하는 방식과 유사하다. 1. i = (1 ~ n)인덱스까지 탐색 2. j = ( (i - 1) ~ 0 ) 인덱스까지 탐색 3. j번째 값이 i번째 값보다 크면 j + 1의 값에 j의 값을 할당하고, 크지 않으면 해당 위치에 i번째 값을 삽입 4. 위 과정 반복 코드 구현 #include void PrintArray(int* arr, int size) { for (int i = 0; i < size; i++) { printf("%d ", arr[i]); } pri.. 2020. 1. 20. [정렬] 버블 정렬 (Bubble Sort) 소개 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘이다. 다른 정렬 알고리즘에 비해 느린 편이지만, 코드가 간단하다. 정렬 과정 첫 번째 탐색 1. 5와 3을 비교 2. 앞에 있는 5가 더 크므로 5와 3의 위치를 바꾼다. 3. 5와 1을 비교 4. 앞에 있는 5가 더 크므로 5와 1의 위치를 바꾼다. 5. 5와 9를 비교 6. 뒤에 있는 9가 더 크므로 위치를 변경하지 않는다. 7. 9와 7을 비교 8. 앞에 있는 9가 더 크므로 9와 7의 위치를 바꾼다. 9. 첫 번째 순회가 끝난 배열 첫 번째 탐색의 과정을 보면 가장 큰 수가 맨 뒤로 이동하게 된다. 즉, 매 순회마다 정렬된 수를 제외한 가장 큰 수가 맨 뒤로 가 뒤에서부터 정렬이 된다. 그러므로 맨 순회마다 배열의 전체를 탐색할 필요 없이 정.. 2019. 11. 21. 에라토스테네스의 체(Eratosthenes' sieve) 에라토스테네스의 체(Eratosthenes' sieve) 1부터 N사이의 모든 소수와 소수가 아닌 수를 찾는 방법이다. 소수는 1과 자기 자신만을 약수로 가지는 수이다. 쉽게 말해 소수는 자기 자신과 1로 밖에 못 나누는 수이다. 이러한 원리를 이용해 배수를 지우면서 소수가 아닌 수를 배제해 나가는 방법이다. 즉, 1)--- 2의 배수인 4, 6, 8, 10, 12..........지움 3의 배수이면서 지워지지 않은 수인 9, 15, 21.......지움 . . . . . . 2)--- 이러한 과정을 반복하며 소수가 아닌 수를 지워나간 후 마지막까지 지워지지 않은 수인 소수를 찾는 방법이다. ----- 예를 들어 1 ~ 50 사이의 소수를 찾는 다면, 1은 소수가 아니므로 먼저 배제하고 2의 배수들을 배.. 2019. 3. 17. 이전 1 다음
