DP (동적 프로그래밍, Dynamic Programming)

1. 소개동적 프로그래밍이란? 동적 프로그래밍(Dynamic Programming, DP)은 복잡한 문제를 작은 부분 문제로 나누어 해결하고, 그 결과를 저장하여 중복 계산를 방지하는 최적화 기법입니다. 언제 사용할까?DP는 다음과 같은 경우에 사용된다. 부분 문제가 반복적으로 등장하는 경우 최적 부분 구조 (Optimal Substructure): 부분 문제의 최적해를 이용해 전체 문제를 해결할 수 있을 때예를 들어, 피보나치 수열을 재귀로 구현하면 동일한 값이 여러 번 중복 계산된다.DP를 사용하면 이를 방지할 수 있다. 분할 정복과의 차이점 동적 프로그래밍분할 정복부분 문제 중복 여부OX대표 예제피보나치 수열, 배낭 문제, LCS병합 정렬, 퀵 정렬해결 방식저장하여 재사용독립적인 작은 문제로 나눠 ..

• format_list_bulleted 알고리즘공부/알고리즘
• · 2025. 3. 1.
• textsms

[알고리즘] A* 알고리즘

A* (A star algorithm) 알고리즘이란??그래프의 한 정점에서 다른 한 정점까지의 최단거리를 각각 구하는 알고리즘목적지까지의 거리를 계산하는 휴리스틱 추정값을 이용해 다익스트라를 개선한 알고리즘휴리스틱 함수의 성능에 따라 알고리즘 성능이 달라진다. 시간복잡도O(b^d) (완전 탐색) ~ O(E log V) (최적화 시)b는 분기 계수 (한 노드에서 이동할 수 있는 평균 갈래 수)d는 최단 경로의 깊이(시작점에서 목표까지의 단계 수)E는 그래프의 간선 수, V는 노드 수 공간복잡도O(b^d) (최악) ~ O(V) (일반적인 경우)   다익스트라와의 차이점 다익스트라출발점에서 모든 노드에 대한 최단거리를 탐색함단순히 현재 지나온 거리가 가장 짧은 노드를 선택해 탐색A*출발점에서 도착점까지의 최단..

• format_list_bulleted 알고리즘공부/알고리즘
• · 2025. 2. 3.
• textsms

[알고리즘] 벨만포드

벨만포드 (Bellman-Ford) 알고리즘이란??그래프의 한 정점에서 다른 모든 정점까지의 최단거리를 각각 구하는 알고리즘음의 가중치를 갖는 간선이 있을 때 사용하는 알고리즘이다. 시간복잡도매번 모든 간선을 확인하기 때문에 O(V*E) 정점 * 간선  공간복잡도정점의 개수만큼 배열이 필요하므로 O(V)   다익스트라와의 차이점 다익스트라매번 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드를 선택음의 가중치가 있으면 사용 X시간 복잡도가 빠르다벨만포드매번 모든 간선을 전부 확인하면서 모든 노드간의 최단 거리를 구함음의 가중치가 있어도 사용 가능 & 음수 사이클 여부 확인 가능시간 복잡도가 느리다. 즉, 간선에 음수가중치가 있으면 벨만포드, 없으면 다익스트라를 사용!  구현 방식 정점의 개수만큼의 길..

• format_list_bulleted 알고리즘공부/알고리즘
• · 2025. 1. 24.
• textsms

[알고리즘] 플로이드 워셜

플로이드워셜 (Floyd-Warshall) 알고리즘이란??그래프의 모든 정점에서 다른 모든 정점까지의 최단거리를 각각 구하는 알고리즘 한 점에서 이웃 노드를 탐색하며 최단 거리를 구하는 다익스트라와 다르게 거쳐가는 중간 노드를 기준으로 최단 거리를 구한다.음수가중치가 허용 되지만, 음수 사이클이 있으면 안된다.  우측의 경우는 2 -> 3 -> 2 사이클을 돌 때마다, 최단경로가 1씩 단축이 되어버리므로 이러한 음수 사이클이 있는 그래프에서는플로이드 워셜을 사용할 수 없다. 또한 플로이드 워셜을 동적계획법을 이용하므로, 동적계획법의 개념을 잘 이해하는 것이 좋다. 시간복잡도 플로이드 워셜은 3중 반복문을 사용하기때문에 O(n^3)의 시간복잡도를 가진다. n은 정점의 개수 공간복잡도 path table을 ..

• format_list_bulleted 알고리즘공부/알고리즘
• · 2025. 1. 24.
• textsms

[알고리즘] 다익스트라

다익스트라 알고리즘이란??그래프의 한 정점에서 다른 모든 정점까지의 최단거리를 각각 구하는 알고리즘 그래프 방향의 유무와 구현 방법에 구애받지 않고 적은 비용으로 가장 빠르게 해답에 도달하는 최단경로 알고리즘이다.하지만 음수 가중치가 존재한다면 사용할 수 없다. 정상 동작하는 경우도 있는데 음수 사이클이 있으면 잘못 나올 수도 있다.그래서 웬만하면 음수 가중치가 없을 때만 사용하는 것이 좋을 것 같다. 음수 사이클이 있는지 판별도 안된다음수가중치가 있다면 벨만포드를 사용하는 것을 추천한다. 다익스트라 알고리즘을 확장시킨 알고리즘인 A* 알고리즘도 존재한다. 구현 방식 1. 출발점으로부터 최단거리를 저장할 배열 - dist - 을 만들고, 출발 노드에는 0, 다른 노드들에게는 INF값을 채워 넣는다. 코드..

• format_list_bulleted 알고리즘공부/알고리즘
• · 2025. 1. 24.
• textsms

[알고리즘] 정렬

정렬이란?? 일련의 데이터들을 정해진 규칙을 따라 순서대로 나열하는 것정해진 규칙이란건 오름차순, 내림차순, 알파벳순서, 문자열의 길이 등 다양한 것이 될 수 있다. 정렬의 종류 1. 선택 정렬 (Selection Sort)제자리 정렬 알고리즘의 하나입력 배열 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법시간 복잡도 O(n^2) 공간 복잡도 O(1) 정렬 과정첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째로 놓고, 두 번째 자료를 세 번째 자료부터 마지막 자료까지와 차례대로 비교하여 그 중 가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬을 수행한다. 예제배열에 9, 6, 7, 3, 5가 저장되어 있다고 하고 오름차순으로 정렬할 때 예..

• format_list_bulleted 알고리즘공부/알고리즘
• · 2025. 1. 22.
• textsms