알고리즘/개념 (18) 썸네일형 리스트형 [복잡도] 시간 복잡도와 공간 복잡도 시간 복잡도 알고리즘을 위해 필요한 연산의 횟수 공간 복잡도 알고리즘을 위해 필요한 메모리의 양 [최단 경로 트리] 플로이드-워셜 알고리즘[Floyd-Warshall] 플로이드-워셜 알고리즘에 대해 알아보자. 플로이드-워셜 알고리즘은 '거쳐 가는 기점'를 기준으로 최단 거리를 구한다. 예를 들어보자. 아래와 같은 그래프가 있다. 이차원 배열의 형태로 출력하면 다음과 같다. 위 상태의 테이블이 의미하는 바는 '현재까지 계산된 최소 비용'이다. 이제 이 배열을 '거쳐 가는 기점'을 기준으로 반복적으로 갱신할 것이다. 그렇게 한다면 결국엔 모든 A에서 B의 최소 비용을 구해진다. 거쳐 가는 기점이 1인 경우 이렇게 거쳐 가는 기점이 1, 2, ... N인 경우를 모두 확인한다. 다익스트라 알고리즘 vs 플로이드-워셜 알고리즘 공통점 거쳐 가는 노드를 기준으로 알고리즘을 수행한다. 차이점 다익스트라 알고리즘은 한 정점에서 다른 모든 정점으로의 최단 경로를 구한다. 플로이드-워.. [이진탐색] 깊이 우선 탐색[DFS]과 백트래킹[Backtracking] 차이점 DFS와 Backtracking의 차이점을 알아보자. DFS 완전 탐색을 기본으로 하는 그래프 순회 기법으로 가능한 모든 경로를 탐색한다. 불필요한 경로를 사전에 차단하는 행동이 없다. 따라서 자원 소모가 심하다. Backtracking 경로를 찾아가는 도중에 해가 되지 않을 것 같은 경로가 갔다면 더 가지 않고 되돌아온다. 이는 가지치기라고 불린다. 불필요한 경로를 조기 차단하기 때문에 확인해야 하는 경로 수를 줄일 수 있다. 위와 같은 트리가 있다. ALT라는 단어를 찾아보자. DFS는 ALT라는 단어를 찾기 전까지 모든 노드를 방문한다. Backtracking은 ALT라는 단어를 찾는 과정에서 ALT라는 단어가 될 수 없을 것 같은 경로에 갔다면 더 가지 않고 돌아온다. [이진탐색] 하한선[Lower bound], 상한선[Upper bound] 개념 이진탐색의 상한선, 하한선은 이진탐색 알고리즘에서 약간 변경된 것이다. 중복된 자료가 있을 때 유용하게 사용된다. 1. 하한선[Lower bound] 데이터내에서 원하는 값보다 '같거나 큰 값' 중에 가장 앞에 있는 원소의 위치를 리턴한다. 위 이미지에서 lower_bound(3)은 index 3이다. 2. 상한선[Upper bound] 데이터내에서 원하는 값보다 '큰 값' 중에 가장 앞에 있는 원소의 위치를 리턴한다. 위 이미지에서 upper_bound(3)은 index 6이다. + 만약 모든 데이터가 원하는 값보다 작을 경우? 데이터 범위밖의 값을 리턴해야 한다. 그래서 일반적인 이분탐색과 달리 high를 len(array)-1이 아니라 len(array)로 한다. 구현 # 이진탐색 def b.. [정렬] 각 정렬의 장단점 및 시간 복잡도 장단점 시간 복잡도 출처 [정렬] 삽입 정렬 [Insertion Sort] 삽입 정렬에 대해 알아보자. 사진 출처 개념 정렬되지 않은 임의의 데이터를 이미 정렬된 부분의 적절한 위치에 삽입해 가며 정렬한다. 특징 버블/선택 정렬은 내부에서 정렬이 거듭될수록 탐색 범위가 줄어든다. 하지만 삽입 정렬은 오히려 정렬 범위가 늘어난다. 복잡도 버블, 선택 정렬과 마찬가지로 별도의 추가 공간을 사용하지 않는다. 주어진 배열 내에서 값들이 위치를 변경하기 때문에 공간 복잡도는 O(1)이다. 모든 데이터가 현재 데이터가 되어야 하므로 O(N)이 필요하다. 현재 데이터는 정렬된 데이터들과 비교하기 위해 O(N)이 필요하다. 따라서 시간복잡도는 O(N^2)이다. 구현 def insertion_sort(li): for end in range(1, len(li)): for i in range(en.. [정렬] 선택 정렬 [Selection Sort] 선택 정렬에 대해 알아보자. 사진 출처 개념 정렬되지 않은 부분에서 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환한다. 이를 모두 정렬될 때까지 반복한다. 복잡도 버블 정렬과 마찬가지로 별도의 추가 공간을 사용하지 않는다. 주어진 배열 내에서 값들이 위치를 변경하기 때문에 공간 복잡도는 O(1)이다. 가장 작은 원소를 앞에 계속 쌓아주기 위해 O(N)이 필요하고, 가장 작은 원소를 찾기 위해 O(N)이 필요하다. 따라서 시간복잡도는 O(N^2)이다. 구현 def selection_sort(li): l = len(li) for i in range(l - 1): min_idx = i for j in range(i + 1, l): if li[j] < li[min_idx]: min_idx = j li[i],.. [정렬] 버블 정렬 [Bubble Sort] 버블 정렬에 대해 알아보자. 사진 출처 개념 오름차순으로 정렬할 경우, 서로 이웃한 데이터들을 비교하여 더 큰 데이터를 뒤로 보낸다. 1회 정렬 후에는 가장 큰 데이터가 가장 뒤에 위치하게 된다. 이것을 반복해서 오름차순으로 정렬시킨다. 복잡도 별로의 추가 공간을 사용하지 않는다. 주어진 배열 내에서 값들이 위치를 변경하기 때문에 공간 복잡도는 O(1)이다. 가장 큰 데이터를 계속해서 가장 뒤에 위치시켜야 하므로 O(N), 서로 이웃한 데이터들의 비교를 위해서 O(N)이 필요하다. 따라서 시간복잡도는 O(N^2)이다. 구현 # 기본 def bubble_sort(li): for i in range(len(li) - 1, 0, -1): for j in range(i): if li[j] > li[j + 1]:.. [시간 복잡도] 빅오 표기법[Big O notation] 1. Big O notation 정의 알고리즘의 연산 횟수를 대략적으로 표기한 것이다. 상한으로 표기한다. 정리하자면 Big O 표기법은 1. 상수항(c)를 무시한다. 2. 영향력 없는 항을 무시한다. 예를 들어보자. f(n) = 2n^2 + 3n + 1 → O(n^2) f(n) = 3n^2 + 5nlogn → O(n^2) f(n) = n(1000) + 3^n → O(3^n) f(n) = 2n! + 5^n → O(n!) 2. Big O 표기법의 빠른 정도 O(1) -> O(logn) -> O(n) -> O(nlogn) -> O(n^2) -> O(n^k) -> O(k^n) -> O(n!) O(1)이 가장 빠르다. 3. 대표적인 시간 복잡도 1) O(1) - 배열의 n번째 원소에 접근 - Stack에 pus.. [정렬] in-place vs not in-place 1. in-place 원소의 개수에 비해 충분히 무시할 만한 저장 공간을 더 사용하는 정렬 알고리즘 2. not in-place 원소의 개수에 비례하여 저장 공간을 더 사용하는 정렬 알고리즘 이전 1 2 다음
