기록기록 우는 갈매기

이진탐색 알고리즘이란? 크기가 n인 정렬된 배열 s에 x가 있는지 결정하는 재귀 알고리즘 알고리즘 설계 전략 배열의 중간에 위치하고 있는 값이 x와 같은 경우 성공을 리턴, 그렇지 않으면 분할(Divide) 분할(Divide) : 배열을 반으로 나누고, x가 배열의 중간에 있는 값보다 작으면 왼쪽 배열을 선택(오른쪽 배열은 버림), 크면 오른쪽 배열을 선택(왼쪽 배열은 버림). 정복(Conquer) : 선택한 배열을 갖고 다시 x를 찾는다. 알고리즘 수도 코드 index location (index low, index high) { index mid; if(low > high) return 0; else { mid = ⌊(low+high) / 2⌋; //배열 가운데 값을 구함 if (x == s[mid]..

divide-and-conquer의 핵심은 재귀호출이다. 전체를 풀 때와 부분을 풀 때의 풀이가 같은 경우 큰 문제를 작은 문제로 쪼개서 해결하는데, 이 때 top-down 방식과 bottom-up방식이 있다. top-down: 처음부터 큰 문제를 방문 후 작은 문제를 호출, 재귀(recursive)방식 사용 bottom-up: 작은 문제들부터 해결 후 이를 바탕으로 더 큰 문제들을 해결, 반복(iterative) 방식 사용 top-down과 bottom-up 모두 문제를 쪼갠다는 점에서 비슷해보일 수 있지만 시도 자체가 다르다. top-down은 처음부터 큰 문제를 해결하려고 시도하지만, bottom-up은 큰 문제부터 해결하려하지 않고 작은 문제부터 시작한다. divide-and-conquer은 위의..

점근 표기법(asymptotic notation)은 시간 복잡도 또는 공간 복잡도 함수의 증가 양상을 구분하기 위해 사용하는 표기법이다. 대표적으로 상한(O), 하한(Ω), 교집합(Θ)이 있다. 먼저 간략하게 뜻을 말하면 아래와 같다. O(f(n)) : 상한, 아무리 느려봤자 f(n) 정도이다. f(n)보다 빠르거나 같다. Ω(f(n)) : 하한, 아무리 빨라봤자 f(n) 정도이다. f(n)보다 느리거나 같다. Θ(f(n)) : 차수, 상한과 하한을 함께 제시. 두 집합의 교집합 하나 하나 알아보기전에, 앞서 말한 '빠르다', '느리다'라는 표현에 대해 그 뜻을 정리할 필요가 있다. 함수의 차수가 높을수록 더 빠를 것 같지만, 차수가 낮은 것이 더 빠르다고 표현한다. 즉, 그래프 상으로 그렸을 때 더 아..

알고리즘을 짰다고해서 끝나는 것이 아니다. 짜긴 짰는데 결과 값을 얻어내기까지 어마어마한 시간을 요구한다면 소용이 없기 때문이다. 따라서 분석을 통해 알고리즘의 효율성을 판단해야한다. 알고리즘의 성능은 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)로 표현한다. 시간복잡도: 얼마나 빠른가? 공간복잡도: 얼마나 많은 공간을 차지하는가? 우선, 시간 복잡도 측정에 대해 주로 다뤄보도록 하겠다. (공간 복잡도는 나중에 중간중간 나올 예정) 시간복잡도 시간복잡도(Time Complexity)는 알고리즘이 '얼마나 빠른가'를 나타내는 함수이며, 보통 함수 이름으로 T(n)을 사용한다. 즉, n과 T(n)의 관계를 구하는 것인데, 이 때 n은 input size가 된다. 시..