algorithm/알고리즘5 벨만포드 알고리즘 (파이썬 구현) 벨만포드 알고리즘이란? 한 노드에서 다른 노드까지의 최단 거리를 구하는 알고리즘이다. 다익스트라 알고리즘과의 차이점 출발노드가 1번, 도착노드가 3번노드라고 하자. 다익스트라 알고리즘은 그리디 알고리즘 기반이므로 1번 노드에서 가중치가 10, 20 중 더 짧은 10을 선택해 3번으로 갈 것이고 3번 노드는 도착 노드이므로 최단거리 10을 반환할 것이다. 하지만 벨만 포드 알고리즘은 출발노드에서 갈수 있는 모든 경로를 확인하기 때문에 1->2->3 의 경로를 확인해 최단거리 5를 반환한다. 즉 벨만포드 알고리즘은 가중치에 음수가 포함되어 있는 경우 사용한다. 동작순서 1. 출발 노드를 설정한다. 2. 최단거리 테이블을 무한대 값으로 초기화한다. 3. 최단거리 테이블에서 출발노드의 값을 0으로 초기화 한다... 2024. 4. 14. 다익스트라 알고리즘 (파이썬 구현) 1. 다익스트라 알고리즘이란? 그래프에서 한 노드에서 다른 노드까지의 최단 경로를 구하는 알고리즘 중 하나이다. 출발노드에서 갈 수 있는 모든 노드들의 최단 경로를 구할 수 있다. 다익스트라 알고리즘은 그리디 기반으로 작동하므로 가중치가 음수일 경우 최단거리를 구할 수 없다. 2. 동작 순서 1) 출발 노드를 설정한다. 2) 출발 노드에서 각 노드로 갈 수 있는 최단 거리를 저장하는 테이블을 만든다. 3) 출발노드부터 시작하여 각 노드로 갈 수 있는 거리가 현재 최단거리 테이블에 저장되어 있는 값보다 작으면 최단거리 테이블을 업데이트 하고 현재 노드에서 갈 수 있는 노드들을 확인한다. 4) 3번 과정을 반복하여 갈 수 있는 모든 노드들을 확인한다. 3. 다익스트라 함수 로직 구현 1) 파라미터로 받은 출.. 2024. 4. 14. 완전탐색 알고리즘 완전탐색이란? 가능한 모든 경우의 수를 구한 후 문제에 나와있는 조건과 일치하는 값을 찾는 방법이다. 모든 가능성을 고려하기 때문에 항상 최적의 해를 찾을 수 있다. 완전탐색 알고리즘은 반복문이 여러번 중첩되어 사용되는 경우가 많으므로 입력값의 범위, 또는 비교해야할 범위가 작은 경우에 유용하다. 완전탐색 알고리즘 종류 2024. 4. 11. 크루스칼 알고리즘 (Kruskal Algorithm) 크루스칼 알고리즘을 이해하기 위한 필수 개념 1. 신장 트리 : 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 없는 부분 그래프를 의미한다. 2. 최소 신장 트리 : 신장 트리 중에서 최소한의 비용으로 구현된 신장트리를 의미한다. 크루스칼 알고리즘은 최소 신장 트리 알고리즘이며 그리디 알고리즘으로 구현된다 ! 크루스칼 알고리즘의 동작 과정 1. 간선 데이터를 비용에 따라 오름차순 정렬한다. 2. 모든 간선을 한번씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다. 사이클 발생하지 않는 경우 => 최소신장트리에 추가한다. 사이클 발생하는 경우 => 최소신장 트리에 추가시키지 않는다. 1. 간선 데이터를 비용에 따라 오름차순 정렬 간선 ( 3 , 5 ) ( 4 , 5 ) ( 1 , 3 ) (.. 2024. 3. 4. DP (dynamic programming : 동적 계획법) 핵심 포인트 재귀 또는 귀납법을 이용할 때 이미 구했던 값은 또 구하지 않기 (구한 값은 저장할 것) 동적계획법 문제인지 확인하는 법 1. 배열을 이용하여 문제를 풀 때 배열의 i번째 인덱스의 값이 중복해서 사용될 경우 2. 특정 알고리즘을 이용해서 푸는 방식이 아닌 피보나치 수열과 같은 방식으로 풀릴 때 ( dp[i]=dp[i-1]+dp[i-2] 공식으로 풀린다면 for문에 i=1이면 dp[0]을 사용하고 i=2일때도 dp[0]을 사용한다. ) -> 구한 값들은 dp배열을 따로 만들어서 i번째 인덱스에 저장 후 반복 사용 2024. 1. 29. 이전 1 다음
