알고리즘
-
알고리즘...8일지 2021. 5. 26. 09:48
정렬이란 n개의 원소를 순서대로 배열하는 것으로 실생활에 다양하게 사용되는 알고리즘이다. 가령 학생을 키 순서대로 줄을 세운다거나 세무서에서 고지서를 날리기 위해 주민등록 번호순으로 정렬하는 것 등을 예로 들 수 있다. - 정렬의 종류 정렬에는 여러 종류가 있으며 대표적으로 다음과 같은 정렬이 존재한다. 선택 정렬 가장 큰 원소 또는 가장 작은 원소를 찾아 첫 위치 또는 마지막 위치와 자리를 바꾸는 정렬, Ο(n²) 버블 정렬 두 개의 원소를 비교하여 정렬 방향에 따라 서로 자리를 바꾸는 연산을 반복하는 정렬, Ο(n²) 병합 정렬 원소를 두 구역으로 나누는 것을 반복한 뒤 병합하며 자리를 바꾸는 연산을 반복하는 정렬, Ο(nlogn) 퀵 정렬 특정 값을 기준으로 영역을 나누어 자리를 바꾸는 연산을 반복..
-
알고리즘과 귀납적 사고프로그래밍 기초/알고리즘 2021. 5. 20. 08:57
알고리즘과 귀납적 사고 알고리즘이란? 어떤 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어내는 과정을 기술한 것으로 알고리즘을 설계하기 위해서는 해야 할 작업을 명확하게 명시해야 한다. ※ 알고리즘이 명확하다는 것은 모호하지 않고 이해하기 쉬운 것을 의미하며 자세한 것과는 다르다. 알고리즘은 가능하면 효율적이어야 하며 그중 작은 입력보다는 충분히 큰 입력에 대해 관심을 가져야 한다. 이렇게 큰 입력에 대한 분석을 점근적 분석(Asymptotic Analysis)라고 한다. 알고리즘을 분석하는 이유 어떠한 입력을 일정 시간 이내에 처리해야 할 때 적용할 수 있는 알고리즘의 시간 분석을 하면 각 알고리즘이 어느 정도의 시간이 소요되는지 파악하여 적절한 알고리즘을 적용할 수 있다. ※ 일반적인 상황에서..
-
알고리즘...7일지 2021. 5. 17. 16:36
- 추정후 증명 추정후 증명은 식의 모양을 보고 점근적 복잡도를 추정한 뒤 그것이 옳음을 증명하는 방법으로 추정을 의미 있게 하는 것이 중요하다. 이때, 적절한 추정을 위해서는 여러 식을 분석하고 결과를 얻는 과정을 반복해 직관을 얻어야 한다. ※ 추정을 너무 크게 한다면 의미가 없는 결과를 얻게 되고 추정을 너무 작게 한다면 증명이 불가능하다. - 마스터 정리 마스터 정리는 다음과 같은 모양을 가진 재귀식에 대해 결과를 바로 알 수 있는 정리이다. T(n) = aT(n/b) + f(n) 어떤 양의 상수 ε에 대하여 f(n)/h(n) = Ο(1/n^ε)이면, T(n)=Θ(h(n))이다. 어떤 양의 상수 ε에 대하여 f(n)/(h(n) = Ω(n^ε)이고, 어떤 상수 c(< 1)와 충분히 큰 모든 n에 대..
-
알고리즘...6일지 2021. 5. 14. 17:47
점화식의 점근적 분석 방법 대표적인 방법으로 반복 대치, 추정후 증명, 마스터 정리가 존재한다. - 반복 대치 : 어떤 함수의 입력이 n일 때 소요 시간을 T(n)이라 할 경우 T(n)을 T(n - 1)로 대치하고 T(n - 1)을 T(n - 2)로 대치하는 것을 반복하여 T(1)까지 대치하는 분석 방법이다. 어떤 함수의 입력이 n일 때 소요 시간 T(n)은 다음과 같이 나타낼 수 있다. T(n) = T(n - 1) + c 이때 c는 자기 호출을 제외한 나머지를 수행하는 시간을 나타낸다. 병합 정렬 알고리즘의 반복 대치를 통한 분석은 다음과 같이 진행할 수 있다. MergeSort MergeSort(A[], p, r) { if (p < r) then { q ← |_ q + r / 2 _| MergeSor..
-
알고리즘...5일지 2021. 5. 13. 02:49
여러가지 점근적 표기법 점근적 표기법에는 대표적인 빅오 표기법 외에도 여러가지 표기법이 존재한다. 세타(Θ) 표기법 최고차항의 차수가 주어진 함수의 차수와 일치하는 함수들의 집합...동등(≒) { n², 3n² + 4, n² + nlogn, ... } = Θ(n²) 빅오(Ο) 표기법 최고차항의 차수가 주어진 함수의 차수와 같거나 작은 함수들의 집합...이하(≤) { 2n², 3n, 2nlogn, ... } = Θ(n²) 오메가(Ω) 표기법 최고차항의 차수가 주어진 함수의 차수와 같거나 큰 함수들의 집합...이상(≥) { n² + n, 3n³ + 4n, 6n⁴ + logn, ... } = Θ(n²) 리틀오(ο) 표기법 최고차항의 차수가 주어진 함수의 차수보다 작은 함수들의 집합...미만(＜) { 3n, 2..
-
알고리즘...4일지 2021. 5. 12. 08:02
점근적 표기 알고리즘의 효율성을 분석하기 위해 매우 큰 입력을 가정하여 분석하는 데 이 분석을 점근적 분석이라 한다. 극한에 대한 문제가 이러한 점근적 분석의 예이다. 이것의 의미는 n이 충분히 커짐에 따라 n의 비율로 증가한다는 것이다. 추가적으로 n와 10n, 2n^2의 예를 들면 다음과 같다. n 10n 2n^2 1 10 2 2 20 8 10 100 200 1,000 10,000 20,000 10,000 100,000 2,000,000 100,000 1,000,000 200,000,000 1,000,000 10,000,000 2,000,000,000,000 10,000,000 100,000,000 200,000,000,000,000 ... ... ... 10^10 10^11 2*10^20 10^20..
-
알고리즘...3일지 2021. 5. 11. 08:18
재귀와 귀납적 사고 재귀를 사용하는 알고리즘이 많으며 일반적으로 재귀와 관계없다고 생각하는 선택 정렬이나 버블 정렬도 재귀적 관점에서 보면 이해하기 쉬워진다. 귀납적 사고는 작은 입력에 대해 옳다고 가정하고 큰 입력에 대한 처리를 진행하는 것을 말한다. 이는 수학적 귀납법의 작은 값에 대해 옳다고 가정하고 문제와의 관계를 통해 결론이 옳음을 보이는 것과 비슷하다. 알고리즘으로 푸는 문제 최단경로 알고리즘 두 지점간의 최단경로 혹은 최단시간의 경로를 찾는 것 ex) 네비게이션 스케줄링 한정된 자원을 효율적으로 이용하는 방법 ex) 자판기 관리 검색 원하는 검색 결과를 최대한 빨리 반환하는 것 ex) 인터넷 검색 엔진 정렬 주어진 값을 정해진 순서대로 정렬하는 방법 ex) 고객 메일링 리스트 참고문헌 참고문..