기록하는 습관 "기습"

사회복지제도의 분석 소비자 이론을 응용해서 사회복지제도와 관련된 세 가지 지원방식의 차이를 비교해볼 수 있다. 여기서 어느 보조 방식을 쓰든 예산은 한정돼있다고 가정한다. 이렇게 하면 각 보조방식의 차이를 분명히 나타낼 수 있다. 그리고 비교의 편의를 위해서 두 개씩 각각 비교를 한다. 현금보조와 현물보조 현금보조는 말그대로 현금을 지원하는 것이고, 현물보조는 쌀이나 물, 라면과 같이 생활에 필요한 물품을 직접 주는 것이다. 보조를 받기 전인 기존 예산선은 선분 AB다. 여기서 만약 현금보조를 받는다면 예산선은 선분 CD로 이동한다. 그러나, 현물보조를 받는다고 가정하면 꺾인 선 AF'D이다. 이는 선분 BD만큼의 쌀을 공급받는다는 것을 알 수 있다. 이 두 경우의 차이는 꺾인 선 CF'A가 포함되어 있..

레드블랙트리 Red-Black Tree 이전 이진검색트리에서, 평균 수행시간이 O(log n)이라 했다. 그러나 트리의 균형이 나쁘다면 최악의 경우 n에 비례한 시간이 걸린다. 이를 보완하기 위한 '균형 잡힌 이진트리'가 바로 레드블랙트리다. 이진검색트리에 몇 가지 조건을 추가해서 균형 잡힌 트리가 되도록 한다. 트리의 높이, 검색/삽입/삭제 연산이 모두 O(log n)의 시간이 걸린다. 레드블랙트리는 모든 노드에 빨강 혹은 검정을 칠하되 다음과 같은 특성을 만족해야 한다. 루트는 블랙이다. 모든 리프(NIL, Null값과 같다)는 블랙이다. 노드가 레드면 그 노드의 자식은 반드시 블랙이다. 루트 노드에서 임의의 리프노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 같다. 참고로 레드블랙트리의 리프노..

검색트리 데이터의 저장과 검색은 자료구조와 알고리즘 분야에서 매우 중요하다. 수행시간에서 커다란 차이를 보이기 때문이다. 데이터의 저장과 검색을 효율적으로 하기 위해서는 적절한 자료구조 및 알고리즘의 사용을 필요로 한다는 사실은 자명하다. 만약 데이터가 들어오는 순서대로 배열에 저장한다고 가정해보자. 자료수가 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) 계수 정렬 기수 정렬 기본적인 정렬 알고리즘 단어 그대로 기본적이며 간단히 구현 가능한 알고리즘이다. 계수가 작을 때는 타 알고리즘에 비해 더 빠른 결과를 얻을 수도 있..