[medium 번역, algorithm] 개발자가 필수로 알아야할 6가지 알고리즘

1. sorting 알고리즘 (정렬 알고리즘)

: 배열의 아이템을 순서대로 정렬하는 알고리즘

• 1-1. 버블 정렬 (Bubble Sort)
  _{가장 기본적인 정렬 알고리즘, 인접한 요소들이 순서에 맞지 않으면 반복적으로 교체한다.}
• 1-2. 병합 정렬 (Merge Sort)
  _{분할 정복 전략을 사용하는 알고리즘이다.}
• 1-3. 퀵 정렬 (Quicksort)
  _{평균적으로 n log n의 시간복잡도를 수행하는 가장 인기있는 정렬 알고리즘이다. 빠르고 효율적이다.}
• 1-4. 힙 정렬 (Heap sort)
  _{완벽한 이진 트리(:heap)로 시각화 되는 배열에 의해 작동한다.}

2. Searching 알고리즘 (탐색 알고리즘)

: 자료(data set)에서 요소를 찾기 위한 알고리즘

• 1-1. 이진 탐색 (Binary Search)
  _{정렬된 배열은 반씩 나뉘고, 아이템들은 배열의 가운데 값과 비교되는 분할 정복 기법을 사용한다. 만약 일치하는 값을 찾으면, 가운데 값이 반환된다.}
• 1-2. 너비 우선 탐색 (Breadth-First Search, BFS)
  _{루트 노드에서 시작해 인접한 모든 노드들을 탐색하는(explore) 알고리즘이다.}
• 1-3. 깊이 우선 탐색 (Depth-First Search, DFS)
  _{그래프의 첫 번째 노드에서 시작해 깊이 깊이 파고들어가며 진행한다. 우리가 찾는 값을 만나거나, 자식 노드가 없을 때까지.}

3. 동적 계획법 (Dynamic Programming, DP)

: 전체에 대한 문제가 작은 하위의 문제들에 의존하고 있을 때 최적화된 솔루션이다. 작고 단순한 하위 문제부터 해결해 나감으로써 전체의 문제를 해결하는 기술이다.

4. 재귀 알고리즘 (Recursion Algorithm)

: 재귀는 작은 인스턴스들의 해결들에 의해 동일한 문제가 해결될 때 쓰인다. 팩토리얼을 짜는 것이 재귀 프로그래밍의 고전적인 예이다.

• 모든 재귀함수들은 다음의 단계를 거친다.
  1. 재귀 프로그램은 시작할 때, 흔히 seed value를 필요로 한다. 이것은 다음 함수로 전달되는 파라미터로 쓰이거나, 재귀적 계산을 위한 seed value를 설정하는 비재귀 함수가 제공함으로써 충족된다.
  2. 현재 값이 기본 case에 의해 진행되고 있는 지를 확인해라. 만약 그렇다면 값을 진행시키고, 반환해라.
  3. 더 작거나 간단한 하위 문제를 위한 해결방법으로 바꿔봐라.(rephrase)
  4. 하위 문제에다 해당 알고리즘을 정의해봐라
  5. 답으로 만들기 위해, 결과들을 결합해라(combine)
  6. 최종 결과를 반환해라

5. 분할 정복

: 분할 정복 알고리즘은 같거나 관계있는 유형의 두 개 이상의 하위 문제로 재귀적으로 나눈다. 하위 문제들은 간단하고, 바로 해결될 수 있는 문제들이어야 한다.

• 분할 정복을 위한 세 가지 구성 요소
  1. 주어진 문제를 하위 문제들로 쪼개라
  2. 각각의 하위 문제들을 한 번에 재귀적으로 해결해라,
  3. 하위 문제들을 전체 문제에 대한 솔루션을 얻기 위해 합쳐라

6. 해싱

: 해싱은 키와 값을 매핑해 해시 테이블로 만들 위해 해시 함수를 사용하는 테크닉이다. 이를 통해 요소에 더 빠르게 접근할 수 있다. 매핑의 효율성은 해시함수의 효율성에 의해 결정된다.

결론

어떤 걸 써야할 지 결정하기 어렵다. 이는 자주 개인의 선호와 관점에 의해 선택된다. 하지만, 이 포스팅의 몇몇 알고리즘은 개발자들이 필수적으로 알고 있어야 한다.

(출처 미디엄 : 6 Algorithms Every Developer Should Know)