오늘은 알고리즘 중에서도 그리디, 구현, DFS, BFS, 선택정렬, 삽입정렬, 퀵정렬, 계수정렬, 탐색, DP에 대해서 정리해볼까 합니다.
첫번째는 그리디 알고리즘입니다.
그리디 알고리즘은 탐욕 알고리즘 또는 욕심쟁이 알고리즘이라고도 불리는 알고리즘으로 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법입니다.
즉, 최적의 선택을 하지는 않는 알고리즘입니다.
지금 당장 좋은 것만을 고르다보니 현재의 선택이 나중에 어떤 영향을 미칠지는 모른다는 것입니다.
그렇기에 최선이 될 수도 있지만 아닐 수도 있는 알고리즘입니다.
두번째는 구현입니다.
구현은 알고리즘을 소스코드를 바꾸는 과정을 말합니다.
풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 것이 문제입니다.
세번째는 DFS(깊이우선탐색) 알고리즘입니다.
DFS는 Depth-First Search의 약자로 이름에서부터 알 수 있다시피 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법입니다.
DFS의 특징으로는 자기 자신을 호출하는 순환 알고리즘의 형태를 가지고 있다는 것이며 전위 순회(Pre-Order Traversals)를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이기도 합니다.
또한, 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다는 것이 큰 차이점입니다.만약 어떤 노드에 방문했었는지 여부를 검사하지 않을 경우 무한 루프에 걸릴 수도 있기에 조심해야 합니다.
네번째는 BFS(너비우선탐색) 알고리즘입니다.BFS는 Breadth-First Search의 약자로 이름에서부터 알 수 있다시피 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법입니다.
BFS의 특징으로는 재귀적으로 동작하지 않는다는 것과 선입선출(FIFO) 원칙으로 탐색하고 DFS와 똑같이 어떤 노드에 방문했었는지 여부를 검사하지 않을 경우 무한 루프에 걸릴 수도 있기에 어떤 노드를 방문했었는지 여부를 반드시 검사해야 합니다.
다섯번째는 선택정렬 알고리즘입니다.
선택 정렬은 정렬되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 가장 앞의 데이터와 교체해나가는 방식입니다.
선택정렬 알고리즘이 작동하는 방식은 이러합니다.
1. 주어진 리스트 중 최소값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다. (패스(pass))
3.맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
여섯번째는 삽입정렬 알고리즘입니다.
삽입정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘입니다.
삽입정렬 알고리즘이 작동하는 방식은 이러합니다.
1. 두번째 자료부터 시작하여 그 앞의 자료들과 비교한다.
2. 삽입할 위치를 찾으면 그 이후의 자료들을 뒤로 옮기고 자료를 삽입한다.
3. 나머지 배열/리스트를 위와 같은 방법으로 정렬한다.
일곱번째는 퀵정렬 알고리즘입니다.
합병정렬과 비슷하게 분할정복(Divide and Conquer) 알고리즘입니다.
평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법으로 다음과 같은 과정을 거칩니다.
1. 리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 pivot(피벗) 이라고 한다.
2. pivot을 기준으로 pivot보다 작은 요소들은 모두 pivot의 왼쪽으로 옮기고 pivot보다 큰 요소들은 모두 pivot의 오른쪽으로 옮긴다.
3. pivot을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.
3-1) 분할된 왼쪽 리스트와 오른쪽 리스트도 다시 pivot을 정하고 pivot을 기준으로 2개의 부분리스트로 나눈다.
3-2) 재귀를 사용하여 부분 리스트들이 더이상 분할이 불가능 할 때까지 반복한다.
여덞번째는 계수정렬 알고리즘입니다.
계수정렬은 주어진 배열의 값 범위가 작은 경우 빠른 속도를 갖는 정렬 알고리즘입니다.
최댓값과 입력 배열의 원소 값 개수를 누적합으로 구성한 배열로 정렬을 수행합니다.
카운팅(계수) 정렬 수행 과정은 다음의 단계로 이루어집니다.
1. 입력 배열의 최댓값, Counting Array 생성
2. 원소의 누적합을 구하기 위한 Counting Array 생성을 위해 입력 배열의 최댓값이 필요하다. 이후 최댓값 + 1 크기의 Counting Array를 생성하여 입력 배열의 값을 기준으로 조회된 좌표에 입력 배열의 각 원소 개수를 count 한다.
3. 입력 배열 원소 개수의 누적합
4. 1번 과정에서 Counting Array 생성 및 원소 Count를 마쳤다면 이전 좌표의 원소 개수를 더해나가 누적합 배열로 만들어준다.
5. 입력 배열과 누적합 배열을 이용한 정렬 수행
6. 입력 배열의 각 원소에 대해 Counting Array에 조회하여 어느 좌표에 들어가야 하는지 체크한 뒤 조회된 원소의 개수를 1 감소시켜 앞의 좌표로 입력받을 수 있게 한다.
아홉번째는 탐색 알고리즘입니다.
탐색 알고리즘은 여러 개의 자료 중 원하는 자료를 찾는 작업을 말합니다.
순차탐색, 이진탐색 등 수많은 종류를 가지고 있는 알고리즘이기도 합니다.
열번째는 DP(동적계획법) 알고리즘입니다.
DP는 Dynamic Programming의 약자로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용합니다.
감사합니다.