히프정렬 (heap sort) 합병 정렬방식은 비록 최악의 경우 연산 시간과 평균 연산 시간 모두 O(nlogn)이지만, 정렬할 레코드 수에 비례하여 저장 공간이 추가로 필요하다. 히프 정렬(heap sort)은 일정한 양의 저장 공간만 추가적으로 필요한 동시에, 최악의 경우 평균 연산 시간이 O(n log n)이다. 하지만, 히프 정렬은 합병 정렬보다 약간 느리다. 히프 정렬의 핵심 알로리즘은 이름처럼 히프를 사용한다. 그중에서도 최대 히프 구조를 이용한다. 따라서, 최대 히프가 되도록 레코드를 재조정 후 루트를 하나씩 빼내면서 정렬을 하는 기법이다. 알로리즘을 정리하면, 1. 최대 히프 생성 2. 히프의 첫 번째 와 마지막 레코드 스와핑 3. 히프 크기 감소 및 재조정 4. n-1 반복 최대 히프 생..
합병 정렬(merge sort) 2개의 정렬된 리스트를 하나의 정렬된 리스트로 합병하여 정렬하는 정렬기법. while 루프를 반복할 때 마다 k는 1씩 증가. k의 총 증가량 n-1+1 for 명령문은 최대 n-i+1 레코드를 복사한다. 레코드 길이 s 가 1보다 클 때 배열 대신 연결 리스트를 이용하면 이들 n-l+1 레코드를 포함한 새로운 정렬된 연결 리스트를 얻을 수 있다. merge 함수에서 배열 mergedList 가 필요한 n-l+1 개의 레코드 공간이 필요 없게 된다. 대신 n-l+1 개의 링크에 대한 공간이 필요하다. void merge(element initList[], element mergedList[], int i, int m, int n) { int j, k, t; j = m + ..
퀵 정렬(Quick Sort) 삽입 정렬은 아주 좋은 평균 정렬 성능을 가지는 정렬 알로리즘이다. 퀵 정렬은 피벗을 정하고 왼쪽과 오른쪽에서 각각 시작하여 왼쪽부터는 피벗이 크거나 같으면, 오른쪽에서는 피벗보다 작거나 같으면 두 값을 스왑 해주고, 오른쪽 값과 왼쪽값이 서로 교차할때 새로운 피벗을 설정하여 이 작업을 재귀적으로 실행하는 방법이다. pivot 26이라고 가정하면 26보다 37 크니 멈추고 19가 피벗보다 작으니 멈추면 둘이 교환한다. 그리고 61 과 15 가 되면 스왑하고 둘이 교차하여 피벗과 right를 스왑해준다. 이 과정을 반복한다. void quickSort(element a[], int left, int right) { int pivot, i, j; element temp; if ..
삽입 정렬(Insertion sort) 새로운 레코드를 i개의 정렬된 레코드 리스트에 끼워넣어 크기가 i+1로 정렬된 결과 레코드 리스트를 만드는 것이다. 즉, a[0]을 사용하면 리스트 끝 검사(즉, i key.key1) //자리바꿈 { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = key; } } void InsertSort_key2(array arr[], int n) //key2 값을 기준으로 { int i, j; array key; for (i = 1; i = 0 && arr[j].key2 > key.key2) { arr[j + 1] = arr[j]; j--; } arr[j +..
해싱(hashing)? 해시함수(hash function)란 데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수입니다. 이 때 매핑 전 원래 데이터의 값을 키(key), 매핑 후 데이터의 값을 해시값(hash value), 매핑하는 과정 자체를 해싱(hashing)라고 합니다. 해시함수는 해쉬값의 개수보다 대개 많은 키값을 해쉬값으로 변환(many-to-one 대응)하기 때문에 해시함수가 서로 다른 두 개의 키에 대해 동일한 해시값을 내는 해시충돌(collision)이 발생하게 된다. 슬롯이 한개일 경우 무조건 충돌이 일어나며 우리는 충돌은 피할 수 없으므로 최대한 적게 일어나는 쪽으로 설계 해야 한다. 슬롯이 한개일 경우에는 오버플로우와 충돌은 같다. Hashi..
fork ( ) 의 필요성 execvp 를 이용하여 프로그램을 실행시킬 때 완전히 새로운 프로그램이 실행된다. 따라서 fork ( ) 를 이용해 각각 별도의 2개의 프로그램을 실행시켜 기존 프로그램 또한 실행되도록 한다. - fork ( ) 는 자기 자신을 복제한다. - 복제 후 부모 프로세스와 자식 프로세스로 나뉜다. - 복제된 새로운 프로세스는 부모 프로세스와 같은 코드와 데이터를 가진다. - fork ( ) 리턴값은 -1 이면 실패 0 이면 자식 프로세스 그외이면 부모 프로세스 fork ( ) 의 작동원리 /* forkdemo1.c * shows how fork creates two processes, distinguishable * by the different return values from ..
흔히 리눅스에서 프로그램은 쉘이라는 환경에서 작동함 프로세스 -프로그램 : 파일에 저장된 일련의 기계어 명령어 - 프로그램 실행이란 : 기계어 명령을 메모리에 로드한 후 프로세서(CPU)에서 명령어 하나씩 실행하는 프로그램 - 프로세스 : 실행중인 프로그램 프로세스는 메모리 페이지의 할당 목록을 유지하는 구조가 있음. 프로세스 생성은 디스크 파일 생성과 유사하다. --> 커널은 프로그램의 기계어 코드와 데이터 바이트를 보관할 수 있는 메모리 페이지를 찾아야한다. --> 커널은 메모리 할당 정보와 프로세스의 속성을 저장하기 위해 데이터 구조를 설정한다. 쉘(Shell)의 작동원리 A. 유저 타입의 a.out B. 쉘은 프로그램을 실행하기 위한 새로운 프로세스를 생성한다. C. 셀은 디스크에서 프로세스로 프..
시그널이란? 시그널은 커널에서 프로세스로 전달되는 한 단어 -동기 신호(Synchronous signals) 프로세스가 수행하는 작업에 의해 발생되는 신호( 예 : 0으로 나누기) -비동기 신호(Asynchronous signals) 사용자가 인터럽트 키를 누르는 등 프로세스 외부의 이벤트로 인한 신호 시그널에 대해 프로세스가 무엇을 할 수 있는가? 프로세스는 3가지 선택이 가능하다. Accept(기본) signal (SIGINT, SIG_DFL); Ignore(무시) signal(SIGINT,SIG_IGN); Call a function(함수 호출) signal(signum, functionname); signal 목적 : 단순 시그널 핸들링 헤더 : #include 사용법 : result = sign..
컴퓨터 개론 SSDSSD는 가장 성능향상 체감이 큰 부품이다.만약 컴퓨터를 새로 산다면 무조건 달아보라고 강추!하는 부품이다. 그게 아니더라도 기존의 컴퓨터에 SSD가 없다면 한번 달아보라고 추천하는 부품이다." SSD Solid State Drive"SSD는 HDD의 플래터와 같은 물리적인 움직임이 전혀 없는, 고정된 형태로 전자적 방식으로 작동하는 드라이브다.그럼 이러한 SSD를 구성하는 것들 중 제품의 대략적 수준을 알 수 있는 방법은 무엇일까?→ NAND Flash Memory Type, 컨트롤러, 제조사(펌웨어)를 따져 보는 것이다.NAND Flash Memory Type : 제품의 대력작 스펙 및 수명컨트롤러 : 제품의 대략적 내구성과 스펙제조사 : 펌웨어 제작 능력 혹은 과거 전력을 통한 안..
흔히들 포카리라고 불리는 GTX 1070 제트스트림(일젯)과 슈퍼제트스트림(슈젯)은 전원부, 기판, 쿨러 등이 대부분 동일합니다. 실제로, 제조사에서도 오버율만 다를뿐이라고 코멘트했습니다.그래서 일젯도 오버수율이 좋으면 얼마든지 슈젯으로 변신이 가능합니다.! 일젯 돈으로 슈젯 퍼포먼스를 느낄 수 있는 방법이 존재하는 것이죠.제트스트림의 파스 점수는 18K대고 슈퍼제트스트림의 파스점수는 19K대로 약 1000점 차이가 납니다. 일젯만해도 FHD 환경에서는 모든 게임을 학살하시겠지만, 좀 더 높은 성능을 원하시는 분들은 슈젯으로 실사용이 가능합니다. 제트스트림에 슈퍼제트스트림 바이오스 덮어씌우기!일단 자신의 일반제트스트림의 클럭이 어느정도인지를 알아야합니다.만약 자신의 오버율도 모르고 바이오스를 입힐 시 그..
인텔의 7세대 프로세서 카비레이크의 데스크탑 라인업이 중국에서 유출되었다.카비레이크는 여러 멀티플 플랫폼을 가지지만 오늘의 포커는 메인스트림 데스크탑 칩을 살펴보겠다. 인텔 카비레이크 데스크탑 CPU 라인업 유출 – 10 SKUs 세부사항라인업의 세부정보는 Coolaler 에 따르면 메인스트림류 데스크탑 칩들은 2017년 초로 공개가 연기 되었다. 현재, 인텔은 카비레이크 아키텍쳐 기반의 모바일 프로세서를 가능한 빨리 선보일 게획인데, 이미 IDF에서 몇몇 모바일 칩들이 OEM형태로 대기업에게 보내졌다. 인텔의 2016년 최대 중점은 가능한 모바일 카비레이크 (4W~15W)를 2016년 가을에 데스크탑으로 넘어가기전 공개하는 것이다.다시 데스크탑으로 돌아와서, 데스크탑 CPU는 2개의 다양성을 가지는데,..