알고리즘 4가지

1. Brute Force

• 하나하나 모든 경우의 수를 보고 값을 내놓는 알고리즘 방식
• 시간도 오래걸리고 비효율 적이지만, 직관적이고 명료하기 때문에 구현이 쉽고, 답을 확실하게 찾을 수 있다.
• 인풋이 작을 경우에는 이 방식을 사용해도 아무 상관이 없지만, 만약 인풋이 엄청나게 큰 경우에는 비효율적이다. 하지만 다른 효율적인 알고리즘을 찾기위한 가장 첫 번째이자 기초적인 단계가 이 방식이기 때문에 잘 알아야 한다.

예시

덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하라
nums = [2,7,11,15], target = 9

def twoSum(nums, target):
   for i in range(len(nums)):
      for j in range(len(nums)):
        if num[i]s + nums[j] == target:
           return [i, j]

이런식으로 하나 하나의 상황을 고려해서 직관적으로 모든 조합의 상황을 고려해서 답을 내는 것이다.

결론 알고리즘을 해결하는 방식중 가장 기본적인 방법이고, 직관적이고 정확하지만, 시간이 오래걸려 비효율적이다.

2. Divide and Conquer(분할 정복 방식)

• 알고리즘에서 어려운 축에 속하는 방식으로, 이 방법을 사용하기 위해서는 재귀에 대한 개념의 이해가 필요한다.
• Divide, conquer, combine이 세 단계를 가지고 문제를 해결한다.

2-1 합병정렬(Merge sort)

두 리스트에 있는 값을 차례로 추출 한 뒤 비교 후 작은 값을 새로운 리스트에 차례로 넣어주는 방식으로 정렬하는 방법

2-2 퀵 정렬(quick sort)

• 하나의 기준(pivot)을 정한뒤 왼쪽은 기준보다 작은 값, 오른쪽은 기준보다 큰 값을 배분하는 방법으로 리스트 내부에서 정렬해 나가는 방법
• 퀵 정렬은 따로 리스트를 합치거나 할 필요가 없기 때문에 combine의 단계는 필요가 없다. 하지만 divide 단계, 리스트를 정렬하는 것이 매우 중요하다. 이 부분을 'partition' 이라고도 한다.

3. Dynamic Programming(동적 계획법)

• 큰 문제를 작은문제의 해결을 통해 해결하는 방법(최적부분구조)
• 부분 문제의 답을 통해 최적의 답을 구할 수 있다.

사용조건

• 중복되는 부분이 있다.
• 최적부분 구조가 있다.

3-1 Memoizaion(재귀, 상향식 접근)

• 위쪽에서 부터 필요한 계산을 요구해서 해결해 나가는 방식으로 기존에 계산 한 값을 cache에 저장해 놓고 필요할때 꺼내는 방식이다. 필요하지 않은 계산은 하지 않는다.

3-2 Tabulation(반복문, 하향식 접근)

• 하나의 테이블에 작은값부터 하나씩 채우어서 필요한 n값을 구해나가는 방식이다. 필요하지 않은 계산도 해야 할 필요가 있다.

4. Greedy Algorithm(탐욕적 알고리즘)

• 미래를 생각하지 않고 눈에 보이는 답을 탐욕적으로 선택해 문제를 해결하는 방식
• 눈 앞에 보이는 답만을 쫒기 때문에 간단하고 빠르나, 항상 최적의 답을 보장하지 않는다.

Greedy Algorithm을 사용해야하는 이유?

• 다른 알고리즘의 문제해결이 너무 느릴때, 굳이 최적의 값이 필요하지 않고 눈 앞의 당면한 과제의 값이 필요할때

Greedy Algorithm의 사용 조건

1. 최적부분 구조가 존재하는가?
2. 탐욕적 선택속성(Greedy choice Property) - 각 단계에서 탐욕스런 선택이 최적의 선택이 존재 할때 사용