728x90 Algorithm5 최단 경로 알고리즘 - 플로이드 워셜 알고리즘 드디어 최단 경로 알고리즘! DFS/BFS의 벽이 너무 높았지만 내가 해냄 플로이드 워셜 알고리즘 플로이드 워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단경로를 구할때 사용하는 알고리즘이다. 단계마다 거쳐가는 노드를 기준으로 알고리즘을 수행한다. 이 때 점화식을 사용하게 되므로 일종의 다이나믹 프로그래밍이다. 노드의 개수가 n개 일때 n번의 단계를 수행하며 단계마다 n^2의 연산을 통해 모든 경로를 고려하게된다. 총 시간복잡도는 n^3이다. 시간복잡도가 큰 만큼 풀 수 있는 유형이 정해져있다. 풀이 순서 1. 2차원의 리스트를 무한의 값으로 채워 넣는다. 2. 자기자신에서 자기자신으로 가는 경우는 비용을 0으로 처리 3. 각 간선의 정보를 입력받아 초기화 한다. 4. 플로이드 워셜 알고리즘 수행.. 2023. 1. 24. 동적계획법(Dynamic Programming, DP) - Python 동적 계획법 (動的計劃法, dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. (위키피디아) 입력 크기가 작은 문제를 해결한 다음 보다 크기가 큰 부분 문를 해결한 다음 그것을 결합하며 최종적으로 전체 문제를 해결하는 상향식 접근 알 고리즘이다. Memoization기법을 사용 : 이전에 사용한 값을 저장하여 다시 계산하지않는다. 이렇게 각 계산값을 저장하게 되면 중복 계산 시간이 줄어든다. 부분 문제는 중복되어 재활용된다 대표적인 예로 피보나치 수열 재귀로 푸는 것도 물론 가능하지만 중복되는 연산을 줄일 수 있는 점에서 아주 효과적임 def fibo(n): cache = [0 for index in range(n + 1)] cache[0] = 0.. 2022. 12. 6. 링크드리스트(Linked list) - Python 링크드 리스트란 연결 리스트로 연결된 공간에 데이터를 나열하는 데이터 구조 - 배열과 달리 떨어진 공간에 존재하는 데이터를 포인터로 연결해서 관리 - 파이썬은 리스트 타입이 링크드 리스트의 기능을 모두 지원! 그림처럼 여기저기 흩어져 있어도 포인터로 서로서로 연결이 가능하다 장점 1. 미리 데이터 공간을 할당하지 않아도된다. 단점 1. 연결을 위한 별도의 데이터 공간(포인터)가 필요하므로 저장공간의 효율이 높진 않다. 2. 연결 정보를 찾는 시간이 필요하므로 접근 속도가 느리다 3. 중간 데이터를 삭제하는 경우 앞 뒤 데이터 연결을 재구성해야하는 부가적인 작업이 필요하다. class Node: def __init__(self, data): self.data = data self.next = None # .. 2022. 11. 9. 정렬 알고리즘(선택정렬, 삽입정렬, 퀵정렬, 계수정렬) - python 선택정렬 가장 작은 것을 선택해서 맨 앞의 데이터와 바꾸는 것을 반복 시간복잡도 Ο(n²)으로 상당히 느린편이다 array = [...] for i in range(len(array)): min_index = i; #가장 작은 원소의 인덱스 for j in range(i+1, len(array)): if array[min_index] > array[j]: min_index = j array[i], array[min_index] = array[min_index], array[i] 삽입정렬 특정한 데이터를 적정한 위치에 삽입 데이터가 거의 정렬되어 있을 때 훨씬 효율적 첫번째 데이터는 정렬되어 있다고 판단하고 두번째 데이터 부터 시작한다 정렬이 이루어진 원소는 항상 오름차순을 유지한다. 시간복잡도는 Ο(n².. 2022. 10. 1. 탐색 알고리즘 - DFS / BFS Tip 탐색문제는 그래프 형태로 표현 후 풀이하면 좋다. DFS : Depth-First Search, 깊이 우선 탐색 인접 행렬 방식 : 2차원 배열에 각 노드가 연결된 형태를 기록 연결되지 않은 노드는 무한의 비용이라고 작성 장점 : 모든 관계를 저장하므로 메모리가 불필요하게 낭비된다. 단점 : 인접 리스트 방식에 비해 속도가 빠르다 인접 리스트 방식 : 모든 노드에 연결된 노드에 대한 정보를 차례로 연결하여 저장 장점 : 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용한다. 단점 : 연결된 데이터를 하나씩 확인해야하므로 속도가 느리다. def dfs(graph, v, visited): visited[v] = True #현재 노드 방문 처리 print(v, end=' ') for i in g.. 2022. 9. 26. 이전 1 다음 728x90 반응형
