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..

📌 (세자리 수) * (세자리 수) www.acmicpc.net/problem/2588 2588번: 곱셈 첫째 줄부터 넷째 줄까지 차례대로 (3), (4), (5), (6)에 들어갈 값을 출력한다. www.acmicpc.net 4 7 2 (1) x 3 8 5 (2) 2 3 6 0 (3) 3 7 7 6 (4) 2 4 1 6 (5) 1 8 1 7 2 0 (6) (1)과(2)는 입력이고 (3),(4),(5),(6) 을 출력할 때 #include int main(){ int a,b; scanf("%d %d", &a, &b); printf("%d\n", a*(b%10)); printf("%d\n", a*((b%100)/10)); printf("%d\n", a*(b/100)); printf("%d", a*b); }..

📌A/B 를 구하는 간단한 문제 main(){ double a,b; scanf("%lf %lf", &a, &b); printf("%.9lf", a/b); } 👉 scanf ("%f") ("%lf") f이면 float, lf이면 double이라고 생각해라 문제에서는 소수점 9자리 이상 출력이 되는 결과가 나왔으므로 float 대신 double을 사용해야 하는 문제 main(){ int a,b; scanf("%d %d",&a,&b); printf("%.9f",(double)a/b); } 아예 %d int 형으로 입력을 받고 print 할때 👉 (double)a/b 이용하여 형을 바꿔주어도 된다 * \\ 는 \ * \" 는 " * \' 는 '

📌합병 정렬 (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)..