행복한 연어의 이야기

검색 알고리즘은 검색 로직뿐만 아니라 삽입 삭제 로직도 같이 구현했습니다. 1. AVL 트리 앞서 설명해드린 이진 트리 탐색 (Binary Tree Search)에는 단점이 있습니다. 이진 트리 탐색은 O(log²n) 의 시간 복잡도를 가지지만 균형이 잡히지 않은 트리일수록 O(n)에 가까워 진다는 것 입니다. 트리의 균형을 잡기위한 여러가지 특성의 트리(균형잡힌 트리)가 있으며 그중에 오늘 소개 드릴 트리는 AVL 입니다. (AVL 은 이 트리를 개발한 사람의 이름 약자입니다.) 2. 구현 방법 검색, 삽입, 삭제는 앞서 구현한 이진 트리 탐색 (Binary Tree Search)과 동일합니다! 다만 삽입과 삭제시 트리의 균형을 검사하여 리밸런싱을 해주는 작업이 추가되었을 뿐입니다. 우선 트리가 균형을..

검색 알고리즘은 검색 로직뿐만 아니라 삽입 삭제 로직도 같이 구현했습니다. 1. 이진 트리 탐색 (이진 탐색 트리) (Binary Tree Search) 이진 트리를 사용하는 검색 방법 입니다. 이진 트리 자체가 매우 효율적인 검색 방법입니다. 자료형이 많이 늘어도 검색 횟수가 크게 늘지 않습니다. 2. 구현 방법 키값은 고유하며, 자식 < 부모 < 오른쪽 이라는 공식이 성립해야합니다. 검색은 찾는 값이 같으면 반환, 노드보다 작으면 왼쪽, 크면 오른쪽으로 이동하며 키값을 찾습니다. 삽입은 검색과 마찬가지로 찾는 값이 같으면 실패(키값은 고유하다.), 노드보다 작으면 왼쪽, 크면 오른쪽으로 이동하며 삽입 위치를 찾습니다. 삭제는 조금 복잡합니다. 이진트리 삭제의 경우 크게 3가지 경우로 나뉩니다. 자식이..

검색 알고리즘은 검색 로직뿐만 아니라 삽입 삭제 로직도 같이 구현했습니다. 1. 이분 탐색, 이진 탐색 (Binary Search) 평균적으로 log²N 의 검색길이를 갖는 빠른 검색방법입니다. 다만 이분검색은 데이터들이 정렬되어 있어야 합니다. 또한 검색은 쉬운데 삽입 삭제가 조금 까다롭다고 생각하시면 됩니다. 즉 삽입 삭제가 빈번이 일어나는 데이터보다 검색만을 위한 데이터를 위해 사용하는게 좋습니다. 2. 구현 방법 이미 정렬된 데이터 집합에 중간값과 내 키의 값을 비교하여 왼쪽 혹은 오른쪽 구간을 선택, 그 구간의 중간값과 키값을 비교 하는 재귀적인 과정을 통해 검색이 완료됩니다. 검색은 중간값과 키값이 일치할떄까지 구간을 반으로 나누는 작업을 진행하며 키값을 찾습니다. 삽입은 어느위치에 넣어야 정..

검색 알고리즘은 검색 로직뿐만 아니라 삽입 삭제 로직도 같이 구현했습니다. 1. 선형 탐색, 순차 탐색(Sequential Search) 주어진 자료파일에서 처음부터 검색하여 필요한 데이터를 비교하며 찾는 가장 단순한 검색 방법입니다. 평균적으로 N/2 번의 비교를 하는 효율이 낮은 검색 방법이지만 구현하기 간단하고 정렬되어 있지 않은 대상으로도 가능하기 때문에 널리 사용하는 방법입니다. 2. 구현 방법 방법은 간단합니다. 첫번째 인덱스부터 끝까지 돌면서 값이 있는지 확인하면 끝이거든요! 검색은 배열을 반복문을 돌리면 끝입니다. 삽입은 순차탐색 특성상 정렬될 필요 없으니 마지막 위치에 넣었습니다. 삭제는 배열로 구현시 바로 빈자리를 채우는 방법과 표시만 해두고 나중에 처리하는(게으른 삭제) 방법중에 바로..

안녕하세요. 오늘은 퀵 정렬을 알아보도록 하겠습니다. 1. 퀵 정렬(Quick)이란? 병합 정렬과 비슷하게 배열을 분할 하는 방식으로 진행됩니다. 병합 정렬은 분할하여 재조립 하면서 정렬한다는 느낌이면 퀵정렬은 피벗의 위치를 찾고 분할하고 분할된 값들 중에서 다시 피벗 찾고 하면서 진행 됩니다. 둘다 분할 정복 개념이 들어가 있습니다. 또한 퀵 정렬은 이름 그대로 빠른 정렬 중 하나이며 다른 O(N log N) 정렬 알고리즘과 비교했을때 가장 빠릅니다. 2. 퀵 정렬의 특징 안정성 X 평균 O(N log N) 최악 O(N²)의 시간복잡도 정렬된 경우, 역순일 경우 느리고 난수일때 가장 빠릅니다. 정렬 안정성 과 알고리즘 시간 복잡도 빅오(Big - Oh) 안녕하세요. 정렬과 탐색 알고리즘 관련 글을 작성..

안녕하세요. 오늘은 병합 정렬을 구현해보도록 하겠습니다. 1. 병합 정렬(Merge Sort)이란? 병합정렬은 배열을 나누고 나눈 부분들을 다시 하나로 만들때 순서대로 정렬하는 방법을 사용합니다. 아래 구현한 병합 정렬의 순서는 다음과 같습니다. 1) 1개의 크기를 가질때까지 배열을 반으로 나눕니다. 2) 두개의 부분을 정렬하여 새로운 임시배열에 넣습니다. 3) 임시 배열에 저장된 결과를 원래 배열에 복사합니다. 2), 3) 을 반복 하여 정렬을 완료 합니다. 2. 병합 정렬의 특징 안정성 O O(N log N) 의 시간복잡도 정렬 안정성 과 알고리즘 시간 복잡도 빅오(Big - Oh) 안녕하세요. 정렬과 탐색 알고리즘 관련 글을 작성 중 간단하게 안정성과 빅오 표기법에 대한 글을 작성하고 첨부해 놓으면..