juju의 컴공일지

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

📌삽입 정렬 (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 ..

📌정렬 Sorting 주어진 레코드를 원하는 키 필드 값의 순서대로 나열하는 작업 ✔️내부 정렬 (Internal Sort) 레코드의 리스트를 주메모리에서 처리 레코드의 수가 메모리에 모두 적재될 정도로 적으면 내부 정렬로 충분 ✔️외부 정렬 (External Sort) 하드 디스크와 같은 별도의 보조 기억장치를 사용하여 처리 레코드의 수가 주메모리의 크기보다 많을 경우 외부 정렬 + 내부정렬 필요 ❓성능은? 키 값의 비교 횟수, 데이터 이동 횟수에 의해 평가됨 ✔️대표적인 내부 정렬 알고리즘 종류 선택 정렬 (Selection Sort) 버블 정렬 (Bubble Sort) 삽입 정렬 (Insertion Sort) 퀵 정렬 (Quick Sort) 쉘 정렬 (Shell Sort) 힙 정렬 (Heap Sor..

📌교착상태 자원을 점유한 상태에서 다른 프로세스가 점유하고 있는 자원을 요구하며 무한정 기다리는 현상 ✔️교착상태 발생하기 위한 필요 충분 조건 ( M H N C ) 👉 상호배제 (Mutual Exclusion) 한번에 한 프로세스만 자원을 사용하는 것 👉 점유와 대기 (Hold & Wait) 다른 자원이 할당되기를 기다리는 동안 이미 확보한 자원을 계속 보유하고 있는 것 👉 비선점 (Non-Preemptive) 강제로 빼앗을 수 없다 👉 환형 대기 (Circular Wait) 서로간의 요구 관계가 회전된다 그렇다면,, ❓교착상태 해결방법은? ✔️예방 기법 (Prevention) 교착 상태는 위의 필요충분 조건이 "모두" 만족해야 하기 때문에 이중 1개의 조건만 발생하지 않아도 예방 가능 -상호 배제 부..