알고리즘
힙 정렬
힙은 최솟값이나 최댓값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리이다. 힙에는 최대 힙과 최솟 값이 존재하는데 최대 힙은 '부모 노드'가 '자식 노드'보다 큰 힙이다.
힙정렬을 하기 위해서는 기본적으로 힙 구조를 가지도록 해야한다.
Heapify Algorithm를 수행해주면 전체 트리가 최대 힙 구조로 형성된다.
static void heapify(int[] arr, int left, int right){
//부모노드랑 자식노드 비교해서 자식노드가 더 크면 바꾸기
int tmp = arr[left];
int parent;
int child; //자식 노드중 큰거
for(parent=left; parent<(right+1)/2; parent = child){ //right의 부모노드까지
int cl = (parent*2+1);
int cr = (parent*2+2);
child = (cl > cr) ? cl : cr;
if(arr[parent] > arr[child])
break;
swap(arr, parent, child);
}
}
static void heapSort(int[] a, int n){
//heapify를 이용해 힙 구조 만들기
for(int i=(n-1)/2; i<=0; i--) // a[i] ~ a[n-1]를 힙으로 만들기 i=4,3,2,1,0 //i=(n-1)/2 자식노드 있는데 까지만 부르는거 아닌가...? 그러면 (n-2)/2 아니야?
heapify(a, i, n-1);
//루트와 맨마지막 요소를 바꿔서 힙 정렬로 바꾸기
for(int i=n-1; i<0; i--){
swap(a, 0, i);
heapify(a, 0, i-1);
}
}
계수정렬 , 도수정렬
대소관계를 판단하지 않고 빠르게 정렬할 수 있는 알고리즘
OS
-
다중 프로그래밍이란 ?
여러 개의 작업들이 메모리에 있고 CPU는 이들 사이를 오가며 실행해 줌으로써 가능한 좋은 결과를 얻고자 하는것 -
프로세스가 하나 만들어진다는 것은 곧, 그 프로세스에 대한 모든 것을 표현하는 PCB 하나가 만들어진다는 말과 같다.
-
프로세스의 상태
- 생성 상태 : 사용자가 요청한 작업이 커널에 등록되고 PCB가 만들어진다.
- 준비 상태 : 메모리가 할당된다. CPU만 주어지면 바로 실행할 준비가 되어있는 상태
- 보류 상태 : 만약 메모리를 할당해 줄 수 없을경우 준비상태가 아닌 보류 상태가 된다.
- 대기 상태 : timeout되거나 입출력 처리를 요청하거나 할 때 CPU를 양도하고 요청한 일이 완료되기를 기다리면서 대기한다.
- 종료 상태 : 모든 자원들이 회수되고 PCB만 커널에 남아있는 상태
해야할것
GSAT , OS, 스프링, 알고리즘, 영어..ㅠ
그리디, 탐색, 기본 동적 프로그래밍만 열심히 하래 기본만
코드업 기본 100제 풀어보기
백준 - 그리디 알고리즘부터 풀기, 그 다음 탐색, 기본 동적 50문제씩 풀어보기
프로그래머스에 카카오 코딩 테스트도 있대
안녕하세요