집밖은 위험해

알고리즘과 복잡도

- 복잡도가 O(n) 처럼 작은 경우가 있지만 복잡도가 매우 큰 알고리즘도 많음

NP 완비 문제

- 풀기 쉬운지 어려운지도 모르는 문제들

P 문제

- 결정론적 알고리즘 deterministic algorithm으로 다항식 시간에 해결할수 있는 문제

- 결정론적 알고리즘 : 명확하게 결정되어있어 데이터 입력시 어느 순서대로 동작하는지 알수있는 알고리즘

NP 문제

- 비결정론적 알고리즘 nondeterministic algorithm으로 다항식 시간에 해결할수 있는 문제

- 비결정성 알고리즘 : 결정 가능한 경우가 여러개로 나뉘어져 적당한 경로러 선택해 나가는 알고리즘

=> 가장 적절한 경로를 잘 선택한 경우 다항식 시간으로 해를 찾을수 있는 문제를 NP 문제라 부름

근사 알고리즘 approximation algorithm

- NP문제는 최악의 경우 복잡도가 지수적으로 됨.

 => 최적해는 아니더라도 최적해에 가깝기만 하면 됨.

- 최적해에 가까운 근사해를 구하는 (결정론적) 알고리즘

휴리스틱 알고리즘

- 해를 얻을때까지 경험해가는 알고리즘

- 최적해의 계산 비용이 크고, 근사해로도 충분한 경우 사용

백트래킹법

- 모든 가능성을 조사하지 않고도 최적해를 얻을수 있는 문제도 존재

- 하나의 시행을 통해 조사하다가 해를 구하지 못하면 이전으로 되돌아가 다른 경우를 조사

=> 해를 찾을떄까지 백트래킹 후 다른 경우를 조사하는 방법

백트래킹 방법의 예시

1. 수도크 플기

분할 통치법

- 잘 파악된 부분을 조금씩 넓혀가 결과를 찾음

- 해에 접근하는 방법에 따라 능률이 좋거나 나빠지기도 함.

탐욕법 greedy algorithm

- 현재 상태에서 볼때 가장 좋은 경우를 따라가는 방법

- 당장의 성능 개선이 보임

- 지역적 최선의 선택이 전역적으로 좋다고 보장할 수 없음

=> 당장의 최적의 방향으로만 쫓다간 지역해에 수렴함. 전역해에 도달못하는 경우 발생

탐욕법의 예시

1. 다익스트라 알고리즘

2. 프림 알고리즘

재귀적인 recursive 방법의 한계

- 재귀적 방법은 문제를 간단한 부분 문제로 만듬

- 하지만 부분 문제의 크기 합을 작게 유지시켜야만 효과적임

- 부분 문제의 크기가 균형이 맞지 않을시 복잡도가 지수적으로 증가

 => 재귀적인 방법의 한계로 인해 동적 계획법 이용

동적 계획법 dynamic programming

- 부분 문제들의 답을 별도의 표에 기억

- 필요할때마다 표를 참조

   * 재귀적 방법의 문제 : 재귀적인 방법에선 그 표의 값을 매번 새로 계산했었음

=> 동적 계획법은 부분 문제의 답을 기억. 이후 다시 계산하지 않음

균형법

- 분할 통치법에서 모든 문제를 같은 크기의 부분 문제로 나눠서 풀거나, 균등하지 않게 나눌수도 있음.

=> 부분 문제의 크기를 균등하게 하면 더 좋은 알고리즘을 얻을 수 있음

균형법의 예시

- 합병 정렬 알고리즘

알고리즘설계기법

분할 통치법 divide and conquer

- 성능 좋은 알고리즘을 설계하기 위해 널리 사용됨

- 해결하려는 문제(크기 n으로 가정)를 작은 여러 문제로 분할

 => 원래 문제의 답을 쉽게 얻는 방향으로 분할 필요

- 분할된 문제를 해결후 간단한 처리로 통합함

분할 통치법의 예시

1. 합병 정렬 merge sort

2. 하노이의 탑

좋은 알고리즘

- 좋은 알고리즘들은 문제해결 방법과 고속화 기법에서 공통점이 많음

좋은 알고리즘 - 퀵 정렬과 합병 정렬의 예시

1. 데이터가 있는 배열을 두개로 나눔

2. 두 배열을 각각 정렬

3. 그 두 배열을 연결

=> 이를 알고리즘 설계 기법 이라고 부름

개발자와 알고리즘 설계

- 해결해야할 새 문제가 발생할때 기존 알고리즘 설계 방법을 응용할수있는지 고민하는것이 새로 개발하는것보다 줄일수 있어 중요

알고리즘 설계 기법의 종류

1. 분할 통치법 divide and conquer

2. 균형법

3. 동적 계획법 dynamic programming

4. 탐욕법 greedy algorithm

5. 백트래킹법 dacktracking

6. 근사해법 approximation algorithm