그리디 알고리즘
그리디 알고리즘은 각 단계에서 가장 최적의 선택을 하는 방식으로 문제를 해결합니다. 각 단계에서의 최적해가 전체적인 최적해를 보장하지 않을 수도 있지만, 그리디 알고리즘은 간단하고 효율적인 구현이 가능한 장점이 있습니다.
구현
구현은 알고리즘을 실제 프로그램으로 구현하는 과정을 말합니다. 주어진 문제의 요구사항을 코드로 작성하고, 실행 가능한 프로그램을 만드는 것이 목표입니다. 구현 능력은 알고리즘을 이해하고 효과적으로 활용하는 데 매우 중요합니다.
DFS(Depth-First Search)
DFS는 그래프 탐색 알고리즘 중 하나로, 한 경로를 최대한 깊게 탐색한 후 다음 경로로 넘어가는 방식입니다. 스택(Stack) 자료구조를 활용하여 구현할 수 있습니다. DFS는 재귀적인 방법으로도 구현할 수 있으며, 그래프의 모든 정점을 방문하고자 할 때 유용합니다.
BFS(Breadth-First Search)
BFS는 그래프 탐색 알고리즘으로, 시작 정점에서부터 인접한 정점들을 모두 탐색한 후에 다음 단계의 인접 정점들을 탐색합니다. 큐(Queue) 자료구조를 사용하여 구현할 수 있습니다. BFS는 최단 경로 문제나 최단 거리를 구하는 문제에 유용합니다.
선택정렬
선택정렬은 배열에서 가장 작은 값을 선택하여 정렬된 부분과 교환하는 정렬 알고리즘입니다. 비교 횟수는 많지만 교환 횟수가 적어 알고리즘 구현이 간단합니다. 하지만 시간 복잡도가 O(n^2)으로 비효율적이므로 큰 크기의 배열에는 적합하지 않을 수 있습니다.
삽입정렬
삽입정렬은 배열을 정렬된 부분과 비교하여 올바른 위치에 삽입하는 정렬 알고리즘입니다. 선택정렬과 마찬가지로 구현이 간단하지만, 시간 복잡도가 O(n^2)이기 때문에 큰 입력에는 효율적이지 않을 수 있습니다. 정렬된 상태에서의 성능이 좋다는 특징이 있습니다.
퀵정렬
퀵정렬은 분할 정복(Divide and Conquer) 방법을 사용하여 배열을 정렬하는 알고리즘입니다. 배열에서 하나의 요소를 선택하고, 이를 기준으로 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 분할하여 재귀적으로 정렬합니다. 평균적으로 좋은 성능을 보이며, 시간 복잡도는 평균적으로 O(nlogn)입니다.
계수정렬
계수정렬은 정수나 정수로 표현할 수 있는 자료에 대해서만 사용 가능한 정렬 알고리즘입니다. 각 요소의 출현 횟수를 세어 정렬하는 방식으로, 입력 크기에 비례하는 크기의 배열을 사용합니다. 계수정렬은 입력값의 범위가 제한되어 있을 때 매우 효율적입니다.
탐색
탐색은 주어진 자료 구조에서 원하는 값을 찾는 과정을 말합니다. 대표적인 탐색 알고리즘으로는 이진 탐색(Binary Search)이 있습니다. 탐색은 데이터베이스, 검색 엔진 등 다양한 분야에서 활용됩니다.
DP(Dynamic Programming)
DP는 큰 문제를 작은 문제로 나누어 해결하는 방법을 의미합니다. 작은 문제들의 결과를 저장하고 재활용하여 중복 계산을 피하며, 효율적으로 문제를 해결합니다. DP는 최적 부분 구조와 중복되는 부분 문제를 가지는 문제에 적용할 수 있습니다.
