잡다한 IT 썸네일형 리스트형 퀵소트 vs 머지소트 Sorting 알고리즘을 다시 공부하면서 궁금증이 생겼다. 머지소트는 시간 복잡도가 항상 O(NlgN) 인 반면에, 퀵 소트는 시간 복잡도가 최선일때 O(NlgN) 이고, 피봇값을 최대 혹은 최소로 설정할 경우 최악으로 O(N^2) 이 생긴다. 뭐 어떤 수열을 Sorting 하느냐에 따라 다르겠지만, 일반적으로 퀵소트를 많이쓰고 빠르다고 하는데 그 이유를 알 수가 없어서 SLACK을 통해서 물어봤다. 그 답은 더보기 Sort , Search 1. 선택 정렬 (Selection Sort) 2. 삽입 정렬(Insertion Sort) 3. 버블 정렬(Bubble Sort) 4. 병합 정렬(Merge Sort) 5. 퀵 정렬(Quick Sort) - 참조 블로그=> http://mygumi.tistory.com/308 6. 이분 탐색(Binary Search) 재귀/비재귀 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610.. 더보기 물리 메모리 관리 #물리 메모리 관리 자료구조 Node -> Zone -> Page Frame Node 는 여러개의 Zone 으로 구성 됨. Zone 은 여러개의 Page Frame으로 구성됨. Page Frame 은 물리 메모리의 최소 단위. #BUDDY ALLOCATOR 와 SLAB ALLOCATOR Page Frame은 보통 최소 단위로 4KB를 사용한다. 이로 인해서 외부 단편화(External Fragmentation) , 내부 단편화 (Internal Fragmentation) 가 발생한다. 이러한 단편화를 해결하기 위해서 리눅스에서 Buddy allocator 와 Slab allocator 를 사용한다. 하지만 Buddy 시스템이 Page Frame 을 반복적으로 할당/해제 해야하는데 오버헤드가 많이 발생하였.. 더보기 스케줄링 고려할 점 스케줄링 고려할 점 1. 어떤 task 를 ready queue( run queue) 에서 선택할 것인가? 일반 task : CFS( completely fair scheduler) 를 이용 실시가 task : FIFO , RR, DEADLINE 정책을 사용 2. CPU의 각 run queue 의 부하가 균등하지 않은 경우에는? 부하 균등( load balancing ) 기법을 활용한다. load_balance() 함수에서는 특정 CPU가 매우 바쁘고 다른 CPU들은 idle 하다면 다른 CPU로 task를 이주시켜서 전반적인 성능 향상을 시도한다. 이때 특정 task 를 이주하기로 결정했다면, 문제는 '어느 CPU' 로 이주시킬 것인지 결정하는 것이다.이때는 task 이주로 인한 성능 저하를 최소화 시.. 더보기 fork , vfork , clone fork , vfork, clone 의 특징 fork - 프로세스를 하나 더 생성한다. 과거에는 부모의 정보를 모두 복사해서 프로세스 생성에 시간이 오래 걸렸다. 하지만 최근에는 COW (Copy On Write) 라는 방식으로 쓰기가 일어날 떄만 복사하여 문제점을 해결했다. vfork - 프로세스를 하나 더 생성하는 방식으로, fork 과 같다. 하지만 fork 나 vfork 는 결국 최종적으로 커널 내부에서 do_fork 함수를 호출하는데, 이때 vfork 일 경우에는 새로 생성된 프로세스가 exit 이나 exec 를 실행하기 전까지는 블락을 시킨다. (참고 사이트 : http://pinocc.tistory.com/2 ) clone - 프로세스가 아닌 쓰레드를 생성한다. 쓰레드는 부모와 자원을 공유하.. 더보기 set-associative cache Set - Associative 에 대해서 더 공부해보기. 더보기 연결 리스트로 완전 이진 탐색(BST) 구현 이진 탐색 트리(Binary Search Tree) - 기본적인 접근 Search()는 대소 비교를 하면서 해당 값과 같은 Node 찾기 Insert()는 대소를 비교해서 빈 자리에 Insert , Tree가 비어있을 때 예외처리. Delete()는 3가지 경우로 나눠서 접근 (삭제할 값이 없는 경우 예외처리) 1. 자식이 없는 경우 – 그냥 삭제 2. 자식이 1개인 경우 – 부모와 교환 ,자식 데이터 delete 함수로 삭제(재귀) 3. 자식이 2개인 경우 – 오른쪽에서 가장 왼쪽 값이나, 왼쪽에서 가장 오른쪽 값이랑 교환, 바꾼 값을 delete 함수로 삭제(재귀) 1234567891011121314151617181920212223242526272829303132333435363738394041424.. 더보기 연결리스트를 통한 큐 구현 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114#include#include typedef struct Node { int data; Node* next;}Node; typedef struct Queue{ int size; Node* front; Node* back;}Queue; //연결리스트 큐에서 큐가 비어있을때/ 비어있지 않을 때 나.. 더보기 이전 1 ··· 6 7 8 9 10 11 12 13 다음
