알고리즘 패러다임

알고리즘 패러다임: 알고리즘 접근 패턴

 

1. Brute Force : 가능한 모든 경우를 다 시도한다

장점: 직관적이고 명확하다. 모든 경우의 수를 다 따지기 때문에 답을 확실하게 찾을 수 있다.

단점: input의 크기가 커지면 오래 걸린다.

 

---

2. 분할 정복 : 문제를 부분 문제로 나눠, 부분 문제를 해결한 값들을 합쳐 기존 문제를 해결한다.

분할 정복과 재귀의 차이

https://velog.io/@sossont/%EC%A2%85%EB%A7%8C%EB%B6%81-%EB%B6%84%ED%95%A0-%EC%A0%95%EB%B3%B5Divide-and-Conquer

[종만북] 분할 정복(Divide and Conquer)

큰 예시로 합병 정렬, 퀵 정렬이 있다.

 

---

3. 다이나믹 프로그래밍: 한 번 계산한 결과를 재사용하는 것

필요 조건

-최적 부분 구조: 부분 문제의 최적의 답을 이용하면 기존 문제의 최적의 답을 구할 수 있다

-중복되는 부분 문제: 문제가 중복되는 부분

 

최적 부분 구조가 있다 ( = 부분 문제를 이용하여 기존의 문제를 해결할 수 있다)

하지만 부분 문제를 풀 때, 부분 문제가 중복이 될 수 있다.

->이럴 때 다이나믹 프로그래밍을 사용하면 된다!

 

다이나믹 프로그래밍 종류

1. Memoization : 캐시에 저장해뒀다가 쓰는 방법(재귀처럼 사용)

장점 : 필요한 것만 부르면 돼서 불필요한 값은 구하지 않아도 된다.

단점 : 재귀 기반이기 때문에 스택 오버 플로우가 될 수도 있다.

 

2. Tabulation : 테이블처럼 만들어서 사용하는 방법(반복문 사용)

장점 : 반복문 기반이기 때문에 스택 오버 플로우가 일어나지 않는다.

단점 : 반복문 기반이기 때문에 불필요한 값을 구해야 할 수도 있다.

 

---

4. Greedy Algorithm: 눈 앞에 보이는 최적의 경우를 선택한다.

장점: 구현이 간단하고 빠르다.

단점: 완벽한 정답을 보장하지 않는다.

 

Greedy Algorithm으로 최적은 답을 보장하는 두 가지 조건

-최적 부분 구조: 부분 문제의 최적의 답을 이용하면 기존 문제의 최적의 답을 구할 수 있다

-탐욕적 선택 속성: 각 단계에서 탐욕스러운 선택이 최종 답을 선택하는 데 최적의 선택이다