해나의 컴공생존기

대부분의 자료구조는 Search, Insert, Delete가 중요하다. 오늘은 배열의 Search, Insert, Delete 를 보려고한다. 배열 상태에 따라 방법이 달라진다 Packed vs Unpacked : 빈자리가 있나 없나 Sorted vs Unsorted : 정렬이 되어있나 없나 총 4가지 경우를 보려고 한다. Case 1 ) Packed, Unsorted 가장 간단한 방법 Item의 개수를 표시하는 변수가 따로 필요 하다. => 위 배열을 보면 item이 5개 있으니 어딘가에 5라고 저장 해놓으면 해결된다. Search : n개의 배열에서 어떤 값 x가 있는지 없는지 확인, O(n) Insert : [Search, O(n)], O(1)(상수시간) Delete : [Search, O(n)]..

우선 Merge Sort에 대해 알아 보기 전에 Merge에 대해 알아보자. Merge 와 Merge Sort 는 서로 같은 뜻 같지만 실제로는 둘이 조금 다르다. Merge 알고리즘은 soring 된 배열 두개를 합쳐서 새로운 배열을 만드는 알고리즘이다. 두 배열을 앞에서부터 비교해 나가면서 작은것들을 복사해서 한 배열에 넣는 알고리즘이다. 이러한 알고리즘을 이용하는 것이 Merge Sort 이다. 어떤 배열을 나눈다음에 서로 2그룹씩 합치면서 점점 올라오면서 정렬하는 것이 Merge Sort의 기본적인 로직이다. int sort(int a[], int n) { int h; int b[n]; h = n / 2; // copy a[] to b[] sort(b,h); // 반 나눈거의 앞부분 sort(b+..

Selection Sort의 알고리즘 로직은 다음과 같다. 배열이 있으면, 전체에서 제일 작은 값을 앞으로 옮긴다. 그 다음 나머지 부분에서 제일 작은 값을 앞으로 옮긴다. 그렇게 반복해서 결과적으로 정렬된 배열을 만들어 내는 것이다. int sort (int a[], int n) // n 은 배열의 크기 { //m 최소값 인덱스, t 는 교환할때 활용 int i, j, m, t; for (i = 0; i a[j] ) m = j; t= a[i]; a[i] = a[m]; a[m]=t; // 두 값의 교환 } return; } 먼저 코드를 보자면 첫번째 루프에서 0부터 n 까지 돌아가는데 거기서 최소값을 찾아서 m에 저장한다. 그리고 그 안에서 한번 더 루프가 돌아가는데 j 는 i 부터 n 까지 가장 작은 ..

Array ( 배열 ) 정의 : 연속된 주소, 동일한 Type 장점 : n개 중 k번째 access(Read&Write)가 상수 시간에 가능, Search(어떤 x가 배열안에 있느냐?)가 빠름 단점 : 크기 변화 비용이 크다. Insert, Delete가 느릴수 있다. 사용 : 변화가 없거나 드문 자료 배열에서 가장 흔히 쓰이는 search 방법은 linear search 이다. 이는 하나하나 다 읽어보며 찾는 방법이고 모두 다 읽어봐야해서 크게 효율적이지 않다. 또 다른 방법은 Binary Search 이다. 이 방법은 sorting 되어있는 상태에서만 사용가능하다. 기본적인 로직은 절반을 확인하고 그의 절반..절반.. 을 확인하는 방법이다. 코드로 나타내면 int search(int a[], int ..

수학적 귀납법 ( 명제 : P(n)이 있을때 ) 기본형 : p(1)이 참이고, p(n-1) -> p(n) 이 참이면 p(n)은 모든 자연수 n에 대하여 참이다. 강한 형태 : p(1)이 참이고, p(1)^p(2) ^ ....^p(n-1) -> p(n) 이 참이면 p(n)은 모든 자연수 n에 대하여 참이다. 수학적 귀납법은 크게 Base 와 Step 부분으로 나뉜다. base: p(1) 이 참이다. step : p(n-1) -> p(n) 가 참이라고 보이면, p (n) 은 모든 자연수 n에 대해 참이라고 증명이 가능하다. base 와 step은 서로 독립적이고, 보통 base는 참인것을 금방 알수 있으며, 포인트가 되는 것은 step 부분이 참인 것을 알아내는 것이다. 그런데 step 에서 p(n-1) -..

변수는 정보를 담아주는 박스같은 존재이다. 변수는 이름, 주소, type으로 구성되어있다. 이름: 사람들을 위한 속성, 변수들을 구별할 수 있도록한다 주소: CPU 와 메모리를 위한 속성, 변수들을 구별할 수 있도록 한다. Type: 몇바이트의 크기를 갖고 어떤 bit들를 어떤 의미로 읽을 것인가를 결정 (문자형, 정수형) 변수를 선언 할 때 Type 이름 = 변수값 ex) int a =8 이런식으로 선언한다. 이렇게되면 우리는 이름과 타입은 알 수 있지만 주소는 알 수 없다. 우리는 다음과 같은 이유로 주소를 알아야한다. - 모든 변수를 다 만들어 둘 수가 없음 - 메모리를 얼마나 쓸지 미리 알 수 없음 -> 메모리 할당 필요 Type이 주소인 변수를 우리는 포인터 변수라고 한다. 포인터 변수는 int..

자료구조를 공부하기 전에 컴퓨터의 기본적인 구조와 컴퓨터가 어떤 방법으로 실행되는지부터 보겠다. 메모리 안에는 무수한 바아트, 비트들이 있다. - 비트 : 0과 1을 표시할 수 있는 전자회로적인 도구 - 바이트 : 8개의 비트 이러한 메모리는 어떤 방식으로 저장하고 동작할까? 이를 알아보기 위해 간단한 코드와 이가 동작하는 방법을 설명해보겠다. int main() { int a,b,c; c= a+b; } //a:300 b:600 C:900 주소에 저장된다고 가정 int a,b,c 가 실행 되면 a,b,c는 memory 어딘가에 저장이 될 것이다. 메모리에는 0번부터 차례대로 번호가 매겨져 있으며 int a,b,c는 빈 자리에 가서 각 4바이트의 연속된 데이터를 차지하고 있을 것이다. 다음으로 c=a+b ..

1. I/O Devices interface : 시스템 소프트웨어가 작동을 제어할 수 있도록한다. 모든 장치에는 지정된 인터페이스와 프로토콜이 있다. internal : 장치가 시스템에 제공하는 추상적인 명령을 구현하기 위해 구현되어있다. While (STATUS == BUSY) ; // 바쁘니까 이따 와라 Write data to DATA register Write command to COMMAND register (Doing so starts the device and executes the command) While (STATUS == BUSY) ; // wait until device is done with your request 비효율성 및 불편함 1. Polling : Busy 면 계속 기다려..

1. Non-deadlock bugs 1.1 Atomicity-violation bugs 코드 영역은 원자성이지만 실행 중에는 원자성이 적용되지 않을 수도 있다. = race conditon -> mutex 로 해결 가능 1.2 Order-violation bugs 원하는대로 스레드가 실행되지 않아 오류가 생길 수 있다. -> mutex랑 cond를 이용하여 해결 가능 2. Deadlock bugs 2.1 Conditions for Deadlock - Mutual exclusion : 스레드가 lock 되어있어야 함 - Hold-and-wait : lock을 갖고 다른 lock을 갖는다 - No preemption : lock을 강제로 뺏지 못한다 - Circular wait : 각 스레드가 다른 스레드..

Semaphores를 이용하면 lock과 conditon variable을 동시에 사용할 수 있다. 이런 Semaphores는 여러가지 용도로 사용할 수 있다. int sem_init(sem_t *s, int pshared, unsigned int value) // 가운데 인자에는 공유한는 프로세스개수, 마지막인자에는 초기값을 넣어 초기화하는 함수이다 int sem_wait(sem_t *s) // s 를 1 감소시키고 s가 음수가 되면 재우는 함수 int sem_post(sem_t *s) // s 를 1 증가시키고 큐에 자는애가 있으면 깨우는 함수 /*사용예시*/ sem_t m; sem_init(&m, 0, 1); sem_wait(&m); // critical section here sem_post(&m..