기록하는 습관 "기습"

검색트리 데이터의 저장과 검색은 자료구조와 알고리즘 분야에서 매우 중요하다. 수행시간에서 커다란 차이를 보이기 때문이다. 데이터의 저장과 검색을 효율적으로 하기 위해서는 적절한 자료구조 및 알고리즘의 사용을 필요로 한다는 사실은 자명하다. 만약 데이터가 들어오는 순서대로 배열에 저장한다고 가정해보자. 자료수가 n개일 때 수행시간은 다음과 같다. 새로운 자료 하나를 저장하는 시간은 Θ(1) 자료를 검색하는 시간은 Θ(n) 보다시피 검색에는 비효율적이다. 허나, 트리 모양 구조의 검색 트리에 저장한다면 어떨까? 저장과 검색, 둘 모두 Θ(log n)의 시간이 걸린다. 검색트리는 자식노드 갯수에 따라, 저장장소에 따라, 검색키에 포함된 필드수에 따라 분류된다. 다만 여기서는 언급하지 않겠다. 이진 검색트리 이..

지수의 문제 지수 index란 상품의 수량이나 가격에 생긴 평균적인 변화를 하나의 수치로 표현한 것이다. 여기서 수량지수와 가격지수로 나눌 수 있다. 수량지수 quantity index : 상품묶음의 양이 평균적으로 증가한 것인지 여부를 판별한다. 가격지수 price index : 상품가격의 평균적인 변화에 대해 알 수 있는 지수다. 수량지수 이질적인 상품들을 하나로 묶어 평균적인 수치로 나타내기 위해 고안된 개념이다. 각 상품의 양에 가격을 곱하고 이를 모든 상품에 대해 더해서 상품묶음의 전체 가액을 구한다. 선분 A0B0는 2004년의 예산선이고, A1B1은 2014년의 예산선이다. i를 보면 소비자는 2004년의 예산으로 Q0를 구매할 수 있었지만 2014년에 들어선 Q1를 구매할 수 있으므로 명백..

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

예산제약 budget constraint 상품을 구입하는 목적으로 지출할 수 있는 소득의 일정한 크기를 의미한다. 자신의 소득을 m이라 가정하고 한 달의 쌀과 옷을 소득에 맞게 각각 구매 한다고 해보자. 그렇다면 나의 예산제약은 다음과 같다. Px X * PyY = M 상품묶음에 대해 분명히 파악하고자 한다면 위의 식을 y에 대해 풀어서 다음처럼 표현해야 한다. -(Px/Py)는 아래에서 보이듯 예산선의 기울기이며, M/Py는 y축 상의 절편이다. 아래와 같은 그래프가 완성되며 이는 예산선 budget line이라 한다. 소득을 전부 사용하였을 때 얻을 수 있는 상품묶음 집합을 그래프로 나타낸 것이다. 예산선의 기울기는 기회비용과도 관련이 있다. 기회비용이란, 어떠한 재화나 서비스를 구매하기 위해 포기하..

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

소비자 이론 시장에서의 수요는 소비자의 효용극대화에 대한 노력에서 나온다. 소득은 한정돼 있으며 이 한정된 예산 안에서 효용 Utility(만족도)을 극대화할 수 있도록 최적의 선택을 해야 한다. 이 선택의 결과가 소비자의 수요행위로 나타난다. 수요행위는 곧 소비자의 수요곡선으로 나타나며, 이를 통해 시장수요곡선을 도출할 수 있다 . % 효용이란 소비자의 주관적 만족도이기에 객관적인 측정이 불가능하다. 그래서 여기선 기수적 효용이 아니라 서수적 효용의 개념을 채택한다. 기수적 서수적 효용의 개념을 설명하자면 다음과 같다. 쥬스 120, 차 80, 물 40의 만족도를 준다고 한다. 기수적 효용은 쥬스와 차의 효용 차이, 차와 물의 효용 차이, 그리고 이로부터 무엇이 효용이 더 큰가에 대해 정확히 알 수 있..

고급 정렬 고급 정렬들은 평균 수행시간이 Θ(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)이며, 어떤 문제 안에서 크기만 다를 뿐 성격이 똑같은 작은 문제 포..