반응형 Algorithm/알고리즘2 [알고리즘] : 동적 계획 알고리즘 및 플로이드 워샬 알고리즘 기초 동적 계획 알고리즘 ( Dynamic Programming (DP) ) 입력 크기가 작은 부분 문제들을 해결하고 그 해들을 이용해 보다 큰 크기의 부분 문제들을 해결하여 최종적으로 원래 주어진 입력의 문제를 해결하는 알고리즘입니다. 분할 정복은 중복이 되지 않습니다. 동적 계획 알고리즘은 중복을 허용합니다. ex] 피보나치 = 0 1 1 2 3 5 8 13 21 - - - - 플로이드 - 워샬 알고리즘 간단하게 플로이드 알고리즘이라고 부릅니다. 플로이드 알고리즘의 시간 복잡도는 O(n^3)으로 다익스트라 알고리즘을 n번 사용할 때의 시간 복잡도와 같습니다. 2021. 11. 8. [알고리즘] : 알고리즘 기초 설명 그리디(greedy) 알고리즘 - 최적화 문제를 해결하는 알고리즘입니다. - 욕심쟁이, 탐욕 알고리즘으로도 불립니다. - 데이터 간의 관계를 고려하지 않고 수행 과정에서 욕심내어 최소값 또는 최대값을 가진 데이터를 선택합니다. # 근시안적인 선택이라고도 합니다. 크러스컬(kruskal) 알고리즘 - 가중치가 가장 작은 간선이 사이클을 만들지 않을 때, 욕심내어 그 간선을 추가 시킵니다. 프림(prim) 알고리즘 - 임의의 점 하나를 선택한 후 (n-1)개의 간선을 하나씩 추가시켜 트리를 생성합니다. - 간선이 누적 된다는 표현을 많이 씁니다. (누적형이지만 최소 가중치 값은 올라가고 있습니다.) 다익스트라(dijkstra) 알고리즘 - 방향성이 있습니다. - 출발 지점이 있습니다. - 출발 지점부터 목적.. 2021. 11. 1. 이전 1 다음 반응형
