그리디

그리디 알고리즘은 현재 상황에서 가장 최적의 선택을 하는 알고리즘이다. 이 선택은 그 순간에는 최적일 수 있지만, 전체적으로 최적이라는 보장은 없다. 그리디 알고리즘의 유명한 예시로는 거스름돈 문제가 있다.
가장 적은 개수의 동전으로 거스름돈을 거스르는 방법을 찾기 위해, 그리디 알고리즘을 사용할 수 있다.

구현

간단하게 말하면 내 머릿 속에 있는 알고리즘을 구현하는 것이다.
어떤 문제를 풀든 간에 소스코드를 작성하는 과정은 필수이므로 구현 문제 유형은 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념이다.
프로그래밍 언어의 문법을 정확히 알고 있어야 하며 문제의 요구사항에 어긋나지 않는 답안 코드를 실수 없이 작성해야 한다.

그래서 구현은 사소한 조건들이 덕지덕지 붙어있을때 어려워지는 법이다.

DFS

깊이 우선 탐색(Depth First Search)은 그래프 탐색 알고리즘 중 하나이다. DFS는 특정한 경로를 탐색하다가 특정한 상황에 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘이다. DFS는 스택 자료구조를 이용하며, 재귀적으로도 구현할 수 있다.

BFS

BFS(Breadth First Search)는 그래프 탐색 알고리즘 중 하나이다. BFS는 특정한 경로를 탐색하다가, 특정한 상황에 다른 경로를 탐색하기 위해 큐(Queue)를 이용하는 알고리즘이다. 큐 자료구조를 이용하기 때문에, 구현할 때는 일반적으로 반복문과 큐 자료구조를 이용한다.

선택정렬

선택정렬(Selection Sort)은 정렬 알고리즘 중 하나이다. 선택정렬은 배열을 정렬할 때, 가장 작은 원소를 선택해 배열의 맨 앞에 위치시키고, 그 다음 작은 원소를 선택해 두번째 위치에 놓는 작업을 반복하면서 정렬을 수행한다. 선택정렬은 최악의 경우에도 시간복잡도가 O(n^2)이라는 단점이 있지만, 코드가 간단하고 구현이 쉬워서 자주 사용된다.

삽입정렬

삽입정렬(Insertion Sort)은 정렬 알고리즘 중 하나이다. 삽입정렬은 배열을 정렬할 때, 앞부분에 이미 정렬된 원소들 중에서, 삽입할 원소가 들어갈 위치를 찾은 후, 원소를 삽입하는 작업을 반복하면서 정렬을 수행한다. 시간복잡도는 선택정렬과 마찬가지로 O(n^2)이다.

퀵정렬

퀵정렬(Quick Sort)은 정렬 알고리즘 중 하나이다. 퀵정렬은 분할 정복(divide and conquer) 방법을 통해 리스트를 정렬한다. 리스트에서 첫 번째 원소를 피벗(pivot)으로 선택한 후, 피벗보다 작은 원소는 모두 피벗의 왼쪽으로, 큰 원소는 모두 피벗의 오른쪽으로 옮긴다. 그리고 나서, 피벗을 기준으로 왼쪽과 오른쪽 부분 리스트에서 각각 퀵정렬을 재귀적으로 적용한다. 이렇게 하면 전체 리스트가 정렬된다. 퀵정렬의 평균 시간복잡도는 O(nlogn)이며, 최악의 경우 O(n^2)이다.

(분할 정복)

(퀵정렬)

계수정렬

계수정렬(Counting Sort)은 정렬 알고리즘 중 하나이다. 계수정렬은 원소의 크기가 제한되어 있는 경우에 사용할 수 있으며, 비교 연산을 하지 않고 정렬할 수 있다. 계수정렬은 각 원소가 몇 개씩 있는지 세는 작업을 먼저 수행한 후, 그 결과를 바탕으로 정렬을 수행한다. 계수정렬의 시간복잡도는 O(n+k)이며, k는 정렬할 원소의 최대값이다. 계수정렬은 정렬할 원소의 범위가 제한되어 있을 때, 다른 정렬 알고리즘보다 빠른 속도를 보인다.

탐색

탐색(Search)은 데이터 집합에서 원하는 데이터를 찾는 과정이다. 대표적인 탐색 알고리즘으로는 이진 탐색(Binary Search)이 있다. 이진 탐색은 데이터가 오름차순으로 정렬된 배열에서 원하는 데이터를 찾는 알고리즘이다. 이진 탐색은 배열의 중간값과 찾고자 하는 데이터를 비교하고, 중간값이 더 작으면 왼쪽 부분 배열에서 탐색을 수행하고, 중간값이 더 크면 오른쪽 부분 배열에서 탐색을 수행한다. 이렇게 반복하면서 원하는 데이터를 찾는다. 이진 탐색의 시간복잡도는 O(log n)입니다. 이진 탐색 이외에도, 선형 탐색(Linear Search), 깊이 우선 탐색(Depth First Search), 너비 우선 탐색(Breadth First Search) 등 다양한 종류의 탐색 알고리즘이 있다.

DP

DP(Dynamic Programming)는 최적화 문제를 해결하는 알고리즘이다. DP는 큰 문제를 작은 문제로 나누어 푸는 분할 정복 기법과 유사하다. 하지만, DP는 중복되는 작은 문제들의 결과값을 저장해놓고, 이를 활용하여 큰 문제를 푸는 것이 특징이다. 이를 통해, 지수 시간 복잡도를 가지는 문제를 다항식 시간 복잡도로 해결할 수 있다. DP를 활용하는 가장 대표적인 문제로는 우리에게 익숙한 피보나치 수열이 있다.