기본 알고리즘 유형

기본 알고리즘 개념

1. 그리디(탐욕법)

그리디란?

• 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘.

예시

-> 그리디 알고리즘의 대표적인 예시는 거르슴돈 문제이다. 즉 '현재 상황에서 특정한 기준에 따라 가장 좋아 보이는 것만을 선택'해서 최적의 해를 구해야 하는것.
(다익스트라 최단 경로 알고리즘), (크루스칼 알고리즘)

2.구현

구현?

• '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'
  (완전 탐색 -> 모든 경우의 수를 주저 없이 다 계산하는 해결 방법)
  (시뮬레이션 -> 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행)

3. 탐색

탐색?

• 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. 대표적으로 코딩 테스트에는 그래프와 트리 자료구조 안에서 탐색 하는 문제를 자주 다룬다.

예시

-> DFS와 BFS 등이 있다

4. 정렬

정렬?

• 데이터를 특정한 기준에 따라서 순서대로 나열 하는것.

4-1 거품정렬 (Bubble Sort)

• Bubble Sort는 Selection Sort와 유사한 알고리즘으로 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘.
• 이름의 유래로는 정렬 과정에서 원소의 이동이 거품 수면으로 올라오는 듯한 모습을 보여서 거품 정렬이라 한다.

4-2 선택정렬(Selection Sort)

• Selection Sort는 Bubble Sort와 유사한 알고리즘으로 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘, 해당 자리를 선택하고 그 자리에 오는 값을 찾는 것.

4-3 삽입정렬(Insertion Sort)

• 손 안에있는 카드를 정리하는 것과 유사하다.
• Selection Sort와 유사하지만 조금 더 효율적이다.
• Insertion Sort는 2번째 원소부터 시작하여 그 앞의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘.

4-4 퀵정렬(Quick Sort)

• Quick Sort는 분할 정복 방법을 통해 주어진 배열을 정렬한다.
• Quick Sort는 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다. 또한 Merge Sort와 달리 Quick Sort는 배열을 비균등하게 분할 한다.
  (분할 정렬 -> 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 방법)

4-5 병합 정렬 (Merge Sort)

• 합병 정렬이라고도 부르며 분할 정복 방법을 통해 구현한다.
• 요소를 쪼갠 후, 다시 합병 시키면서 정렬해나가는 방식으로, 쪼개는 방식은 퀵정렬과 유사하다.

4-6 힙 정렬(Heap Sort)

• 완전 이진 트리를 기본으로 하는 힙(Heap) 자료구조를 기반으로 한 정렬 방식.
  (완전 이진트리 -> 삽입할 때 왼쪽부터 차례대로 추가하는 이진 트리)
• 힙 정렬은 불안정 정렬에 속한다.

4-7 기수 정렬 (Radix Sort)

• 데이터를 구성하는 기본 요소(Radix)를 이용하여 정렬을 진행하는 방식

4-8 계수 정렬 (Count Sort)

• 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 알고리즘.

5. 이진탐색

• 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘. (데이터가 무작위일 때는 사용할수 없다.)
• 탐색 범위를 절반씩 좁혀 나가며 데이터를 탐색하는 특징
• 이진 탐색은 위치를 나타내는 3가지 변수, 탐색하고자 하는 범위의 시작점, 끝점 그리고 중간점을 사용하고 찾으려는 데이터와 중간점위치에 있는 데이터를 반복적으로 비교해 원하는 데이터를 찾는 과정이다.

6. DFS & BFS

• 그래프 알고리즘으로 경로를 찾을때 상황에 맞추어 DFS(깊이 우선 탐색) , BFS(너비 우선 탐색)을 사용한다.

6-1 DFS(깊이 우선 탐색)

• Depth-First Search. 깊이 우선 알고리즘으로서 그래프를 탐색하는 알고리즘 이다. 최대한 멀리 있는 노드를 우선으로 탐색하는 방식으로 동작한다.

• 스택이나 재귀함수를 통해 구현한다.

  a. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
  b. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
  c. b과정을 더 이상 수행할 수 없을 때까지 반복한다.

6-2 BFS(너비 우선 탐색)

• 루트 노드 또는 임의의 노드에서 인접한 노트부터 먼저 탐색하는 방법.

• 큐를 통해 구현한다.

  a. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
  b. 큐에 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
  c. b과정을 더 이상 수행할 수 없을 때까지 반복한다.

7. 다이나믹 프로그래밍 (동적 계산법 = DP)

• 다이나믹 프로그래밍 DP의 경우 한 가지 문제에 대해서, 단 한 번만 풀도록 만들어주는 알고리즘이다. 똑같은 연산을 반복 하지 않도록 만듦으로서 실행 시간을 줄이기 위해 많이 이용되는 방법.

8. 다익스트라 알고리즘(Dijkstra)

• DP를 활용한 최단 경로 탐색 알고리즘.

• 다익스트라 알고리즘은 '단계마다 방문하지 않은 노드 중에서 가장 최단 거리가 짧은 노드를 선택'한 뒤에, 그 노드를 거쳐 가는 경우를 확인하여 최단 거리를 갱신하는 방법.

  a. 출발 노드를 설정한다.
  b. 최단 거리 테이블을 초기화한다.
  c. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
  d. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
  e. c d를 반복한다.