CS

알고리즘 - 선택 정렬(Selection Sort)

선택 정렬(Selection Sort)은 입력 배열 전체에서 최솟값을 선택하여 배열의 0번 원소와 자리를 바꾸고, 다음에는 0번 원소를 제외한 나머지 원소에서 최솟값을 선택하여 1번 원소와 자리를 바꾼다. 이런 방식으로 마지막에 2개의 원소중에서 작은 값을 선택하여 자리를 바꿈으로써 오름차순의 정렬을 마친다. 정렬 할 데이터: 15 9 6 27 24 9 8 13 10 1 5 정렬된 데이터 1회전 결과: 1 9 6 27 24 9 8 13 10 15 5 2회전 결과: 1 5 6 27 24 9 8 13 10 15 9 3회전 결과: 1 5 6 27 24 9 8 13 10 15 9 4회전 결과: 1 5 6 8 24 9 27 13 10 15 9 5회전 결과: 1 5 6 8 9 24 27 13 10 15 9 6회전 ..

알고리즘 - 버블 정렬(Bubble Sort)

버블정렬 이웃하는 숫자를 비교하여 작은 수를 앞 쪽으로 이동시키는 과정을 반복하여 정렬하는 알고리즘이다. 버블정렬의 시간복잡도는 O(N^2)이다. 한 번의 Loop에 요소의 갯수만큼 비교를 하며 총 Loop는 요소의 개수번 돈다. 정렬할 수: 15, 2, 6, 27, 24, 9, 8, 13,10, 1, 5 실행 결과 0 회전 결과: 2 6 15 24 9 8 13 10 1 5 1 회전 결과: 2 6 15 9 8 13 10 1 5 24 2 회전 결과: 2 6 9 8 13 10 1 5 15 24 3 회전 결과: 2 6 8 9 10 1 5 13 15 24 4 회전 결과: 2 6 8 9 1 5 10 13 15 24 5 회전 결과: 2 6 8 1 5 9 10 13 15 24 6 회전 결과: 2 6 1 5 8 9 1..

알고리즘 - 알고리즘

알고리즘이란 이름은 페르시아 수학자 알라콰즈미(al-Khwarizmi 서기 780 ~ 850년)로부터 유래되었다. 알고리즘은 문제를 해결하는 단계적 절차 또는 방법이다. 입력이 주어지고, 수행 결과인 해(또는 답)을 출력한다. 알고리즘의 특성 - 정확성 알고리즘은 주어진 입력에 대해 올바른 해를 주어야 한다. - 수행성 알고리즘의 각 단계는 컴퓨터에서 수행이 가능하여야 한다. - 유한성 알고리즘은 유한 시간 내에 종료되어야 한다. - 효율성 효율적일수록 그 가치가 높아진다. 알고리즘은 항상 시간적, 공간효율성을 갖도록 고안되어야한다. 알고리즘의 분류 - 분할 정복 - 그리디 - 동적 계획 - 근사 - 백트래킹 - 분기 한정 그 외에도 확률 개념이 사용되는 랜덤, 병렬, 분산, 양자 알고리즘 등이 있다.

알고리즘 - 동전 거스름돈

