[알고리즘] 벨만포드

벨만포드 (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

[알고리즘] 최단 경로 찾기

최단 경로를 찾는 데 자주 사용되는 알고리즘은 여러 가지가 있다. 1. One-To-One 한 지점에서 다른 특정 지점까지의 최단경로 구하기2. One-To-All 한 지점에서 다른 모든 지점까지의 최단경로 구하기3. All-To-All 모든 지점에서 모든 지점까지의 최단경로 구하기 문제의 조건마다 사용되는 알고리즘이 다르기때문에 적절히 선택해서 사용해야 한다.그러려면 어떤 알고리즘이 있는지 알아야 할 것! 1. 다익스트라(Dijkstra) 알고리즘 목적 단일 시작점에서 다른 모든 노드까지의 최단 경로를 구하는 것원하는 목적지가 나오면 종료할 수도 있음 그래프 유형 가중치가 있는 방향성 또는 무방향성 그래프 - 음수 가중치 허용 X 시간복잡도 O((V+E)⋅log⁡V) 구현방식1. 시작 노드의 거리를 0..

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

1. 알고리즘이란

알고리즘의 정의 컴퓨터가 계산이나 기타 문제 해결 작업을 수행할 때 따라야 하는 프로세스 또는 일련의 규칙문제 풀이에 필요한 계산 절차 또는 처리 과정의 순서를 뜻함 알고리즘 문제는 답을 찾는 것도 중요하지만 효율적인 방식으로 푸는 것도 중요하다.문제의 효율을 따질때는 보통 시간복잡도와 공간복잡도를 고려한다. 공간복잡도 공간 복잡도란 프로그램 실행과 완료에 얼마나 많은 공간(메모리)가 필요한지를 나타낸다.알고리즘을 실행시키기 위해 필요한 공간(space)는 두 가지로 나눌 수 있다.알고리즘과 무관한 공간, 즉 고정 공간코드가 저장되는 공간, 알고리즘 실행을 위해 시스템이 필요로 하는 공간 등알고리즘과 밀접한 공간, 즉 가변 공간문제를 해결하기 위해 알고리즘이 필요로 하는 공간.변수를 저장하는 공간, 순환..

• format_list_bulleted 알고리즘공부/알고리즘
• · 2024. 11. 24.
• textsms