with with

- 정의 이전 두 항의 합이 다음항이 되는 수열이다. - Pseudocode // Iterative way public static int IterFib (int n) { index i; int[] f = new int[n+1]; if (n

* 배열의 인덱스가 1부터 시작한다고 가정합니다. ([1] = 1번째 와 같이 이해하기 쉽도록) - 알고리즘 정의 정렬이 된 배열에서 찾고자 하는 원소가 나올 때 까지 탐색하는 알고리즘. 탐색하는 방법은 low, high의 가운데, mid와 비교하여 찾고자 하는 값이 mid보다 크면 오른쪽, 작으면 왼쪽의 배열에서 다시 탐색한다. - Pseudocode // Iterative way public static index BinSearch (int n, keyType[] S, keyType x) { index location, low, high, mid; low = 1; high = n; location = 0; while (low

* 배열의 인덱스가 1부터 시작한다고 가정합니다. ([1] = 1번째 와 같이 이해하기 쉽도록) - 알고리즘 정의 찾고자 하는 원소가 나올 때 까지 인덱스의 처음부터 순차로 탐색하는 알고리즘. - Pseudocode public static index SeqSearch(int n, keyType[] S, keyType x) { index location = 1; while (location n) location = 0; return location; } 크기가 n인 배열 S에서 x를 찾는 알고리즘. location이 n보다 작거나 x를 발견하지 못할 경우 location을 1씩 증가하며 탐색 찾은 경우, 또는 배열의 끝까지 탐색한 경우 while문을 빠져나온다. 끝까지 탐색한 경우에는 location을 ..

재귀함수를 이용하여 구현된 알고리즘의 경우 시간 복잡도 함수를 구하다 보면 재귀식으로 이루어진 시간 복잡도 함수를 마주하게 된다. 이런 경우 재귀식을 일반식으로 수정해야 하는데, 그 방법을 알아보자. * 선형인 재귀식의 경우만을 다룹니다. - Homogeneous case f(n) = 0 인 형태의 식을 homogeneous라고 하는데, 이런 경우의 재귀식을 계산하는 법을 알아보자. 위 식을 생각해보자. tk 항으로 이루어진 재귀식이다. 이 경우 아래와 같은 특성 방정식(characteristic equation)으로 변환 가능하다. 여기서 두 가지 경우로 나뉘는데, (r-1)(r-2)(r-3) 처럼 중근을 갖지 않는 경우와 (r-1)(r-2)^2 처럼 중근을 갖는 경우로 나뉘게 된다. * 중근을 갖지 ..

Time complexity 시간 복잡도는 알고리즘이 수행되는 데 걸리는 시간을 의미하며, 시간 복잡도가 클 수록 알고리즘이 수행 되기까지 걸리는 시간이 길다는 것을 의미한다. 시간 복잡도를 계산하기 위해선 2개의 파라미터가 필요하다. - Input size 입력으로 들어온 값의 크기를 의미한다. 입력으로 들어온 값은 배열일 수도, 특정 값이나 문자열, 혹은 graph와 같이 vertices, edges가 들어올 수 있다. - Basic operation 알고리즘은 여러 줄의 코드로 이루어진다. 그 중 핵심이 되는 코드를 기본 연산으로 삼아서 시간 복잡도를 계산한다. 예로 들어 순차 탐색 알고리즘의 경우에는 배열의 특정 index와 찾고자 하는 값의 비교 연산이 이에 해당한다. 시간 복잡도 분석은 모든 ..