개발자로 살아남기

퀵정렬 (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..

버블 정렬 (Bubble Sort) 버블 정렬 (Bubble Sort) 가장 단순한 정렬 알고리즘 인접한 요소와 정렬 기준(오름차순, 내림차순)대로 교환 안정 정렬 (stable sort) : 정렬 후에도 같은 값들 끼리의 순서가 보장됨을 의미 제자리 정렬 (in-place sort) : 데이터에 필요한 공간을 제외하고 추가적인 공간이 필요없음을 의미 정렬한 데이터의 개수가 적을때는 나쁘지 않은 속도를 보임 버블 정렬 방법 (오름차순 기준) 첫 번째 사이클이 끝나면 맨 마지막 값이 정렬되고, 두 번째 사이클이 끝나면 뒤에서 두 번째의 값이 정렬된다. 이같은 과정을 계속 반복하면 최종적으로 정렬이 된다. 버블 정렬의 성능 시간복잡도 최악의 경우 : O(n^2) 최선의 경우 : O(n) 최악의 경우 : 모든..

우선순위 큐(Priority Queue)와 힙(Heap) 우선순위 큐 (Priority Queue) 기존의 큐와 다르게 들어간 순서와 상관없이 우선순위가 높은 데이터가 먼저 나옴 데이터간에 순서가 보장되지 않음 ex) 2, 3, 4, 1, 5 추가 후 iterator를 이용해 출력 시 1, 2, 4, 3, 5로 출력 구현방법 및 특징 - 배열 기반으로 구현 1) 인덱스로 데이터에 바로 접근할 수 있음 2) 데이터의 삽입/삭제에서 데이터들을 한칸씩 뒤로 밀거나 당기는 연산이 있어야 함 3) 삽입의 위치를 찾아내기 위해 최악의 경우 배열의 모든 데이터들과 우선순위를 비교해야 함 4) 저장 시 시간복잡도 O(n), 삭제 시 시간복잡도 O(1) - 연결리스트 기반으로 구현 1) 삽입의 위치를 찾기위해 최악의 경..

트리 (Tree) 트리 (Tree) 비선형 자료구조 계층적 관계를 표현하는 자료구조 (일상생활에서 사용하는 회사의 조직도 등) 여러 노드가 하나의 노드를 가리킬 수 없는 구조 (아래 그림은 트리가 아님) 용어 정리 노드 (node) - 트리의 구성요소로, 위 그림에서 A, B, C, D, E, F가 이에 해당됨 간선 (edge) - 노드와 노드를 연결하는 선 루트 노드 (root node) - 위 그림의 트리구조에서 최상위에 존재하는 A를 의미 단말노드 (terminal node) 또는 잎사귀 노드 (leaf node) - 다른 노드가 연결되어있지 않은 노드로서 위 그림에서 E, F, C, D가 이에 해당됨 내부노드 (internal node) 또는 비단말 노드 (nonterminal node) - 단말..