기록하는 습관 "기습"

선택 알고리즘 Selection algorithm 눈 앞에서 각각 숫자가 놓여 있다. 1, 3, 5, 6, 7 ... 여기서 만약 3번째로 큰 원소를 찾아야 한다. 여기서 보통 O(n log n) 시간이 걸리는 정렬 알고리즘을 사용하여 정렬해놓고 위치를 찾을 수 있다. 하지만, 더 빠르게 찾을 수도 있다. 더욱 n에 비례하는 시간에 근접할 수 있는 알고리즘이 선택 알고리즘 selection algorithm이다. 선택 알고리즘에는 두 가지 유형이 있다. 평균적으로 선형시간(n에 비례한 시간)이 소요되는 선택 알고리즘을 말한다. (select라 보통 표현한다.) '최악'의 경우에도 선형시간이 보장되는 선택 알고리즘이다. (linearselect라 보통 표현한다.) 여기서는 일반적인 선택 알고리즘을 먼저 설..

특수 정렬 지금까지 봐온 정렬들은 모두 원소끼리 비교해서 정렬하는 비교 정렬 comparison sort이었다. 이 비교 정렬은 최악의 경우, 아무리 빨라도 수행시간이 Θ(nlogn)이다. Ω(nlogn)이라고도 할 수 있다. 다시 말해, '하한'이 존재한다. 그러나 원소들이 특수한 성질을 만족하면 다른 기법으로 O(n) 정렬이 가능하다. 계수 정렬 Counting Sort 기수 정렬 Radix Sort 계수 정렬 counting sort 원소들의 값이 모두 O(n) 범위에 있을 때 사용가능하다. 또는 -O(n)~O(n) 범위에 있을 때도 가능하다. 이를 전제로 하는 과정은 다음과 같다. 배열 A[1~n]의 원소들이 k(상수)를 넘지 않는 자연수인 경우, 배열에서 1에서 k까지 자연수가 몇 번씩 나타나는..

