Code/ALGORITHM7 억지기법과 완전 탐색 억지 기법 ( brute-foce ) 란 ? 매우 광범위한 문제에 적용 가능한 알고리즘 설계 기법 중 하나 입력의 크기가 작은 경우 충분히 빠를 수 있고, 점근적으로 더 효율적인 알고리즘 보다 실제 빠른 경우도 존재 효율적인 알고리즘 설계와 분석을 위해 이론적 기반이 됨 정렬, 탐색, 기하학적 문제, 완전 탐색, 그래프 탐색 등에 사용 가능 [1] brute-force를 사용한 선택 정렬 : 입력 리스트에서 가장 작은 항목을 매번 루프마다 찾고, 이를 꺼내 정렬된 리스트에 순서대로 삽입한다. ▶ 이를 개선 시키면, 새로운 리스트에 저장하는 것이 아니라 정렬되지 않은 최근 포인트에 접근하여 교환하는 것도 가능 ( 제자리 정렬 ) 선택 정렬 알고리즘 def selection_sort(A): n = len(A.. 2022. 10. 2. 최단 경로 알고리즘 (2) 개선된 다익스트라 알고리즘 저번장의 알고리즘은 시간 복잡도가 O(V^2)으로 노드의 개수가 10,000개를 넘어가는 순간 해결이 어려워졌었다. 하지만 다음의 구현 방법을 이용하면 최악의 경우에도 시간 복잡도 O(E logV)를 보장하여 해결할 수 있다. 여기서 V는 노드 개수 , E는 간선 개수이다. 저번 장의 알고리즘에서 최단 거리가 짧으면서 탐색하지 않은 노드를 찾기 위해서 선형적으로 테이블을 탐색해야 했다 => N 이 때 힙 자료구조를 사용하여 최단거리에 대한 정보를 빠르게 찾도록 하자 힙을 사용하면 선형시간이 아닌 로그시간이 걸리므로 N이 1,000,000 이라면 로그시간에서 약 20 정도로. 속도가 크게 빨라진다. - 파이썬에서 우선순위 큐를 지원하기 위해 PriorityQueue 와 heapq.. 2021. 9. 6. 최단 경로 알고리즘 최단 경로 알고리즘에 대표적인 알고리즘으로는 다익스트라, 플로이드 워셜, 벨만 포드 알고리즘이 있다. 다익스트라 최단 경로 알고리즘 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 이 때 조건은 음의 간선이 없는 경우에 정상적으로 동작한다는 점이다. 현실 세계에서의 길에는 음의 간선의 표현될 일이 없으므로 실제 GPS 소프트웨어의 기본 알고리즘으로 채택되곤 한다. 다익스트라 알고리즘을 그리디 알고리즘(탐욕법)으로도 분류된다. '매번 가장 적은 비용의 노드를 선택'하는 임의의 과정을 반복하기 때문이다. 알고리즘은 최단 경로를 구하는 과정에서 각 노드에 대한 현재까지의 최단거리를 단계마다 게속 갱신해 나간다. 즉 매번 현재 처리하고.. 2021. 9. 1. 다이나믹 프로그래밍 컴퓨터의 연산에는 크게 두 가지의 제약사항이 존재한다. 메모리 공간과 연산 속도의 한계이다. 이러한 상황에서 메모리 공간을 약간 더 할애 한다면 비약적으로 연산속도를 증가시킬 수 있는 방법이 있다. 이 대표적인 방법이 다이나믹 프로그래밍 , 동적 게획법이다. 다이나믹 프로그래밍은 2가지 방식 텀 다운과 보텀 업으로 나눌 수 있는데 텀 다운 같은경우에는 맨 위의 큰 문제에서 아래 문제로 쪼개 가며 해결해가는 하향식 해결 방법이고 보텀업의 경우에는 작은 문제들을 먼저 해결해가면서 큰 문제로 합쳐서 해결하는 상향식 해결방법이다. 다이나믹 프로그래밍을 설명하는데에는 피보나치 문제가 주로 이용된다 피보나치 수열에 대해서 설명은 생략하고 재귀적으로 풀어낸 피보나치 소스코드를 살펴보면 아래와 같다. def fibo(.. 2021. 8. 12. 이전 1 2 다음 반응형
