juju의 컴공일지

📌트리(Tree) root 와 서브 트리로 구성된 계층형 hierarchical 자료 구조 📌이진 트리 (Binary Tree) 각 노드는 최대 2개의 자식노드 [ 용어 정리 ] ✔️단말 노드 자식 노드가 없는 차수가 0인 노드 ✔️레벨 루트는 레벨 1이며 단말 노드 방향으로 1씩 증가 ✔️부모-자식 부모와 자식 노트의 레벨 차이 1 ✔️형제 형제 노트는(sibling) 부모가 동일한 자식 노드들 ✔️조상 노드 (Ancestor node) 특정 노드에서 루트까지 경로에 존재하는 모든 노드 ✔️자손 노드 (Descendant node) 특적 노드의 서브 트리에 존재하는 모든 노드 ✔️내부 노드(Internal node) 자식이 최소한 1개 이상인 노드 ✔️외부 노드(External node) 자식이 없는 ..

앞에서 이진 탐색, 보간 탐색은 탐색 키가 발견될 때까지 저장된 값들과 반복적인 비교 수행 이런 경우 n이 높아질 수록 시간 소요가 많다 📌해싱 탐색(Hashing Search) 탐색 키 간의 비교 없이 탐색 키에 직접 산술 연산 적용 탐색 키 정보가 저장되어 있는 테이블 상의 위치 계산 => 주소를 통해 접근 ex)Dictionary 👉 탐색하려는 명칭 x에 해시 함수를 적용하면 이 명칭의 정보가 저장된 해시 테이블의 버켓 주소가 반환 된다 📌해싱 탐색 시간 : O(1) => 상수만큼 걸린다 📌해시테이블(Hash table) 명칭 identifier 들이 저장된 고정된 크기의 표 👉 행 row = 버켓 bucket 👉 열 column = 슬롯 slot 행이 b개 열이 s개 있다면 b*s개의 명칭을 적재..

