알고리즘 공부하면서 알게되는 내용들을 정리하고 잊어버지않게 기록으로 정리합니다.
- 가능한 모든 경우의 수를 탐색하면서 요구조건에 충족되는 결과만을 가온다.
- 강력한 점은 예외없이 100%의 확률로 정답을 출력한다.
- 완전탐색자체만으로 알고리즘이라고 부르기 어렵다. => 문제 푸는 방법이라고 이해하는게 좋다.
- 답으로 가능한 경우의 수가 많은 경우에는 완전 탐색으로는 해결하기 어렵다. 해당 문제를 잘 파악하는게 중요하다.
👌 완전 탐색 레시피
- 문제에 처음 접근해야 하는지에 대한 대략적인 지침.
- 존재하는 모든 답을 하나씩 검사하므로, 걸리는 시간은 가능한 답의 수에 비례해야한다.
최대 크기의 입력을 가정했을 때, 제한 시간안에 풀이 가능한지 파악해야한다.
만약 계산 불가능이라면 다른 알고리즘을 사용한다.
- 가능한 모든 답의 후보를 만드는 과정을 여러개의 선택으로 나눈다. 각 선택은 답의 후보를 만드는 과정의 한조각이 되어야한다.
- 그 중 하나의 조각을 선택해 답의 일부를 만들고, 나머지 답을 재귀호출을 통해 만든다.
- 조각이 하나밖에 남지 않은 경우, 혹은 하나도 남지 않은 경우에는 답을 생성했으므로, 이것을 기저사례(base case)로 처리한다.
👌👌 완전 탐색 실전 이용예시
- 입력으로 주어지는 데이터(n)의 크기가 매우 작다.
- 답의 범위가 작고 임의의 답을 하나 선택했을 때 문제 조건을 만족하는지 역 추적이 가능한지 파악해야한다.
- 여러 문제 조건 중 한 조건을 고정시키면 문제 풀이가 간단해진다.
- 문제를 해결하는 과정에서 그 순간순간이 최적이라고 생각되는 결정을 하는 방식의 알고리즘.
- 하지만 순간마다의 최선의 결정이 전체 문제에서 최선의 해결책이 되지 않는다.
- "우리는 인생의 순간에서 매번 최선의 결정을 하게 되지만 그것이 언제나 '최선'이 아니듯이...
- Greedy 알고리즘의 가장 큰 장점은 계산 속도에 있다.
- 특수한 조건이 만족되어야 사용할 수 있다.
- 탐욕 선택 속성(Greedy Choice Property)
- 이전의 선택이 이후에 영향을 주지 않어야한다.
- 당장의 상황에서 목표를 위해 가장 도움이 되는것이라고 할만한것을 고를 수 있는가.
- 선택한 것을 버리고 다른것을 취하지 않는다. 이것이 DP(Dynamic Programmin)와 가장 큰 차이점이다.
- 최적 부분 구조(Optimal Substructure)
- 부분 문제의 최적 겨로가가 전체에도 그대로 적용된다.
- 문제애 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.
👌 그리디 알고리즘 레시피
- 문제의 답을 만드는 과정을 여러 부분 문제로 나누어준다.
- 각 부분 문제마다 어떠한 우선순위(조건)으로 탐욕적 선택을 할지 결정한다.
- 2번에서 어떠한 방식을 생각해 냈다면 특수한 조건( 1. 탐욕 선택 속성, 2. 최적 부분 구조)를 만족하는지 생각한다.
- 하나의 문제를 단 한번만 풀도록 하는 알고리즘이다.
- 재귀적으로 함수를 호출하지 않아도 된다.
- 동적 프로그래밍은 다음의 가정하에 사용이 가능하다.
- 큰 문제를 작은 문제로 나눌 수 있다.
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하게 사용이 가능하다.
👌 다이나믹 프로그래밍 레시피
- 큰 문제가 있을 때 그것의 가장 작은 문제부터 생각한다.
- dp[0], dp[1], dp[2], dp[3] ... dp[n] 이렇게 작은 문제를 해결하다보면 규칙을 발견하게 된다.
- 때문에 dp[4]를 해결할 즈음에는 이전에 구해놓은 작은 문제들인 dp[0], dp[1], dp[2], dp[3]을 이용해 점화식을 도출할 수 있다.
👌👌 문제 접근 방법
- Bottom-up 방법 "
- 가장 작은문제부터 해를 구하여 원래 문제의 해에 도달하는 문제풀이이다.
- 메모이제이션을 통해 상향식으로 정복해 나간다.
- 주로 "반복문"를 이용하여 문제를 푼다.