CS

알고리즘 - 힙 정렬(Heap Sort)

우선 힙 트리를 알고 가야한다. 출처: 동빈나 힙 트리 힙 트리는 트리 자료구조에서 자식노드보다 부모노드가 큰 상태를 뜻한다. 최대힙과 최소힙의 다른점은 점점 내려갈수록 값이 커지는가, 작아지는가 차이지만 모두 균일성을 유지해야 한다. 완전 이진트리 완전 이진트리는 왼쪽부터 채워나간다. 완전 이진트리는 배열에 넣게되어도 유휴 공간이 발생하지 않는다. 아래와 같은 이진트리가 있을경우 A번 노드부터 L번 까지의 노드에 번호를 매긴다면 아래와 같다. 이를 보고 추리한다. n노드의 부모 -> n / 2 (나머지는 버림) n노드의 왼쪽 자식노드 -> n * 2 n노드의 오른쪽 자식노드 -> n * 2 + 1 heapify heapify는 하나의 노드에 대해 수행한다. 자식노드와 자신을 비교해 자식노드에 더 큰 수..

알고리즘 - 쉘 정렬(Shell's Sort)

쉘 정렬은 삽입 정렬의 개선판. 삽입 정렬을 이해하고 있어야 한다. 삽입정렬 https://clamp-coding.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%82%BD%EC%9E%85-%EC%A0%95%EB%A0%ACInsertionSort 알고리즘 - 삽입 정렬(InsertionSort) 삽입 정렬) 두 번째 원소로 시작해서 그 앞의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자로를 삽입하여 정렬하는 알고리즘. 해당 배열을 오름차순으로 clamp-coding.tistory.com 쉘 정렬) 쉘 정렬은 갭의 크기가 줄어들면서 정렬되는 알고리즘이다. 예를 들어 n개의 값을 가지고 있는 배열이 있다면, 처음 g..

알고리즘 - 삽입 정렬(InsertionSort)

삽입 정렬) 두 번째 원소로 시작해서 그 앞의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자로를 삽입하여 정렬하는 알고리즘. 해당 배열을 오름차순으로 정렬한다면. 두 번쨰 요소를 시작으로 key이전의 요소들과 비교를 한다. 7보단 5가 더 작으므로 7을 밀고 5를 삽입한다. 2번째 요소를 정렬했기 때문에 3번쨰 요소인 1을 이전 요소들과 비교 시작. 7보다 1이 작기때문에 7을 이동, 1을 삽입. 2회전의 결과이다. 이 이후로도 같은 작업을 이어간다. 2번째 요소부터 시작하지만 1번째 요소까지 계속 비교하며 N to 1 까지 비교해나간다. 삽입 정렬의 특징 - 배열 내에서 교환하는 방식으로, 공간복잡도는 O(1)이다. 추가적인 부분은 원소를 교환할때 사용하는 임시요소정..

운영체제(OS) - System Call

시스템 호출(System Call) - 프로그램과 운영체제가 상호작용하기 위한 수단. - 프로그램한테 보여지는 운영체제 인터페이스 - System Call을 통해 프로그램은 필요로 하는 서비스를 운영체제 커널에 요청한다. 시스템 호출과 함수 호출 - 둘 다 요청한 사항을 수행하고 원래 프로그램으로 복귀 한다는 점은 같다. - 시스템 호출: 유저 모드(user mode)에서 커널모드(kernel mode)로 전환이 일어남. - 함수 호출: 유저 모드에서 계속 수행 시스템 호출 방법은 운영체제/기계마다 다르다. 어셈블리 언어(기계어) 수준에서 사용가능하며 고급언어(C언어) 수준에서는 시스템 호출로 이어지는 라이브러리가 제공된다. System Call의 일종인 File Management 해당 함수들은 운영체..

운영체제(OS) - 운영체제란

컴퓨터 시스템 컴퓨터 시스템은하드웨어 위에 운영체제가 작동한다 그 운영체제는 User interface frogram이 작동하며 그 위에 우리가 사용하는 프로그램들이 동작하는 식으로 운영된다 운영체제는 확장된 기계로서 지저분한(상세한) 하드웨어들을 감추고 추상화되고 깔끔하며 직관적이고 편리한 모습들을 사용자에게 제공해준다. 또한 자원 관리자의 역할을 한다. 각 프로그램은 시간적 측면에서 자원을 공유하고, 공간적 측면에서 자원을 공유한다. 시간적 측면에서 자원을 공유한다. -> CPU, printer 공간적 측면에서 자원을 공유한다. -> Memory 운영체제를 통해 한개의 CPU가 여러개의 프로그램에 접근할 수 있는 스케쥴링 역할을 하기 때문이다. 다중 프로그래밍: 실선은 CPU를 사용중인 구간, 점선..

운영체제(OS) - 프로세스

프로세스(process)는 컴퓨터에서 연속적으로 실행되고 있는 컴퓨터 프로그램을 말한다. 프로세스는 프로그램, 입력, 출력, 상태를 갖는다. 동일한 프로그램을 2번 실행시키면 2개의 프로세스가 생성된다. 이들은 프로그램은 갖지만 입력, 출력, 상태는 실행할 때, 조건에 따라 달라질 수 있다. 프로세스 모델: *program counter: 다음 cpu가 수행해야 할 명령어의 주소를 저장하는곳. (a) 다중 프로그래밍  메모리에 여러개의 프로그램을 적재한다 -> 다중프로그래밍 cpu는 한개의 프로그램씩 순차적으로 수행한다. 한개의 프로세스씩 순차적으로 실행하기 때문에 프로그램 카운터는 한개로 충분하다. (b) 병렬처리 4개의 프로그램을 독립적으로 병렬처리를 한다. 독립적인 순차프로세스를 진행한다. 동시..