그리디 알고리즘
그리디(Greedy) 알고리즘은 최적해를 구하기 위해 각 단계에서 가장 좋은 선택을 하는 알고리즘이다.
이 알고리즘은 각 단계에서 현재 상황에서 가장 최선의 선택을 하고, 그 선택들의 조합이 전체적으로 최적의 해가 된다. 그리디 알고리즘은 매우 직관적이고 간결한 설계와 구현이 가능하며, 빠른 실행 속도를 가지는 특징이 있습니다.
예제
예를 들어, 동전 거스름돈 문제를 생각해 봅시다. 우리에게는 500원, 100원, 50원, 10원짜리 동전이 무한정 있다고 가정해보자. 이때, 우리가 지불해야 하는 금액을 가장 적은 동전의 개수로 거슬러주는 문제를 해결해야 한다.
def coin_change(n, coins):
result = []
coins.sort(reverse=True) # 동전을 큰 순서대로 정렬
for coin in coins:
count = n // coin # 해당 동전으로 거슬러 줄 수 있는 개수 계산
n -= count * coin # 거슬러 주고 남은 금액 업데이트
result.append((coin, count)) # 동전의 종류와 개수를 결과에 추가
return result
amount = 760
coin_types = [500, 100, 50, 10]
change = coin_change(amount, coin_types)
print(change)
- 거스름돈을 구성할 동전의 종류를 큰 순서대로 정렬한다. (500원, 100원, 50원, 10원)
- 동전 종류를 순서대로 탐색하면서, 해당 동전으로 거슬러 줄 수 있는 개수를 계산한다.
- 거슬러 주고 남은 금액을 업데이트한다.
- 동전의 종류와 개수를 결과에 추가한다.
- 모든 동전 종류에 대해 반복한 후, 결과를 반환한다.
구현
머리에 있는 알고리즘을 코드로 바꾸는 과정
DFS,BFS
DFS(Depth First Search, 깊이 우선 탐색)와 BFS(Breadth First Search, 너비 우선 탐색)는 그래프 탐색 알고리즘의 두 가지 기본적인 방법론이다. 이들은 그래프의 모든 노드를 방문하거나 특정한 조건을 만족하는 노드를 찾는 데 사용된다.
DFS
DFS는 트리나 그래프에서 한 노드로부터 시작하여 깊이 방향으로 탐색하고, 더 이상 갈 곳이 없으면 되돌아와 다음 분기점으로 이동하는 방식이다.
구현 방법 : 스택(Stack), 재귀 함수
주요 특징
- 한 분기의 끝까지 탐색하고 나서야 다른 분기로 이동한다.
- 보통 그래프의 깊이를 우선으로 탐색하기 때문에, 목표 노드를 빠르게 찾을 수 있다.
- 메모리 사용량이 크다는 단점이 있을 수 있다.
예제 코드
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start)
for neighbor in graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited)BFS
BFS는 트리나 그래프에서 한 노드로부터 시작하여 인접한 노드를 모두 탐색한 후, 같은 깊이의 노드들을 차례대로 탐색하는 방식이다.
구현 방법 : 큐(Queue)
주요 특징
- 한 노드의 모든 이웃을 먼저 탐색한다.
- 그래프의 너비를 우선으로 탐색하기 때문에 최단 경로를 찾는 용도로 사용할 수 있다.
- 더 많은 메모리를 필요로 하지만, 보통 DFS보다 빠른 속도로 결과를 얻을 수 있다.
예제코드
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
node = queue.popleft()
if node not in visited:
visited.add(node)
print(node)
for neighbor in graph[node]:
queue.append(neighbor)정렬
선택 정렬
선택 정렬은 간단한 정렬 알고리즘으로, 정렬되지 않은 부분에서 가장 작은 원소를 선택하여 정렬되지 않은 부분의 맨 앞과 교환하는 과정을 반복한다. 이 과정을 전체 리스트가 정렬될 때까지 반복한다.
주요 특징
- 간 복잡도는 O(n^2)로, 큰 리스트에는 비효율적이다.
- 추가적인 메모리를 필요로하지 않고, 제자리에서 정렬을 수행한다.
삽입 정렬
삽입 정렬은 또 다른 간단한 정렬 알고리즘으로, 최종적으로 정렬된 배열을 하나씩 구축한다. 두 번째 원소부터 시작하여 앞의 모든 원소와 비교하고 필요한 경우 교환하여 정렬 순서를 유지한다. 이 과정을 전체 리스트가 정렬될 때까지 반복한다.
주요 특징
- 시간 복잡도는 O(n^2)이지만, 작은 리스트나 거의 정렬된 리스트에 대해서는 선택 정렬보다 성능이 좋다.
- 제자리에서 정렬을 수행하는 알고리즘이다.
퀵정렬
퀵 정렬은 분할 정복 기법을 기반으로 하는 널리 사용되는 정렬 알고리즘이다. 피벗 원소를 선택하고, 배열을 피벗보다 작은 원소와 큰 원소의 두 하위 배열로 분할하며, 하위 배열에 대해 재귀적으로 정렬한다. 각 분할 후에 피벗은 최종적으로 정렬된 위치에 위치한다.
주요 특징
- 평균 시간 복잡도는 O(n log n)으로, 큰 리스트에 대해 효율적이다.
- 안정적인 정렬 알고리즘이 아니므로, 동일한 값의 상대적인 순서가 변경될 수 이다.
- 성능은 피벗의 선택에 크게 의존이다.
계수 정렬
계수 정렬은 정수 기반의 정렬 알고리즘으로, 입력 리스트에서 각 고유한 원소의 발생 횟수를 세는 방식으로 동작한다. 그런 다음 이 정보를 사용하여 각 원소를 최종 정렬된 배열에 올바른 위치에 배치한다.
주요 특징
- 시간 복잡도는 O(n+k)로, n은 원소의 개수이고 k는 입력의 범위이다.
- 원소의 범위가 작은 정수 배열을 정렬하는 데 효율적이다.
- 각 원소의 발생 횟수를 저장하기 위해 추가적인 메모리가 필요하다.
탐색
탐색은 주어진 데이터 구조에서 원하는 항목을 찾는 과정을 말한다. 주어진 조건 또는 목적에 따라 데이터를 탐색하여 원하는 결과를 얻을 수 있다. 대표적인 탐색 알고리즘으로는 선형 탐색, 이진 탐색, 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS) 등이 있다.
DP
큰 문제를 작은 하위 문제로 나누어 해결하는 알고리즘 디자인 기법이다. 작은 하위 문제들의 해결 결과를 저장하고 재활용함으로써 중복 계산을 피하고 효율적인 해결 방법을 제공한다. 다이나믹 프로그래밍은 중복 부분 문제와 최적 부분 구조의 특성을 가진 문제들에 적용된다.
