본문 바로가기

IT 공부91

최단 경로 알고리즘 (2. 벨만-포드 알고리즘) 👩‍💻 최단 경로 알고리즘이란?가중 그래프 상의 두 노드를 연결하는 가장 짧은 경로를 찾는 방법으로지도 경로 탐색, 네트워크 구축에 드는 비용을 최소화 하는데 사용한다. ✨ 최단 경로 알고리즘 종류다익스트라벨만-포드플로이드-워셜위의 세 가지 알고리즘은 각각 해결할 수 있는 상황이 조금씩 다르고, 알고리즘 복잡도도 다르다. ✏️ 벨만 - 포드 (Ballman-Ford)음수 간선이 포함되어 있어도 최단 경로를 구할 수 있음but, 음수 사이클이 있으면 정상 동작하지 않음매번 모든 간선을 확인하기 때문에 다익스트라에 비해 느림알고리즘 복잡도 : O(VE)따라서 음수간선이 포함되어 있는 경우 벨만-포드를 사용해야하지만, 아닌 경우는 다익스트라를 사용하는 것이 낫다. 💫 음수 간선이 포함된 가중그래프에서 .. 2024. 8. 6.

최단 경로 알고리즘 (1. 다익스트라) 👩‍💻 최단 경로 알고리즘이란?가중 그래프 상의 두 노드를 연결하는 가장 짧은 경로를 찾는 방법으로지도 경로 탐색, 네트워크 구축에 드는 비용을 최소화 하는데 사용한다. ✨ 최단 경로 알고리즘 종류다익스트라벨만-포드플로이드-워셜위의 세 가지 알고리즘은 각각 해결할 수 있는 상황이 조금씩 다르고, 알고리즘 복잡도도 다르다. ✏️ 다익스트라 (Dijkstra)출발점에서 목표점까지의 최단 경로를 구하는 알고리즘한 노드에서 다른 모든 노드로의 최단 경로를 구할 수 있음간선에 음의 가중치가 없어야 한다.그리디 + DP형태알고리즘 복잡도 : O(ElogV) 💫 다익스트라 알고리즘 Flow다음과 같이 노드와 간선 가중치 정보가 있을때,: A 노드에서 다른 노드들에 대한 최단 경로를 구하는 것은 아래와 같다... 2024. 8. 6.

백트래킹 알고리즘 (Backtracking) 👩‍💻 백트래킹 (Backtracking) 이란?✨ 모든 경우의 수를 탐색하며 최적해를 구하는 과정해서 유망하지 않은 쪽은 더 이상 구하지 않는 방법(full search = brute force = 완전 탐색)돌다리도 두드려보고 간다! 라는 느낌의 알고리즘 재귀함수를 많이 이용, DFS와 많이 섞여 나온다. ✏️ 백트래킹에서의 용어유망 (Promising)해가 될 가능성이 있는 경우 유망하다고 함가지 치기 (Pruning)해가 될 가능성이 없는 경우 해당 노드를 제외 하는 것백트래킹 (Backtracking)유망하지 않은 쪽으로 가지 않고 되돌아 오는 것 ✏️ 백트래킹 예시✨ N-Queen 문제: N x N 체스판에서 퀸 N개를 서로 공격할 수 없도록 배치하는 경우의 수(룰 : 퀸은 가로, 세.. 2024. 8. 4.

다이나믹 프로그래밍 ✨DP (Dynamic Programming) 👩‍💻 다이나믹 프로그래밍 (DP) 란?동적 계획법이란, 큰 문제를 부분 문제로 나눈 후 답을 찾아가는 과정에서, 계산된 결과를 기록하고 "재활용"하며 문제의 답을 구하는 방식 중간 계산 결과를 기록하기 위한 메모리가 필요but, 한 번 계산한 부분을 다시 계산하지 않아 속도가 빠르다. DP를 이용하여 알고리즘을 풀면 런타임에러를 해결할 수 있는 경우가 많다. ✏️ 다른 알고리즘과의 차이점분할 정복과의 차이분할 정복은 부분 문제가 중복되지 않는다.but, DP는 부분 문제가 중복되어서 재활용하여 사용한다.그리디 알고리즘과의 차이그리디 알고리즘은 순간의 최선을 구하는 방식이다. 즉, 근사치이다.but, DP는 모든 방법을 확인 후 최적해를 구하는 방식이다.* 그리디 알고리즘을 사용할 수 있는 문제.. 2024. 8. 2.

분할 정복 알고리즘 (Divide and Conquer) 👩‍💻 분할 정복 이란?큰 문제를 작은 부분 문제로 나누어 해결하는 방법이다.ex) 합병 정렬, 퀵 정렬, 이진 검색 등 분할 정복의 과정은 아래와 같다.문제를 하나 이상의 작은 부분들로 분할 한다.부분들을 각각 정복한다.부분들의 해답을 통합하여 원래 문제의 답을 구한다. ✏️ 분할 정복의 장 단점장점 : 문제를 나누어 처리하며 어려운 문제 해결 가능병렬 처리에 이점이 있음 (서로 영향을 끼치지 않고, 각각의 프로세싱을 돌릴 수 있는 구조)단점:메모리를 많이 사용(재귀 호출 구조) ✏️ 분할 정복 예시계속 반으로 잘라가며 모두 분할이 되면 조건에 맞는 값을 찾고 재귀적으로 최종 답을 찾아간다.public static int getMax(int[] arr, int left, int right){ in.. 2024. 8. 2.

그리디 알고리즘 (Greedy Algorithm) 👩‍💻 그리디 알고리즘 (Greedy Algorithm) 이란?매 순간 현재 기준으로 최선의 답을 선택해 나가는 기법빠르게 근사치를 계산할 수 있다.하지만 결과적으로 최적해가 아닐 수 있다. ✏️ 그리디 알고리즘 예시1) Activity Select ProblemN개의 활동과 각 활동의 시작/ 종료 시간이 주어졌을 때,한 사람이 최대한 많이 할 수 있는 활동의 수 구하기: 매 순간 선택할 수 있는 것 중에 최선을 선택! ✨but, 그리디 알고리즘은 항상 최적해를 주지 않는다. 아래의 사진이 그 예이다. 따라서 그리디 알고리즘의 적용 조건을 살펴볼 필요가 있다. ✏️ 그리디 알고리즘 적용 조건그리디 알고리즘은 빠르지만, 최적해를 보장하지는 못한다. 따라서 아래의 두 가지 조건에 해당하는 경우 적용.. 2024. 7. 20.

이전 1 ··· 5 6 7 8 9 10 11 ··· 16 다음

티스토리툴바