게으름뱅이의 앞구르기

해시(Hash)란? 데이터를 최대한 빠른 속도로 관리하도록 도와주는 자료구조 해시를 사용하면 메모리 공간이 많이 소모되지만 매우 빠른 속도로 데이터를 처리할 수 있음 빠르게 데이터에 접근할 수 있어 데이터베이스 등에 활용 특정한 값을 찾고자 할 때 키(Key)로 접근할 수 있음 일반적으로 해시 함수는 모듈로 연산 등의 수학적연산으로 이루어져 있어 O(1)만에 값에 접근할 수 있음 해싱 알고리즘은 나눗셈법이 가장 많이 활용됨 입력값을 테이블의 크기로 나눈 나머지를 키로 이용하는 방식 테이블 크기는 소수(Prime Number)로 설정하는 것이 효율성이 높음 해시의 충돌 해시 함수의 입력값으로는 어떤 값이나 들어갈 수 있지만, 해시 함수를 거쳐 생성되는 키의 경우의 수는 한정적이라 키 중복이 발생할 수 있음..

이진 탐색 트리 이진 탐색 트리의 조건 각 노드에 값이 있다. 값들은 전순서가 있다. 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다. 노드의 오른쪽 서브트리에는 그 노드의 값과 같거나 큰 값들을 지닌 노드들로 이루어져 있다. 좌우 하위 트리는 각각이 다시 이진 탐색 트리여야 한다 ※ 성능을 최대치로 끌어내기 위해서는 완전 이진트리에 가까워질 수 있도록 설계해야함 이진 탐색 트리 삽입 삽입을 하기 전, 검색을 수행한다. 트리를 검색한 후 키와 일치하는 노드가 없으면 마지막 노드에서 키와 노드의 크기를 비교하여서 왼쪽이나 오른쪽에 새로운 노드를 삽입한다. 이진 탐색 트리 삭제 삭제하려는 노드의 자식 수에 따라 자식노드가 없는 노드(리프 노드) 삭제 : 해당 노드를 단순히..

깊이 우선 탐색(Depth First Search) 맹목적 탐색방법의 하나로 탐색을 함에 있어서 보다 깊은 것을 우선적으로 하여 탐색하는 알고리즘 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식 탐색시작 노드를 스택에 삽입하고 방문처리함 스택의 최상단 노드에게 방문하지 않은 인접노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리함 / 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄 2를 더이상 수행할 수 없을 때까지 반복 스택 자료구조에 기초함 빠르게 모든 경우의 수를 탐색하고자 할 때 쉽게 사용..

그래프(Graph) 사물을 정점(Vertex)와 간선(Edge)로 나타내기 위한 도구 이론적으로 그래프는 리스트와 행렬 구조 중의 하나로 구별 가능하지만 실제 적용에 있어서 최적의 자료구조는 이 두 구조의 조합된 형태를 띤 형태임 인접 행렬(Adjacency Matrix) : 2차원 배열을 사용 인접 리스트(Adjacency List) : 리트스를 사용 무방향 그래프 : 모든 간선이 방향성을 가지지 않는 그래프 비가중치 그래프 : 모든 간선에 가중치가 없는 그래프. 연결되어 있는 상황을 인접 행렬로 출력할 수 있음 방향 그래프 : 모든 간선이 방향을 가짐 가중치 그래프 : 모든 간선에 가중치가 있음 그래프 개념과 구현 인접 행렬은 모든 정점들의 연결 여부를 저장하여 O(V2)의 공간을 요구하므로 공간 효..

순차 탐색(Sequential search) 특정한 원소를 찾기 위해 원소를 순차적으로 하나씩 탐색 O(N)의 시간복잡도를 가짐 검색할 리스트의 길이가 길면 비효율적 검색 방법 중 가장 단순하여 구현이 쉽고 정렬되지 않은 리스트에서도 사용할 수 있다는 장점이 있음 이진탐색(Binary search) 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘. 탐색 범위를 절반씩 좁혀가며 데이터를 탐색 O(logN)의 시간 복잡도를 가짐 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 됨 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있음 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다. 참고..