제 6장: 그 외의 알고리즘들(1)

Column: 관계형 데이터베이스를 이용한 정렬과 검색

• 관계형 데이터베이스: 대량의 데이터를 효율적으로 처리(개발과 유지보수 용이)
  • 프로그램을 두개의 역할로 나눠 분담하게 할 수 있기 때문
    • 프로그램을 실행하는 코드
    • 데이터 관리
• 데이터베이스를 활용해 특정 데이터를 정렬하거나 검색 → SQL 언어 사용
• SQL문의 지식과 질 좋은 알고리즘의 학습으로 데이터를 효율적으로 검색하거나 정렬할 수 있다.

66. 미분을 활용해 고차 방정식의 해를 구하는 ‘뉴턴법’

• 뉴턴법: 함수 f(x)가 x축과 만날 때, f(x)와 도함수 f’(x)를 이용해 f(x)=0의 해 x를 구하는 알고리즘
• 예시: $x^2=k$ 일때, $x=±\sqrt{k}$ 이므로, $f(x)=x^2-k$의 올바른 해는 $k$이다.
• 위의 예시에서 $k$를 구하는 방법

  1. 함수 그래프의 임의의 점 $P_0(x_0, f(x_0))$ 에서의 점선의 기울기 → $f(x)=x^2-k$의 도함수 $f’(x)=2x$ 로 구할 수 있으므로,

     i. $f’(x_0)=2_{x0}$

  2. 접선의 기울기 = $\frac{y의 \ 변화량}{x의 \ 변화량}$ 이므로, $P_0$의 접선이 x축과 만나는 점을 $x_1$이라고 하면 $f’(x_0) = \frac{f(x_0)}{x_0-x_1}$이므로, i에 의해

     ii. $2x_0 = \frac{f(x_0)}{x_0-x_1}$

  3. $f(x_0)=x_0^2-k$ 이므로, i에 의해 $2x_0=\frac{x_0^2-k}{x_0-x_1}$ 이 되며, 이 식을 변형하면

     $2x_0(x_0-x_1)=x_0^2-k$ → $x_0-x_1=\frac{x_0^2-k}{2x_0}$ → $x_1=x_0 - \frac{x_0^2-k}{2x_0}$우

  4. 위 식을 $P_1(x_1,f(x_1))$, $P_2(x_2,f(x_2))$에도 동일하게 적용시키면

     iii. $x_2=x_1=\frac{x_1^2-k}{2x_1}$, $x_3=x_2=\frac{x_2^2-k}{2x_2}$, … 이 되어 $x_n=x_{n-1}=\frac{x_{n-1}^2-k}{2x_{n-1}}$따

     따라서, $x_0$ 에 적당한 값을 부여하고, $x_n$, $x_{n-1}$ 값의 차이가 충분히 작아질 때까지 iii의 계산을 반복하면 $x_n$의 값이 $\sqrt{k}$의 근사값이 된다.