📌보간 탐색 (interpolation search) 항목들이 정렬되어 있을 때 키 값의 차이와 위치의 차이가 비례한다는 가정을 바탕으로 정렬된 항목 리스트에 대한 것? => 이진 탐색과 유사 단, median값을 이용하는 것이 아닌 탐색 Key와 탐색 경계 값의 차이를 고려하여 키의 위치 결정 ✔️가정 양쪽 경계 값들의 차이 : 키 값과 왼쪽 경계 값의 차이 = 양쪽 범위의 거리 : 탐색 위치와 왼쪽 경계의 거리 차이 즉, 👉 ( list[right] - list[left] ) : ( key - list[left] ) = ( right - left ) : ( 탐색위치 - left ) 계산하면 👉 pos = left + [( right - left ) * ( key - list[left] )] / [( ..

📌이진탐색 (Binary Search) 탐색시간을 줄이기 위하여 항목들을 정렬한 후에 탐색을 적용 ✔️알고리즘 1. 오름차순으로 정렬된 항목들에 대해 가운데 median을 찾아 key와 비교한다 2. key=median이면 중간값의 인덱스를 반환하고 탐색을 종료한다 3. 탐색 키가 중간 값보다 작으면 중간 값의 왼쪽만 탐색하면 된다, 반대면 오른쪽만 4. 변경된 탐색 대상 항목들에 대해 탐색 반복한다 📌시간복잡도: O(log_2n) public class BinarySearch { public static void main(String[] args) { int n = 9; int pos; int key = 23; int[] num = {0, 1, 5, 9, 13, 17, 23, 32, 45}; pos =..

📌탐색 다수의 레코드 집합에서 특정 키 값과 일치하는 레코드 찾는 작업 ✔️레코드 객체(object)의 속성(property)에 해당하는 필드(field)의 집합 ✔️리스트 레코드의 집합 ✔️디스크 리스트가 파일형식으로 저장되는 곳 📌순차탐색 (Sequential Search) 목표 키를 찾을 때까지 순차적으로 비교 반복 ❗️최상 : 첫번째 비교에서 목표 레코드 찾는 경우 , 비교 횟수 1번 💢최악 : 가장 마지막 비교에서 목표 레코드 찾는 경우 , 비교 횟수 n번 시간 복잡도 : O(n) import java.util.Scanner; public class Sequential { public static void main(String[] args) { Scanner sc = new Scanner(Sys..

📌합병 정렬 (Merge Sort) ✔️알고리즘 레코드 리스트를 반으로 나누어 2개의 서브리스트로 분할 또 분할.. 재귀적으로 분할.. 더 이상 분할 불가능 할 때까지 분할이 완료된 이후 이웃하는 두개의 파티션을 병합하여 정렬하는 방식 📌시간복잡도 : (nlog_2n) ✔️분할하는데 걸리는 시간 O(n) ✔️병합에 걸리는 시간 ( n + log_2n ) -두 서브 리스트 원소의 개수 s,t개라고 할 때 두 서브 리스트 병합에 걸리는 시간 n=s+t이므로 O(n) -레벨의 수 (log_2n) 전체 레벨의 분할과 병합에 걸리는 시간 (nlog_2n) 노트에다 막 쓴거라 깔끔하진 않으나.. 첨부 해본다 #include void mergesort(int num[], int left, int right); voi..

📌힙 정렬 (Heap Sort) 최대 힙의 루트 = 원소의 최댓값 📌시간복잡도 : O(nlog_2n) 한번 Heapify가 수행되는 시간 (log_2n) 전체 트리 구조에 대해서 (nlog_2n) ✔️힙이란 최댓값 및 최솟값을 찾아내는 완전이진트리를 기본으로 한 자료구조 ✔️알고리즘 1. n개의 레코드를 최대 힙으로 구성 2. 루트를 힙의 마지막 원소와 교환 3. 정렬된 마지막 원소를 제외하고 나머지 원소에 대해 최대 힙으로 재구성 후 반복 4. 정렬된 원소 제외 최대 힙에 원소 1개 남으면 종료 ❓최대힙 : 부모 노드가 자식 노드보다 커야 한다 최대 힙을 만들어 주는 알고리즘을 이용하는 것이 힙 정렬이다 👉힙 생성 알고리즘 수행 (Heapify Algorithm) : 특정한 노드의 두 자식 중에서 더 ..

📌퀵 정렬 (Quick Sort) pivot x를 임의로 선택하여 정렬 대상들을 x보다 큰 값들, 작은 값들로 나눠서 정렬한다 ✔️알고리즘 1. pivot을 가장 왼쪽 수로 선택하고 pivot을 기준으로 작은 그룹과 큰 그룹으로 나눈다. 2. 분할이 완료되면 pivot은 큰 그룹과 작은 그룹 사이로 이동한다. 3. 재귀적으로 1,2를 진행한다. 📌시간 복잡도 : O(nlog_2n) 분할했는데 한쪽으로만 몰리는 모든게 큰 값 혹은 작은 값으로 몰릴 때는 최악 : O(n^2) 👆p는 pivot을 나타내고 i는 왼쪽에서 부터, j는 오른쪽에서부터 #include void quick_sort(int num[], int left, int right); void print_array(int num[], int n)..

📌삽입 정렬 (Insertion Sort) 이미 정렬되어 있는 서브 리스트에 새로운 원소를 추가하는 정렬방법 📌시간 복잡도 이미 정렬이 완료되어 있는 경우 => 최상 O(n) 원소들이 역순으로 되어 있는 경우 => 최악 O(n^2) ✔️알고리즘 1. 리스트의 인덱스 0번 위치의 항목 한개는 이미 정렬이 완료된 리스트 2. 정렬 리스트의 오른쪽에 있는 정렬되지 않은 1번 위치의 원소는 앞의 원소와 크기 비교하여 자리 교환 3. 동일하게 2번 위치의 원소도 왼쪽으로 전진 4. 이 과정을 반복 i 20 19 14 16 18 - 20 19 14 16 18 1 19 20 14 16 18 2 14 19 20 16 18 3 14 16 19 20 18 4 14 16 18 19 20 👆i의 값에 따라서 pivot이 제자..

📌버블 정렬 (Bubble Sort) 👉 항목의 키 값을 풍선에 비유한 것이다 버블! 값이 클수록 더 높이높이 올라간다 가장 큰 값의 키가 오른쪽 끝으로 이동하고 그 다음 큰 값은 그 옆으로 그옆으로... 반복 📌시간복잡도 : O(n^2) 중복해서 비교가 일어난다 ✔️ 알고리즘 1. 가장 왼 쪽의 인접한 두 수를 비교하여 왼쪽 수가 더 크면 오른쪽과 위치 변경 2. 오른쪽으로 1칸 이동.. 같은 방식으로 두 수 비교하면서 교확 3. 가장 오른쪽에 도달할 때까지 반복 4. 오른쪽 끝에 최댓값이 도달하였으면 이 원소 제외하고 나머지 원소 반복 5 1 4 3 8 swap = 0 1 5 4 3 8 1 1 4 5 3 8 1 1 4 3 5 8 1 1 4 3 5 8 1 1 4 3 5 8 0 1 3 4 5 8 1 1 ..