일지
-
JUNGOL...101일지 2021. 7. 25. 15:37
Intermediate_Coder/분할정복/Tutorial : 이진탐색(Binary Search-이진검색) 문제 [분할 정복 알고리즘(Divide and Conquer Algorithm)] 주어진 문제의 크기가 감당하기 어려운 경우 보다 작은 문제로 나누어 해결하는 방법(알고리즘)이다. 이진검색, 퀵정렬, 합병정렬 등이 대표적인 예이다. [이진 검색(Binary Search)] 이진 검색(탐색) 알고리즘이란 정렬된 데이터 리스트에서 목표값 또는 목표값이 있는 위치를 빠른 시간에 찾는 분할 정복 알고리즘 중에 하나이다. 예를 들어 정렬된 데이터 배열 A[]가 주어지고 목표값 target 을 찾는다고 가정해보자. 이때 첫 번째 원소의 인덱스는 low 이고, 마지막 원소의 인덱스는 high 라고 하자. 이제 ..
-
알고리즘...26일지 2021. 7. 25. 13:55
최악의 경우 선형시간 선택 알고리즘 최악의 경우에도 원소가 선형적으로 선택되지 않도록 하여 소요 시간이 Θ(n)이 되도록 하기 위한 알고리즘이다. 이를 위해 배열을 5개씩의 그룹으로 나누고 그룹의 중간 값을 이용하여 분할 및 선택을 진행한다. 최악의 경우 선형시간 선택 알고리즘 LinearSelect(A[], p, r, i) { 1. 원소의 총 수가 5개 이하이면 원하는 원소를 찾고 알고리즘을 끝낸다. 2. 전체 원소를 5개씩의 원소를 가진 ┌n/5┐개의 그룹으로 나눈다. 3. 각 그룹에서 중앙값을 찾는다. + 이렇게 찾은 중앙값들을 m1, m2,..., m┌n/5┐이라 하자. 4. m1, m2,..., m┌n/5┐들의 중앙값 m을 재귀적으로 구한다. 5. M을 기준 원소로 삼아 전체 원소를 분할한다. ..
-
JUNGOL...100일지 2021. 7. 23. 16:56
Intermediate_Coder/분할정복/Tutorial : 이진탐색(Binary Search-이진검색) 문제 [분할 정복 알고리즘(Divide and Conquer Algorithm)] 주어진 문제의 크기가 감당하기 어려운 경우 보다 작은 문제로 나누어 해결하는 방법(알고리즘)이다. 이진검색, 퀵정렬, 합병정렬 등이 대표적인 예이다. [이진 검색(Binary Search)] 이진 검색(탐색) 알고리즘이란 정렬된 데이터 리스트에서 목표값 또는 목표값이 있는 위치를 빠른 시간에 찾는 분할 정복 알고리즘 중에 하나이다. 예를 들어 정렬된 데이터 배열 A[]가 주어지고 목표값 target 을 찾는다고 가정해보자. 이때 첫 번째 원소의 인덱스는 low 이고, 마지막 원소의 인덱스는 high 라고 하자. 이제 ..
-
알고리즘...25일지 2021. 7. 23. 14:50
평균 선형시간 선택 구현 배열 arr과 배열의 길이 n, 몇 번째로 작은 값인지에 대한 idx 입력으로 받는 함수를 구현한다. AvgNSelection.hpp #pragma once #include "../Common.hpp" int AvgNSelection(int arr[], int p, int r, int idx); int Partition(int arr[], int p, int r); /// /// 주어진 배열에서 idx 번째로 작은 값을 찾는다. /// /// 정렬을 진행할 배열 /// 배열의 길이 /// 찾으려는 값 /// 결과 출력 여부 void AvgNSelection(int arr[], int n, int idx, bool printData = false) { int result{ AvgN..
-
JUNGOL...99일지 2021. 7. 22. 14:36
Intermediate_Coder/분할정복/Tutorial : 이진탐색(Binary Search-이진검색) 문제 [분할 정복 알고리즘(Divide and Conquer Algorithm)] 주어진 문제의 크기가 감당하기 어려운 경우 보다 작은 문제로 나누어 해결하는 방법(알고리즘)이다. 이진검색, 퀵정렬, 합병정렬 등이 대표적인 예이다. [이진 검색(Binary Search)] 이진 검색(탐색) 알고리즘이란 정렬된 데이터 리스트에서 목표값 또는 목표값이 있는 위치를 빠른 시간에 찾는 분할 정복 알고리즘 중에 하나이다. 예를 들어 정렬된 데이터 배열 A[]가 주어지고 목표값 target 을 찾는다고 가정해보자. 이때 첫 번째 원소의 인덱스는 low 이고, 마지막 원소의 인덱스는 high 라고 하자. 이제 ..
-
알고리즘...24일지 2021. 7. 22. 14:28
선택 알고리즘 n 개의 원소를 가진 정렬되지 않은 집합에서 최소 원소를 찾는 것은 Ω(n)이 소요된다. 더 나아가 i 번째로 작은 원소를 찾을 때 Ο(nlogn)이 소요되는 정렬을 수행 후 i 번째 원소를 찾는다면 Ο(nlogn)이 소요될 것이다. 선택 알고리즘은 이러한 문제를 Ο(n)에 가깝게 수행하기 위한 알고리즘이다. 평균 선형시간 선택 알고리즘 퀵 정렬의 분할 알고리즘을 이용하여 기준 점 좌측 배열에 원하는 순서의 원소가 존재한다면 좌측 배열에 대해서만 재귀적으로 분할 알고리즘을 적용하여 원하는 위치의 원소를 찾을 수 있게 된다. 평균 선형시간 선택 알고리즘 Select(A[], p, r, i) { if (p = r) then { return A[p]; } q ← Partition(A, p, r)..
-
JUNGOL...98일지 2021. 7. 20. 16:02
Beginner_Coder/재귀/싸이클 문제 두 자연수 N과 P를 가지고 다음 과정을 거쳐서 나오는 숫자들을 차례대로 출력해보자. 처음 출력하는 숫자는 N이고, 두 번째 이후 출력하는 숫자들은 N을 곱하고 P로 나눈 나머지를 구하는 과정을 반복하여 구한다. 즉, 먼저 N에 N을 곱하고, 이 수를 P로 나눈 나머지를 두 번째에 출력한다. 다음에는 이 나머지에 N을 곱하고 P로 나눈 나머지를 출력한다. 다음에는 이 나머지에 N을 곱한 후 P로 나눈 나머지를 출력한다. 이 과정을 계속 반복해보면 출력되는 숫자들에는 반복되는 부분이 있다. 예를 들어서, N=67, P=31인 경우를 생각해보자. 처음 출력되는 숫자는 67이고, 두 번째로 출력되는 숫자는 67×67=4489를 31로 나눈 나머지 25이다. 다음에는..
-
알고리즘...23일지 2021. 7. 20. 15:56
계수 정렬 입력의 값이 모두 Ο(n)을 넘지 않는 경우 사용할 수 있는 정렬 방법으로 Θ(n) 이 소요되는 알고리즘이다. 계수 정렬 알고리즘 // A[]를 정렬한 결과가 B[]에 저장될 때 CountingSort(A[], B[], n) { // 배열(혹은 딕셔너리) C[] 초기화 for i ← 1 to k { C[i] ← 0; } // 값이 A[j]인 개수 for j ← 1 to n { C[A[j]]++; } // 값이 A[j] 보다 작은 것의 개수 for i ← 2 to k { C[i] ← C[i] + C[i - 1]; } // B[]에 A[]의 자리를 확인하여 저장 for j ← n downto 1 { B[C[A[j]]] ← A[j]; C[A[j]]--; } } 더보기 참고문헌 한빛아카데미.문병로.(..