기록하는 습관 "기습"

특수 정렬 지금까지 봐온 정렬들은 모두 원소끼리 비교해서 정렬하는 비교 정렬 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)이며, 어떤 문제 안에서 크기만 다를 뿐 성격이 똑같은 작은 문제 포함되어 있는 것..

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

데이터 통신 개요(Data Communication) 데이터 Data는 '주어진 어떤 것'이란 의미의 라틴어 datum의 복수형이다. 사용자에 의해 합의된 형식으로 사실, 개념, 명령 등을 표현한 것이다. 통신 Communication은 정보 공유를 의미하는 라틴어 communicare에서 유래되었다. 따라서 통신은 정보의 공유를 의미한다. 데이터 통신은 우리가 학교에서 배웠던 '광케이블' 같이 특정 전송매체를 통해 두 장치 간에 이뤄지는 데이터 교환을 의미한다. 이러한 통신 시스템은 다음과 같은 3가지 기본 특성을 지닌다. 전달성 Delivery : 목적지에 정확히 데이터가 전달되어야 한다. 정확성 Accuracy : 전송 도중, 신호가 감쇄하거나 비트가 상실하기에 데이터 그대로 정확히 전달해야 한다...

비효율성 어쩌다 보니 해외 유튜브에서 애플워치 울트라만으로 하루 보내기 같은 영상을 보았다.문득 이런 생각이 들었다. 정말 LTE 통신이 가능한 스마트워치가 보조용 이외에 유의미할까? 몇 달 전, 스마트폰을 바꾸면서 갤럭시워치 5와 버즈 프로2를 함께 구매했다. 여러 용도를 고민해보고 구매한 거라 후회는 없다. 하지만 내 생각만큼 효율적이지 않다는 것을 곧 깨달았다. 블루투스 모델을 들고 있다는 것은 대부분의 경우, 스마트폰도 항상 소지하고 다닌다. 알림을 빠르게 확인해야 하는 상황 말고는, 전화를 주고받는 상황이나, 메세지를 주고 받는 상황에서 '압도적으로' 스마트폰이 편리하다. 폰과 워치는 포지션이나 폼팩터에서 차이를 보이지만 '용도'에서 동일함을 보인다면 이야기가 달라진다. 그렇다고 LTE 모델..

소비자 물가 지수 CPI Consumer price index 인플레이션율 Inflation rate : 지난 기간 대비 물가 지수의 변화 근원 소비자물가지수 Core CPI : 단기간 변동성이 큰 식료품과 에너지를 제외한 모든 재화와 서비스의 전반적인 비용 지표. 생산물가지수 Producer price index PPI : 기업들이 구입하는 재화 묶음의 비용 지표. 소비자가 구입하는 재화와 서비스의 전반적인 비용을 나타내는 지표이다. 이를 통해 시간의 경과에 따른 생계비가 어떻게 변동하는지 알 수 있다. 인플레이션율 측정에 사용된다. 소비자 물가지수를 구하는 식은 다음과 같다. CPI = 재화묶음 구입 비용 / 기준연도 재화묶음 구입비용 * 100 CPI 지난 기간 대비 물가지수의 상승률을 인플레이션율..