본문 바로가기

항해99 chap02

 (26)
Dynamic Programming 동적 계획법 (Dynamic Programming) 동적 계획법(Dynamic Programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. 여러 개의 하위 문제를 풀고 그 결과를 기록하고 이용해 문제를 해결하는 알고리즘입니다! 즉, 우리가 재귀함수를 풀어나갈 때 많이 했던 함수의 수식화를 시키면 됩니다. F(string) = F(string[1:n-2]) 라고 수식을 정의했던 것 처럼, 문제를 쪼개서 정의할 수 있으면 동적 계획법을 쓸 수 있습니다! 이처럼 문제를 반복해서 해결해 나가는 모습이 재귀 알고리즘과 닮아있습니다! 그러나 다른 점은, 그..
최단경로 최단경로 최단경로( ex. A에서 B로 가는 최단 경로) 그래프로 표현 각 지점은 노드, 도로는 간선. 다익스트라, 플로이드-워셜 다익스트라 알고리즘 INF = int(1e9) def dijkstra_naive(graph, start): def get_smallest_node(): min_value = INF idx = 0 for i in range(1, N): if dist[i] < min_value and not visited[i]: min_value = dist[i] idx = i return idx N = len(graph) visited = [False] * N dist = [INF] * N visited[start] = True dist[start] = 0 for adj, d in graph[..
이진탐색 이진탐색 배열이 정렬되어있을 경우, 절반씩 줄여나가면서 탐색하는 기법 def binary_search(nums,target): def bs(start,end): if start>end: return -1 mid = (start+end)//2 if nums[mid]target: return bs(start,mid-1) else: return mid return bs(0,len(nums)-1)
병합 정렬 MergeSort 쪼개서 합치면서 정렬 [1, 2, 3, 5] # 정렬된 배열 A [4, 6, 7, 8] # 정렬된 배열 B [] # 두 집합을 합칠 빈 배열 C ↓ 1단계 : [1, 2, 3, 5] ↓ [4, 6, 7, 8] 1과 4를 비교합니다! 1 4 이므로 4을 C ..
퀵 정렬 #퀵소트 (Quick Sort) 분할정복을 통해 주어진 배열을 정렬 하는 알고리즘입니다. 배열에서 기준(pivot)을 잡고, 기준보다 값이 작은 집합과 큰 집합으로 나눕니다(Divide). 그리고 그 사이에 기준을 위치시킵니다. 작은 집합과 큰 집합을 대상으로 재귀호출하여 정렬한 뒤(Conquer) 결과를 합치면 정렬된 배열을 얻을 수 있습니다. def quicksort(lst, start, end): def partition(part, ps, pe): pivot = part[pe] i = ps - 1 for j in range(ps, pe): if part[j] = end: return None print(lst) p = partition(lst, start, end) quicksort(lst, sta..
버블,선택,삽입 정렬 버블 정렬(BubbleSort) O(n^2) 가장 큰걸 뒤로 보내자 def bubblesort(lst): iters = len(lst)-1 for iter in range(iters): wall=iters-iter for cur in range(wall): if lst[cur]>lst[cur+1]: lst[cur] , lst[cur + 1] = lst[cur+1],lst[cur] print(lst) lst = [4, 6, 2, 9, 1] bubblesort(lst) [4, 6, 2, 9, 1] # 정렬되지 않은 배열 1단계 : [4, 6, 2, 9, 1] 4와 6을 비교합니다! 4 2 이므로 둘을 변경합니다..
힙 힙은 부모가 자식보다 큰 완전 이진트리. 힙은 좌,우 자식의 위치가 대소관계를 반영하지않음 (BST와는 다름) 계산편의를 위해 인덱스는 1부터사용 Parent : x / left : 2x / right : 2x+1 힙의 규칙 힙은 항상 큰 값이 상위 레벨 작은값이 하위레벨에 있어야함 최대힙 - 삽입 시간 복잡도 결국 원소를 맨 밑에 넣어서 꼭대기까지 올림 -> 완전 이진트리의 최대 높이는 O(log(N))즉 반복하는 최대횟수도 O(log(N))이다 맥스 힙의 원소추가는 O(log(N))의 시간복잡도를 가짐 최대 힙 - 추출 알고리즘 최댓값, 루트 노드를 삭제 하는것 스택과 같이 맨 위에 있는 원소만 제거할 수 있고, 다른 위치의 노드를 삭제할수는 없다. 방법 루트 노드와 맨 끝에 있는 원소를 교체 맨 뒤..
이진 트리 트리는 바로 비선형 구조입니다! 비선형 구조는 선형구조와는 다르게 데이터가 계층적 혹은 망으로 구성되어있습니다. 선형구조와 비선형구조의 차이점은 형태뿐만 아니라 용도에서도 차이점이 많습니다! 선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고, 비선형구조는 표현에 초점이 맞춰져 있습니다. 높이가 h 일 때 최대 노드의 개수는 2^(h+1) - 1개 입니다. 그러면 이 때 최대 노드의 개수가 N이라면 N = 2^(h+1) - 1 → h = log_2(N+1)-1 라고 할 수 있습니다! 즉! 완전 이진 트리 노드의 개수가 N일 때 최대 높이가 log_2(N+1) - 1이므로 이진 트리의 높이는 최대로 해봤자 O(log(N))이 구나! 라고 말씀하시면 됩니다. class TreeNode: def __i..

티스토리툴바