물건을 사고 거스름돈을 동전으로 받아야 한다면? 예를 들어 거스름돈이 730원인 경우 가장 적은 수의 동전을 받기 위해서 1. 730원에서 500원짜리 몇 개? 1개 -> 730 - 500 = 230 2. 230원에서 100원 짜리 몇 개? 2개 -> 230 - 200 = 30 3. 30원에서 50원짜리 몇 개? 0개 4. 30원에서 10원짜리 몇 개? 3개 500원짜리 1개 200원짜리 2개 10원짜리 3개 쓸데없이 재귀함수 소스코드) void change(int money){ if (money >= 500) { int fivehun = money / 500; printf("500원 짜리: %d개\n", fivehun); change(money % 500); } else if(money >= 100){..

알고리즘 - 이진탐색(Binary Search)

이진탐색(Binary Search), K찾기 - 오름차순으로 데이터를 정렬한다. - 중간 숫자와 K비교한 후 같으면 탐색 성공 - K가 작으면 앞부분 반에서 같은 방법으로 K를 찾고 - K가 크면 뒷부분 반에서 같은 방법으로 K를 찾는다. 값이 보다 크다면 mid + 1 ~ high / 2 값이 보다 작다면 low ~ mid - 1 / 2 void binarysearch(int a[], int high, int target){ int low = 0, mid; //첫 최솟값은 0 while (low

알고리즘 - 순차탐색(Sequential Search)

최대 숫자 찾기 가장 큰 숫자가 적힌 카드를 찾는 한 가지 방법은 카드의 숫자를 하나씩 비교하면서 본 숫자들 중에서 가장 큰 숫자를 기억해가며 진행하는 방법일 것이다. n개의 숫자가 있을경우 n - 1의 비교가 이루어진다. 1 3 2 4 1 5 6 9 6 5 10개의 숫자가 있을 경우 1번째 요소를 가장 큰 요소로 두고 10번까지 9번의 비교가 이루어진다. 소스코드) void SequentialSearch(int a[], int n){ int tmp = 0; for (int i = 1; i < n; i++) { if (a[tmp] < a[i]) { tmp = i; } } printf("\n%d\n", a[tmp]); }

운영체제(OS) - IPC(Inter-Process Communication), ITC(Inter-Thread Communication)

Concurrency는 프로그램의 성질이고 parallism은 기계의 성질이다. Concurrency(병행성) - 프로그램 여러 부분들이 순서에 상관없이 부분순서(partial-order)로 수행될 수 있는 능력을 일컫는다. 어떤 프로그램이나 알고리즘이 순서에 상관없이 동시에 수행될 수 있다면 concurrent하다고 말한다. 예를들어 1부터 100까지 숫자를 더하는 과정을 생각해보자면 숫자 100개를 여러 부분 집합으로 나눈 뒤 동시에 부분합을 구한다. 그리고 이 부분합을 다시 더하면 원래 얻고자 하는 값을 얻을 수 있다. 이 때 이 알고리즘을 concurrent하다고 말한다. 그런데 이 알고리즘이 정말 물리적으로 병렬로 돌아갈지 아닐지는 이 알고리즘이 어떤 하드웨어 위에서 돌아가는지 알아야 확답을 할..

운영체제(OS) - 스레드(thread)

스레드: 실행흐름(thread of execution)을 줄려서 스레드라 부름. 프로세스 1개당 1개의 스레드 프로세스 1개당 여러개의 스레드 프로세스와 스레드의 차이 프로세스: 프로세스는 프로세스가 새로운 프로세스를 생성하면 각 각 독립적인 메모리 영역을 소유한다. 이는 코드, 전역변수, 지역변수 모두에 해당한다. 스레드:  새로운 스레드를 생성 할 경우 부모와 자식은 stack(지역변수)만 다르고 독립적인 데이터 영역을 소유한다. 하지만 이외에 전역변수와, 코드는 같은 메모리 영역을 공유한다. 프로세스와 스레드 관련 함수. 프로세스: - fork() - exit() - waitpid() 스레드: - pthread_create() - pthread_exit() - pthread_join() - pt..

운영체제(OS) - 프로세스(2)

Running: CPU를 실제로 사용중인 상태 Ready: 언제든 실행 가능하지만 CPU는 다른 프로세스에 의해 점유되어 있기 떄문에 기다려야 하는 상태 Blocked(sleep): 외부 이벤트를 기다리고있는 상태 화살표 예) 1: 프로세스가 입력을 받기위해 Blocked상태로 변함 2: Scheduler에 의해 할당된 CPU사용시간을 모두 사용한 경우. 3: 2번 이후, Scheduler에 의해 다시 CPU제어권을 다시 넘겨받은 경우 4. 1번 이후 Input을 받고 CPU제어권을 넘겨받길 기다림. 프로세스 당 유지되는 정보들 PCB, Process Control Blocked 프로세스의 구현 인터럽트가 발생하면 OS의 가장 하위 레벨에서 발생하는일. 1. 인터럽트가 발생하면 2. 하드웨어 적으로 스택..

알고리즘 - 병합 정렬(Mearge Sort)

병합정렬 - '분할 정복' 방법을 채택한 알고리즘 - O(N * logN)의 시간 복잡도를 가진다. - 하나의 큰 문제를 두 개의 작은 문제로 분할한 뒤에 각자 계산하고 나중에 합친다. 기본 아이디어는 일단 정확히 반으로 나누고 나중에 정렬한다 계속 반으로 나누어서 한 개씩 남을 때 까지 나눈다. 예를 들어 a = { 8, 3, 4, 5, 1, 3, 2, 5} 이란 배열이 있을 경우 반을 나눌 경우 8 3 4 5 1 3 2 5 또 나눌 경우 8 3 4 5 1 3 2 5 또 반을 나눌 경우 8 3 4 5 1 3 2 5 한 개씩 남게된다. 다 나눴을 때 합치게 된다. 합치게 되는 과정은 보통 2의 배수만큼 합친다. 첫 번째 병합 첫 번째 합칠 때는 두 개씩 합치는데 합치면서 정렬을 하게 된다 8 3 4 5 ..