다락방

B-Tree B트리는 이진트리에서 발전되어 모든 리프노드들이 같은 레벨을 가질 수 있도록 자동으로 밸런스를 맞추는 트리다. 정렬된 순서를 보장하고, 멀티 레벨 인덱싱을 통한 빠른 검색이 가능하다. B트리는 이진트리와 다르게 하나의 노드에 많은 수의 정보를 가지고 있을 수 있다. 최대 M개의 지식을 가질 수 있는 B트리를 M차 B트리라고하며 다음과 같은 특징을 가진다. 노드는 최대 M개부터 최소 M/2개 까지의 자식을 가질 수 있다. 노드에는 최대 M-1개 부터 최소 [M/2]-1개의 키가 포함 될 수 있다. 노드의 키가 x라면 자식의 수는 x+1개 이다. 최소차수는 자식수의 하한값을 의미, 최소차수가 t라면 M=2t-1를 만족한다. Key 검색과정 루트노드에서 시작하여 하향식으로 검색을 수행한다(검색하고..

위상정렬(Topological Sorting) 순서가 정해져 있는 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘. 사이클이 없는 방향, 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것. 진입차수와 진출차수 진입차수(Indegree) : 특정한 노드로 들어오는 간선의 개수 진출차수(Outdegree) : 특정한 노드에서 나가는 간선의 개수 동작과정 큐를 이용해 구현한다. 진입차수가 0 인 노드를 큐에 넣는다. 큐가 빌 때까지 다음의 과정을 반복한다 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다 새롭게 진입차수가 0이 된 노드를 큐에 삽입한다. 위상정렬을 수행할 수 있는 그래프는 사이클이 없는 방향 그래프(DAG)이여야 한다. 위상정렬의 특징 위상정렬은 사..

DFS(Depth-First Search) 깊이 우선 탐색 알고리즘 특정한 경로를 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문 한 후 다시 돌아가 다른 경로로 탐색하는 알고리즘 DFS는 스택 자료구조를 이용한다(보통 재귀함수를 이용해 DFS를 구현한다.) 동작과정 탐색 시작노드를 스택에 삽입 후 방문 처리를 한다. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접노드를 스택에 넣고 방문처리를 한다. 방문하지 않은 인접노드가 없으면 최상단 노드를 꺼낸다. 2를 수행할 수 없을때까지 반복한다. def DFS(graph,v,visit): visited[v] = True print(v) for i in graph[v]: if not visited[i]: DFS(graph,i,vi..

병합정렬(Merge Sort) 하나의 리스트를 두개의 균일한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법. 동작과정 Divide - 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다 Conquer - 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면(left < right) 순환호출을 이용해 다시 분할 정복 방법을 적용한다. Combine - 정렬된 부분 배열들을 하나의 배열에 병합한다. def merge_sort(arr): def sort(low, high): if high - low < 2: return mid= (low + high) // 2 sort(low, mid) sort(mid, high) me..

분할정복(Divide and Conquer) 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방식 대표적인 예 퀵정렬 합병정렬 이진탐색 선택문제 고속 푸리에 변환 분할정복의 설계 Divide - 원래 문제가 분할하여 비슷한 유형의 더 작은 하위 문제로 분할 가능할때까지 나눈다. Conquer - 각 하위 문제를 재귀적으로 해결한다. 하위 문제의 규모가 나눌 수 없는 단위가 되면 탈출 조건을 설정하고 해결한다. Combine - Conquer한 문제들을 통합하여 원래 문제의 답을 얻어 해결한다. Divide를 제대로 나누면 Conquer 과정은 자동으로 쉬워진다. 그래서 Divide를 잘 설계하는 것이 중요하다. 분할정복 알고리즘은 재귀 알고리즘이 많이 사용되는데, 이 부분에서 분할정복..

이진탐색(BinarySearch) 이진탐색(이분 탐색) 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 이진탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 변수 3개(start,end,mid)를 사용하여 탐색한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진탐색의 과정이다. def binary_search(target,start,end): if start >= end: return 0 mid = (start + end) // 2 if target == mid: return 1 elif target > mid: start = mid + 1 else: end = mid -1 retu..

완전탐색(ExhaustiveSearch) 간단히 가능한 모든 경우의 수를 다 체크해서 정답을 찾는 방법. 무식하게 한다는 의미로 ‘BruteFroce’ 라고도 부르며, 직관적이여서 이해하기 쉽고 문제의 정확한 결과값을 얻어낼 수 있는 가장 확실하며 기초적인 방법이다. 완전탐색 기법을 활용하는 방법 해결하고자 하는 문제의 가능한 경우의 수를 대략적으로 계산한다. 가능한 모든 방법을 다 고려한다. BruteForce기법 - 반복/조건문을 활용해 모두 테스트 하는 방법 순열(Permutation) - n개의 원소 중 r개의 원소를 중복 허용 없이 나열하는 방법 재귀호출 비트마스크 - 2진수 표현 기법을 활용하는 방법 BFS,DFS를 활용하는 방법 실제 값을 구할 수 있는지 적용한다.

검색(Search) 검색과 키 키(Key) - 데이터의 일부 검색의 종류 배열검색 선형검색 - 무작위로 늘어놓은 데이터 집합에서 검색수행 이진검색 - 일정한 규칙으로 늘어놓은 데이터 집합에서 아주 빠른 검색 수행 해시법 - 추가 삭제가 자주 일어나는 데이터 집합에서 아주 빠른 검색 수행 체인법 - 같은 해시값 데이터를 연결리스트로 연결 오픈 주소법 - 데이터를 위한 해시값이 충돌할 때 재해시 하는 방법 연결리스트 검색 이진 검색 트리 검색 선형 검색(LinearSearch) 직선 모양(선형)으로 늘어선 배열에서 검색하는 경우에 원하는 키값을 가진 원소를 찾을때까지 맨앞부터 스캔하여 순서대로 검색하는 알고리즘 선형 검색의 종료조건 검색할 값을 찾지 못하고 배열의 맨 끝을 지나간 경우 - 검색 실패 검색할 ..