고급 정렬 고급 정렬들은 평균 수행시간이 Θ(nlogn)이다. 이 중에 퀵 정렬이 가장 많이 사용된다. 병합 정렬 merge sort 정렬할 대상을 반으로 나누고, 반으로 나눈 전반부와 후반부를 독립적으로 정렬한다. 정렬된 두 부분을 합치면서 정렬된 배열을 얻는다. 병합정렬 또한 재귀알고리즘이다. 수행시간은 두 부분을 각각 정렬하는 시간과 병합시간을 합하면 된다. 점화식으로 표현하면 다음과 같다. T(n) = 2T(n /2) + Θ(n) 마스터정리를 이용한 점근적 표기로는, a=2, b=2 f(n)=n h(n)=nlog2 =n 따라서, h(n)이 더 크므로 T(n)=Θ(nlogn) 병합 정렬을 자바 코드로 구현해보자. public class MergeSort { public static void sort..

정렬 알고리즘 정렬이란, n의 개의 원소를 기준에 따라 순서대로 배열하는 것을 의미한다. 정렬 알고리즘의 수행시간은 대부분 O(nlogn)~O(n²)을 지닌다. 다만, 정렬하고자 하는 값이 특수한 성질을 만족하면 O(n) 수행시간도 가능하다. 정렬 알고리즘 분류 기본적인 정렬 -평균 θ(n²) 선택 정렬 selection sort 버블 정렬 bubble sort 삽입 정렬 insert sort 고급 정렬 - 평균θ(nlogn) 병합정렬 merge sort 퀵 정렬 quick sort 힙 정렬 heap sort 특수 정렬 - 평균 θ(n) 계수 정렬 기수 정렬 기본적인 정렬 알고리즘 단어 그대로 기본적이며 간단히 구현 가능한 알고리즘이다. 계수가 작을 때는 타 알고리즘에 비해 더 빠른 결과를 얻을 수도 있..

점화식 Recurrence relation 어떤 함수를 자신보다 더 작은 변수에 대한 동일 함수와의 관계로 표현한 것! 사전적 의미는 이렇다. 당연히 잘 이해가 되지 않는다. 풀어서 설명하면 다음과 같다. -> 동일한 함수가 등호나 부등호 양쪽에 나타난다. 이 두 함수의 변수 크기는 다르다. 하지만 동일하다. 입력 크기가 작으면 알고리즘의 효율성을 굳이 따질 필요가 없다. 허나 크기가 커지면 얘기가 다르다. 이런 경우를 위한 분석이 '점근적 분석 Asymptotic analysis'이다. 이번에는 점화식으로 표현한 재귀 알고리즘을 점근적 표기로 나타내는 방법을 알자. 재귀 알고리즘의 수행시간 ->점화식으로 표현 재귀로 표현한 병합정렬을 보자. mergeSort(A[ ], p, r) ▷ A[p ... r]..

바람직한 알고리즘 주어진 문제를 체계적인 절차로 해결했다고 해서 모든 알고리즘이 바람직하다고는 할 수 없다. '좋은 알고리즘'의 특성은 다음과 같다. 모호하지 않고 이해하기 쉽도록 명확해야 한다. 같은 문제를 해결하는 알고리즘 사이에 수행시간 수백 배 차이가 날 수 있다. 가장 적은 수행시간을 갖는다. 알고리즘 분석 알고리즘의 타당성을 확인하기 위해 알고리즘을 분석할 필요가 있다. 여기서 '소요시간(수행시간)'이 가장 중요하다. 알고리즘 a는 연산시간 1/5초 걸릴 수 있고, 알고리즘 b는 연산시간 5초 걸릴 수도 있다. n의 값 25를 기점으로 수행시간에 현저한 차이를 보인다. 재귀와 귀납적 사고 재귀란, 자기호출(recurrence)이며, 어떤 문제 안에서 크기만 다를 뿐 성격이 똑같은 작은 문제 포..

알고리즘이란? 주어진 문제를 해결하기 위해 체계적으로 기술한 것이다. 이를 설계하려면 문제해결을 위해 무엇을 해야 할지 명확히 알아야 한다. 즉, 입력으로부터 출력을 만들어내야 한다. 예를 들어보자. 한 학교에서 n명의 학생이 시험을 봤다. 그중 가장 높은 점수를 받은 학생만 뽑아야 한다. maxScore(x[],n){ x[1, ... , n]을 차례대로 찾는다. return 최대값을 반환한다. } 알고리즘은 배운다는 것은 곧, 생각하는 방법을 배우고 문제해결에 도움이 되는 생각의 빌딩블록을 제공받는 것이다.

검색 search이란 컴퓨터에 저장한 자료 중에서 원하는 정보를 찾는 작업이다. 다르게 말하자면, 원하는 검색키를 지닌 항목을 찾는 것이며, 원하는 항목이 있을 경우엔 '검색 성공', 없을 경우엔 '검색 실패'가 된다. 원소의 삽입 삭제를 위해서도 검색 연산을 수행하기도 한다. 검색 알고리즘을 고를 땐 고려해야 할 사항이 있다. 수행 시간 복잡도, 자료구조, 정렬 여부, 자료의 위치 등이 있다. 검색 수행 위치에 따라, 메모리에서 수행하면 내부 검색, 보조기억장치에서 수행하면 외부 검색으로 나뉜다. 검색 방식에도 분류가 있다. 검색 대상의 키를 저장된 자료의 키와 비교하여 검색하는 '비교 검색'과 계수적인 성질 값을 이용한 계산으로 검색하는 '계산 검색'이 있다. 순차 검색 Sequential searc..

정렬 자료들을 오름차순이나 내림차순으로 재배열하는 것이다. 정렬에 기준이 되는 특정 값을 키key라고 한다. 정렬 시에는 안정 정렬 stable sort를 이용해야 하는 경우가 있다. 두 개의 열이 정렬됐을 때 원래 순서가 보장되는 경우, 안정정렬이 된 것이고, 원래 순서가 유지되지 않는 경우 안정정렬이 되지 않은 것이다. 다양한 정렬 알고리즘 중에서 하나를 선택할 때는 고려해야 할 사항들이 많다. 시간 복잡도는 얼마인가? 구현이 간단한가? 자료량이 많거나 적을 때 적절한가? 안정정렬인가? - 이 조건으로 선택가능한 알고리즘이 줄어든다. 추가 메모리양은 얼마인가? 이미 정렬된 경우 더 신속하게 정렬가능한가? 또, 정렬에는 내부정렬 internal sort과 외부정렬 external sort이 있는데 여기..

그래프 Graph는 사물이나 현상을 정점 vertex이나 간선 edge으로 표현한 것이다. 정점은 대상, 간선은 대상 간의 관계를 나타낸다. 선형 자료구조나 트리 구조로는 표현할 수 없는 다 대 다 관계를 표현할 수 있다. 그래프의 종류 무방향 그래프 undirected graph 간선에 방향이 없는 그래프다. 정점 a와 정점 b를 동일하게 가르킨다. 즉, (a,b), (b,a)이다. 방향 그래프 directed graph digraph라고도 한다. 간선에 방향이 있는 그래프다. 무방향 그래프와 다르게 한쪽 방향만 가르킨다. 완전 그래프 complete graph 각 정점에서 다른 모든 정점으로 가는 간선이 존재하는 그래프를 뜻한다. 즉, 주어진 정점 수에 대해 간선수가 최대이다. 정점이 n개인 완전 그..