강의노트/알고리듬 (8) 썸네일형 리스트형 [알고리듬] 6주차: Backtracking Divide-and-Conquer 문제(Computing problem)를 효율적으로 풀기 위한 일반적인(general) 방법론 점화식은 보통 이런 형태: $T(n) = rT(n/c) + O(f(n))$ Backtracking 탐색 알고리즘에서 많이 쓰는 기법(트리나 그래프 등) 미로에서는 일단 진행해보고 막다른 길에 다다르면 뒤로 돌아온다 그리고 아직 가보지 않은 길로 다시 진행한다. 이게 백트래킹 올바른(또는 최선의) 결정의 sequence를 통해 점진적으로 해를 구성한다 여러 개의 갈림길 중 하나를 골라야 할 때는 모든 길을 다 가본다. 그리고 그 중 최상의 것을 선택한다. 어차피 그 갈림길들 중 하나는 답임. N Queens problem $n \;\times\; n$ 체스보드 위에 서로 공격받지.. [알고리듬] 5주차: Divide-and-Conquer Master Theorem ⓐ $f(n) = \Omega(n^{\log_c{r} + \epsilon}$ = $f(n)$의 지수가 $\log_c{r}$에 비해 크면 $T(n) = O(f(n))$ ⓑ $f(n) = \Theta(n^{\log_c{r}}\log^k{n}) \;\;for\;\;some\;\; k \geq 0$ = $f(n)$의 지수가 $\log_c{r}$과 비슷하면 $T(n)=O(f(n)\cdot\log{n})$ ⓒ $f(n) = O(n^{\log_c{r} - \epsilon})$= $f(n)$이 $n^{\log_c{r}}$에 비해 작으면 $T(n) = O(n^{\log_c{r}})$ $f(n)$은 non-recursive한 부분 Solving Recurrence $T(n)=2T(n/2) + O.. [알고리듬] 4주차: Divide-and-Conquer Recursion - Simplify and Delegate - Reduction - 종료 조건: Base case Correctness: Induction으로 증명 Time complexity analysis: 점화식부터 구한다 Divide-and-Conquer 나누고(Divide) 정복한다(Conquer) -> 분할정복 Recursion 활용 Ex) Mergesort, Quicksort Pattern 분할정복은 일반적으로 다음의 세 단계로 진행된다. ① Divide 문제를 나눈다.(Mergesort에서는 2개) 같은 문제의 더 작은 instance로 나눈다. ② Delegate (Conquer) 각각의 더 작은 instance에 대해 재귀호출을 한다. ③ Combine Mergesort의 Merge에.. [알고리듬] 3주차: Homework#1 1. 반복문을 사용하지 않고 재귀로만 다음을 구현한 후 시간 복잡도 분석하기 - 배열에서 최솟값 찾기 - 배열의 모든 원소의 총합 구하기 - 선택 정렬 https://t0pli.tistory.com/199 2. Pancake Sorting(Jeff Erickson의 책 의 Exercise 9(a),(b) in Chapter 1 of [E]) (a): 팬케이크가 $n$장일 때 $O(n)$번 뒤집는 알고리즘을 구하면 됨 (b): 모든 양의 정수 $n$에 대해 정렬을 위해 $O(n)$ filps가 필요한 배열 구성을 구하면 됨 https://t0pli.tistory.com/200 (a)는 그냥 내가 짠 코드를 설명하면 끝이었다. (b)는 생각이 좀 필요했다. 내가 제시한 답은 내림차순으로 정렬된 배열이다. 내.. [알고리듬] 3주차: Recursion - Mergesort, Quicksort * 피보나치 곱셈의 시간복잡도 분석 한 자리씩 곱해서 10으로 나눈 나머지를 각 자리에 설정하는 방식이다. 교수님피셜) 내가 짠 건데 틀린 거다. 어디가 틀렸는지 찾아봐라 답: index가 범위를 넘어감 $m$은 $X$의 자리수고 $n$은 $Y$의 자리수인데, $k$의 범위가 $0\;\sim\;n+m-1$이고 $i$의 범위가 $0\;\sim\;k$이므로 $Y[k\,-\,i]$에서 $i=0$이고 $k=n+m-1$이면 $Y[n+m-1]$이 되어 $m \gt n$이면 index bound를 넘어간다. Ex) $n=5,\;m=3$고 $k=2$일 때 $i=0\;\sim\;2$이므로 연산은 다음과 같이 진행된다. $X[0] \times Y[2]$ $X[1] \times Y[1]$ $X[2] \times Y[0]$ .. [알고리듬] 2주차: 정렬 Selection sort ① $n$개 수 중 최소값을 찾는다 ② 그 수를 맨 앞으로 이동 ③ 그 수 다음부터 $n - 1$개 수에 대해 위 작업 반복 -> $i$번째 반복에서 앞의 $1$ ~ $(i - 1)$번째까지는 정렬이 되어 있음 시간복잡도: $O(n^2)$ Insertion sort ① $n$개의 수 중 $i$번째 수를 꺼냄 ② $1$ ~ $i-1$번째 중 올바른 위치에 삽입 ② $i=2$부터 $n$에 대해 위 작업을 반복 -> $i$번째 반복에서 앞의 $1$ ~ $i - 1$번째까지는 정렬이 되어 있음 시간복잡도: $O(n^2)$ *Best case: $\Theta(n)$ Bubble sort 이웃한 수끼리 교환으로 정렬 Merge sort and Quick sort Divide and con.. [알고리듬] 2주차: 시간복잡도 Time Complexity 알고리듬의 수행시간을 '이론적으로' 분석 -> 실제로 수행해보고 시간을 측정하는 게 아니다 실제 수행시간은 환경에 따라 달라진다. - 무슨 코드로 작성했는가? - 컴파일러 버전은 무엇인가? - 알고리즘을 수행하는 기계의 스펙은 어떻게 되는가? - 입력으로 주어지는 데이터의 크기 - 다른 프로세스가 점유한 자원은 얼마나 되는가? - etc. -> 이런 모든 환경적 요인들은 고정되었다고(모두 같다고) 가정한다. 추상화 환경적 요인의 조합은 거의 무한 -> 매번 모든 알고리즘을 구현할 수는 없다. 통상적인 어떤 환경에서 알고리즘 A가 알고리즘 B보다 빨랐다면 다른 환경에서도 그렇지 않을까? -> 환경적 요인을 고려할 필요가 없다: 추상화 Ex) C로 짰든 Java로 짰든 Pytho.. [알고리듬] 1주차 1. 알고리즘의 정의(레시피의 비유) - 알고리즘은 문제를 해결하기 위한 방법, '레시피' - 레시피의 실행 주체는 사람, 알고리즘의 실행 주체는 컴퓨터(기계) -> 구체적 기술이 필요 * 안 중요한 내용 영어: Algorithm 'thm'이니까 따지면 알고리'듬'이 맞는데 일본의 영향을 받아 알고리즘이라고 하는 듯. (일본에서는 Algorithm을 アルゴリズム(아르고리즈무)라고 읽는다.) 2. 문제 - 주어진 입력에 대한 출력의 명확하고 정확한 명세 Ex) 자연수 $x$와 $y$가 주어질 때 $x\,\times\,y$ 3. 컴퓨터 - '컴퓨터'를 하나의 Computation model로 생각할 수 있다. - 컴퓨터마다 연산 속도(또는 performance)는 다르지만 제공되는 연산은 거기서 거기 4. .. Prev 1 Next
