-
퀵 정렬(Quick Sort) 구현
퀵 정렬 이 정렬은 정렬 중에서도 가장 빠른 정렬 알고리즘이다.(이름값 함) 퀵 정렬의 과정은 아래와 같다. 정렬해야 하는 임의의 배열 arr이 있고, 이 배열의 길이가 length라고 하자. Partition(low,high)이란 함수가 있다. 이 함수의 역할은 다음과 같다. 오름차순 정렬을 한다고 가정했을 때 arr[low](혹은 arr[(low+high)/2])를 기준으로 이 값보다 작은 원소는 이 배열의 왼쪽에,...
-
운영체제(Operating System) 핵심 개념 정리 (3) - Process
Process의 정의 실행 중인 프로그램. Process의 구조 다음과 같이 실행을 위한 자원들이 필요하다. CPU : PC, SP 같은 레지스터들 Memory(주소 공간)의 영역들, 낮은 주소 -> 높은 주소 순으로 작성 Text 영역: 프로그램 코드들 Data 영역: 전역 변수들 Heap 영역: 동적할당 된 것들. Stack 영역: 지역 변수, 매개변수 등.. I/O 정보:...
-
운영체제(Operating System) 핵심 개념 정리 (2)
운영체제(Operating System, OS)란 무엇인가 자원관리자(Resource Manager)라고 할 수 있다. 물리적인 자원(CPU, DRAM, Disk, Flash, Network)를 가상화 시켜서 더 효율적으로 자원을 관리할 수 있도록 해주는 시스템을 말한다. 운영체제와 커널(Kernel)의 용어에 대해서 헷갈릴 수 있는데, 커널은 항상 메모리에 상주해서 자원을 관리하는 것을 의미하고, 운영체제는 항상 메모리에 상주하지는 않는다. Linux 환경에서는 OS가 항상...
-
P, NP문제와 co-NP, NP-난해(NP-Hard), NP-완전(NP-complete) 개념 정리
인터넷 상에 돌아다니는 P,NP에 관한 글들은 나에겐 굉장히 어렵게 느껴졌다.(P-NP에 관한 글은 쉽게 적혀있어도, co-NP, NP-Hard, NP-complete에 관한 문제는 이해하기가 쉽지가 않다.) 원래 가볍게 알고 넘어가려 했지만, 워낙에 중요한 개념이기도 한데 자료들 대부분이 어렵고 애매하게 정리되어 있어서, 명확하게 정리해두면 좋을 것 같아 글을 작성했다. P - NP 문제 의의 P-NP...
-
(Data Structure) 최소 힙(Minimum Heap)
최소 힙이란? 부모 노드가 자식 노드보다 항상 작은 트리 구조를 말한다. 완전 이진 트리이고, 배열로 구현된다. 배열로 구현된다는 말은, 부모 노드의 index가 parentIndex라고 하면 왼쪽 자식 노드의 인덱스는 parentIndex*2, 오른쪽 자식 노드의 인덱스는 parentIndex*2+1 이라는 의미이다. 삽입 최고 깊이에서 가장 오른쪽에 삽입된다. 새로 삽입된 노드의 부모 노드를 계속 bottom-up 하면서,...