본문 바로가기

Computer Science112

[알고리즘] ep1-4+) O(n + klog(n))의 힙정렬 문제: 중복이 있을 수 있는 n개의 정수들로 이루어진 무순리스트 L을 구축 후, k번째 작은 원소를 O(n + klog(n)) 시간에 찾아 인쇄하라  프로그램 요구사항:findKthSmallest(L, n, k)중복이 있을 수 있는 n개 정수 원소들로 이루어진 리스트 L의 원소 가운데 k-번째로 작은 원소를 찾아내 반환한다.buildList(n, min, max)난수함수를 이용하여 min ~ max 사이의 중복이 있을 수 있는 정수 n개의 무작위, 무순리스트를 만들어 반환한다.리스트는 1D 배열 또는 단일연결리스트 가운데 하나를 자유롭게 선택하여 구현한다.main()buildList(10, 1, 100)을 호출하여 1과 100 사이의 정수 10개로 이루어진 리스트를 만들어 L에 저장한다.정수들 사이를 공.. 2024. 7. 10.
[알고리즘] 정렬 알고리즘 선택 매뉴얼 ㅇ버블정렬 - 실무에서는 아예 사용하면 안된다"제자리 + stable" O(n^2)   ㅇ선택정렬: 우선순위 큐 (무순 리스트로 구현)"제자리 + unstable" O(n^2): 느리다 - 소규모 입력에 적합   ㅇ삽입정렬: 우선순위 큐 (순서 리스트로 구현)"제자리 + stable" O(n^2): 느리다 - 소규모 입력에 적합  ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ  ㅇ힙정렬: 우선순위 큐 (힙으로 구현)"제자리 + unstable" O(nlog(n)): 빠르다 - 대규모 입력에 적합   ㅇ병합정렬: 분할통치"제자리 X + stable" O(nlog(n)): 빠르다 - 초대규모 입력 + stable 결과에 적합   ㅇ퀵정렬: 분할통치"제자리 + unstable".. 2024. 7. 7.
[운영체제] 후기 운영체제에 대한 정리를 끝마치게 되었다처음 운영체제에 대한 큰 틀을 잡을 때는 혼공컴운(강민철) 책을 사용해서 기반을 다졌고, 이후 나머지 심화적인 내용은 박태순교수님의 Operating Systems: Internals and Design Principles(William Stalling), Operating System Concepts(Silberschatz, Abraham) 책으로 공부했다. 컴퓨터공학과 박태순교수님의 운영체제 강의는 세종대 대표 명강의로 유명하다 수강신청이 굉장히 치열해 과연 잡을 수 있을까 했지만 1순위 우선순위를 갖고 재빠르게 신청하니 다행히 운 좋게도 쟁취할 수 있었다 학습 분위기는 학생들 수준도 굉장히 높고 치열했다 컴퓨터공학과와 컴퓨터공학과를 복수전공하는 학생들 중 열의 .. 2024. 7. 7.
[알고리즘] ep1-6) 퀵정렬(quick sort) ㅇ퀵정렬(quick sort): 분할통치법에 기초한 정렬 알고리즘"제자리 + unstable" O(nlog(n))※ 최악의 시간 복잡도: O(n^2) (이미 정렬된 리스트에서 항상 최악의 피벗을 선택하는 경우) 이름에서 알 수 있듯이 복잡하지만 매우 효율적인 알고리즘이다 일각에서는 이렇게 지칭한다 '살아있는 레전드' *피벗(pivot): 기준점1. 피벗을 기준점으로 잡는다2. 피벗보다 작으면 왼쪽에, 피벗보다 크면 오른쪽에 둔다3. 왼쪽과 오른쪽을 각각 정복한다  [분할 함수(partition 함수) 과정]  다양한 피봇 선정 방식 -> 다양한 퀵소트 버전    (참고)퀵정렬 트리: quickSort의 실행을 이진트리로 보이기이진트리의 각 노드는 quickSort의 재귀호출을 표현하며 다음을 저장- 실행.. 2024. 7. 7.
[알고리즘] ep1-5) 병합정렬(merge sort) ㅁ분할정복법 == 분할통치법(Divide and Conquer): 문제를 작은 부분으로 나누어 해결한 후, 그 결과를 결합하여 전체 문제를 해결하는 방법e.g. 병합정렬, 퀵정렬, 이진탐색, 하노이탑   ㅇ병합정렬 = 합병정렬(merge sort): 비교 기반의 정렬 알고리즘 중 하나로, 분할 정복 기법을 사용"제자리 X + stable" O(nlog(n))폰 노이만이 개발했으며 stable 특성 때문에 실무에서 많이 사용된다  병합(merge) 예시 - 연결리스트로 구현한 merge 함수     (참고)      합병정렬 트리: mergeSort의 실행을 이진트리로 보이기이진트리의 각 노드는 mergeSort의 재귀호출을 표현하며 다음을 저장한다- 실행 이전의 무순리스트 및 분할- 실행 이후의 정렬리스.. 2024. 7. 5.
[알고리즘] ep1-4) 힙정렬(heap sort) 복습하고 오자!https://claremont.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-ep1-3-%ED%9E%99heap [알고리즘] ep1-3) 힙(heap)*완전 이진 트리(Complete Binary Tree): 트리의 위부터 아래, 왼쪽부터 오른쪽의 순서로 빠짐없이 가득 차있는 이진 트리 ㅁ힙(heap): 가장 크거나 가장 작은 값을 빠르게 찾기 위해 만든 완전 이진 트claremont.tistory.com    ㅇ힙정렬(heap sort): 힙을 이용하여 정렬하는 방식"제자리 + unstable" O(nlog(n)) 1. 원소들을 전부 힙에 삽입한다.2. 힙의 루트는 남은 수들 중에서 최솟값(or 최댓값)을 가지므로 루트를 출력하고 힙에.. 2024. 7. 4.
[운영체제] ep10) I/O Management and Disk Scheduling I/O를 다루는 OS 설계의 목적 2가지1. 속도 이슈2. 통일된 방식으로 모든 I/O 기기를 다루는 것 속도 이슈에서 중요한 것은 Seek time(탐색시간)이다Seek time(탐색시간) - 시간 大Rotational delay(회전지연)Transfer Time(전송시간) (참고) 탐색시간, 회전지연, 전송시간 https://claremont.tistory.com/entry/%EC%BB%B4%ED%93%A8%ED%84%B0-%EA%B5%AC%EC%A1%B0-ep7-%EB%B3%B4%EC%A1%B0%EA%B8%B0%EC%96%B5%EC%9E%A5%EC%B9%98 [컴퓨터 구조] ep7) 보조기억장치하드디스크와 플래시메모리같은 보조기억장치들은 개인 컴퓨터부터 서버구성 및 관리까지 다방면으로 사용되는 부품.. 2024. 7. 4.
[운영체제] ep9) Multiprocessor and Real-Time Scheduling 멀티 프로세서 시스템이란 뭘까? 2가지 특징이 있다- 프로세서가 여러 개이지만, 메인 메모리가 딱 하나다- 하나의 OS가 시스템 전체를 관리한다 멀티 프로세서 시스템에서는 동기화(Synchronization) 개념이 매우 중요하다 [멀티 프로세서 시스템 스케줄링 디자인 이슈들]- 동기화 빈도- 프로세서 수 프로세서에 프로세스를 할당하는 방법은 2가지가 있다방법 1: 각각의 프로세서마다 별도의 레디-큐를 둔다방법 2: 전역 큐를 둔다 (큐가 c.s. 안에 있어야 한다) - Mutual Exclusion요즘에는 방법 2를 채택한다 멀티 프로그래밍을 쓸까? 말까?동기화가 자주 일어나지 않는다면 문맥 전환이 적어 오버헤드가 적기 때문에 멀티 프로그래밍을 잘 사용할 수 있지만동기화가 자주 일어난다면 문맥 전환이 .. 2024. 7. 4.
[운영체제] ep8) Uniprocessor Scheduling ㅇCPU 스케줄링: Process에 CPU 시간을 할당하는 방법스케줄링의 목적은 유저 입장과 시스템 입장으로 나눌 수 있다response time(응답시간): 프로세스가 처음 도착한 후, 처음 CPU를 할당받아 실행되기까지 걸리는 시간turnaround time(반환시간): 프로세스가 시스템에 도착한 후, 모든 작업을 마치고 종료될 때까지의 총 시간throughput(처리율/처리량): 단위시간당 Process를 종료시키는 수processor efficiency(CPU 효율성): 얼마나 OS 개입이 적고, CPU를 이용하였는지Fairness(공정성): 같은 기준을 갖은 Process들은 모두 공정하게 같은 기회를 가져야 한다Predictability(예측 가능성): 언제쯤 끝날지에 대한 예측 가능성  스케.. 2024. 7. 4.

티스토리툴바