개발자로 살아남기

이진 탐색 트리 (Binary Search Tree, BST) 이진 탐색 트리 (Binary Search Tree, BST) 이진 트리의 일종 데이터를 트리에 저장하는 규칙에 따라야 함 노드에 저장된 키 값은 유일해야 함 왼쪽 자식 노드 키 > 부모 노드 키 > 오른쪽 노드 키 삽입할 데이터가 부모 노드보다 작으면 왼쪽, 크면 오른쪽에 삽입 왼쪽과 오른쪽의 서브 트리도 이진 탐색 트리 이진 탐색 트리 구현 방법 삽입 부모 노드와 삽입할 데이터를 비교해서 삽입할 데이터가 더 크면 오른쪽에 추가하고, 더 작으면 왼쪽에 추가한다. 단, 비교할 대상이 없을때까지 내려가야 한다. 탐색 삽입과 마찬가지로 찾고자하는 데이터가 부모 노드보다 작으면 왼쪽, 크다면 오른쪽으로 탐색한다. 단, 탐색 도중 데이터를 찾았거나 ..

보간 탐색 (Interpolation Search) 보간 탐색 (Interpolation Search) 균일하게 n개의 데이터가 분포되어 정렬된 배열이 있을 경우 이진 탐색보다 성능이 좋음 ex) 10, 12, 13, 15, 18, 22, 25, 26, 27, 30, ... => 성능 ↑ 10, 102, 192, 375, 462, 1777, ... => 성능 ↓ 이진 탐색은 탐색 대상의 값과 상관없이 무조건 절반씩 잘라서 비교하지만, 보간 탐색은 탐색 대상이 앞쪽에 있을 경우 앞쪽부터 탐색을 진행 선형 보간법을 이용해 탐색 위치를 결정함 보간 탐색 방법 탐색을 시작할 위치를 공식을 통해 알아낸다. 해당 위치에 탐색 대상이 있을 경우 해당 위치 값을 반환한다. 해당 위치의 값이 탐색 대상보다 작으면 탐색 ..

기수 정렬 (Radix Sort) 기수 정렬 (Radix Sort) 비교 연산이 없는 정렬 알고리즘 적용할 수 있는 범위가 제한적임 - 정수, 알파벳, 특수문자 등의 아스키로 표현할 수 있는 것들 - 소수는 불가능 기수 (Radix)를 이용한 정렬 - 2진수의 경우 : 0, 1 / 10진수의 경우 : 0 ~ 9 / 알파벳 소문자의 경우 : a ~ z (0 ~ 25) 기수만큼의 추가 저장 공간이 필요함 - 저장 공간을 버킷 (Bucket) 이라고 부름 Queue를 이용한 정렬 알고리즘 LSD (Least Significant Digit) 정렬 방법과 MSD (Most Significant Digit) 정렬 방법이 있음 - LSD : 덜 중요한 첫번째 자리수부터 정렬 (즉, 가장 작은 자리수) ex) 123..

퀵정렬 (Quick Sort) 퀵정렬 (Quick Sort) 분할정복 (divide and conquer) 알고리즘 중 하나 피벗(pivot)이라는 것을 이용해 정렬 피벗 : 데이터 리스트에서 하나를 고르는 것 불안정 정렬 (unstable sort) - 같은 데이터끼리의 순서가 보장되지 않음 ex) 5(A), 5(B), 3, 2, 1 => 1, 2, 3, 5(B), 5(A) nlog2(n) 알고리즘들 중 평균적으로 가장 빠름 제자리 정렬 (in-place sort) - 데이터 크기만큼의 저장공간을 제외하고 추가적인 공간이 필요하지 않음 퀵정렬 방법 데이터들 중 하나를 골라 피벗으로 설정 데이터 리스트의 앞과 뒤에서 탐색하며 피벗보다 작은 값들은 앞에 오고 피벗보다 큰 값들은 뒤로 가도록 분할 분할된 리..

힙 정렬 (Heap Sort) 힙 정렬 (Heap Sort) 최대힙 트리나 최소힙 트리를 구성해 정렬하는 방법 내림차순 정렬은 최대힙으로 구성 오름차순 정렬은 최소힙으로 구성 힙 관련 내용 참고 (https://banjjak1.tistory.com/45) 힙 정렬 방법 내림차순일 경우 데이터를 최대힙으로 구성하고 오름차순일 경우 최소힙으로 구성 최대힙의 경우 루트노드는 해당 트리에서 항상 최대값을 가지고 있으므로 힙 구성 후 삭제를 반복하면 다음 최대값이 루트노드가 되어 결국 내림차순 정렬이 됨 성능 시간복잡도 최악의 경우 : n log2(n) 최선의 경우 : n log2(n) : 데이터 저장 및 삭제의 시간복잡도 log2(n) : 정렬할 데이터가 n개인 경우 n개의 데이터를 저장 및 삭제해야 하므로 n..

합병(병합) 정렬 (Merge Sort) 합병(병합) 정렬 (Merge Sort) 안정 정렬 (stable sort) - 정렬 후에도 같은 값들끼리의 순서가 보장됨을 의미함 ex) 5, 4, 3(A), 2, 3(B), 1 1, 2, 3(A), 3(B), 4, 5 분할정복 (divide and conquer) 알고리즘 중 하나 정렬 시 데이터 크기만큼의 추가 공간이 필요하므로 제자리 정렬 (in-place sort)가 될 수 없음 합병 정렬 방법 분할 (divide) : 데이터 리스트에서 데이터가 하나씩 정렬될 때까지 리스트를 절반씩 나눈다. 정복 (conquer) : 나눈 데이터들끼리 재귀적으로 정렬을 진행한다. 결합 (combine) : 정렬된 데이터들을 하나로 합친다. 성능 시간복잡도 최악의 경우 :..

삽입 정렬 (Insertion Sort) 삽입 정렬 (Insertion Sort) 구현이 간단함 안정 정렬 (stable sort) - 정렬 후에도 같은 값들 끼리의 순서가 보장됨을 의미함 ex) 5, 3(A), 2, 4, 3(B), 1 => 1, 2, 3(A), 3(B), 4, 5 제자리 정렬 (in-place sort) - 데이터에 필요한 공간을 제외하고 추가적인 공간이 필요없음을 의미 선택 정렬, 버블 정렬보다 비교적 빠르지만 마찬가지로 배열이 클수록 효율이 떨어짐 선택 정렬과 비슷하지만 선택 정렬은 배열의 모든 값을 탐색해 최소값을 구한 후 정렬하는 방식이지만 삽입 정렬은 데이터의 앞쪽을 탐색하며 자신의 위치를 찾아 정렬함 삽입 정렬 방법 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 ..

선택 정렬 (Selection Sort) 선택 정렬 (Selection Sort) 제자리 정렬 (in-place sort) - 데이터에 필요한 공간을 제외하고 추가적인 공간이 필요없음을 의미 비안정 정렬 (unstable sort) - 정렬 후에 같은 값들의 순서가 변함 - 아래는 같은 값을 A, B로 구분하였음 ex) 3(A), 6, 2, 5, 4, 3(B), 1 1, 2, 3(B), 3(A), 4, 5, 6 정렬할 데이터의 개수가 적을때는 나쁘지 않은 속도를 보임 선택 정렬 방법 위 그림은 아래 방법을 그림으로 표현한 것 주어진 리스트 중에 최소값을 찾는다. 그 값을 맨 앞에 위치한 값과 교체한다. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. 성능 시간복잡도 최악의 경우 : O(n^2..