[패스트캠퍼스 수강 후기] 올인원 패키지 : 컴퓨터 공학 전공 필수👉C언어인강 100% 환급 챌린지 45회차 미션

 

 

 

환급미션 45일째...

 

 

 

소프트웨어 베이직 - 자료구조와 알고리즘 - 09. 정렬 - 계수 정렬

소프트웨어 베이직 - 자료구조와 알고리즘 - 10. 정렬 - 기수 정렬

 

운영체제 - 쓰레드의 이해 - 01. 스레드 개념

운영체제 - 쓰레드의 이해 - 02. 스레드 장단점

운영체제 - 쓰레드의 이해 - 03. 스레드 동기화 문제

 

 

 

 

 

소프트웨어 베이직 - 자료구조와 알고리즘 - 09. 정렬 - 계수 정렬

 

 

 

- 계수 정렬 (Counting sort) : 데이터의 개수를 세는 정렬 알고리즘

 

 

데이터의 크기를 기준으로 분류 O(N)의 시간 복잡도를 가진다.

동작이 빠른 편

데이터의 크기가 한정적일 때 사용할 수 있다.

 

 

 

원소들을 살펴보면 데이터의 크기가 0~3까지의 범위 내에 있다.

따라서 인덱스 값이 0~3까지로 정해진다.

 

 

 

위의 그림과 같이 배열에 원소의 값들을 기록한 이후에,

앞에서부터 배열을 확인하면서 값을 출력한다.

-> 0 0 1 1 1 2 2 2 3 3

 

 

 

- 계수 정렬의 구현

 

 

-----------

#include <stdio.h>

#define MAX_VALUE 10001

//데이터의 크기가 10001을 넘어가면 정렬할 수 없다. 크기 제한을 두기 위해 사용하였다.

 

int n,m;

int a[MAX_VALUE];

 

int main()

{

    scanf("%d", &n);

    for (int i=0; i<n; i++) //정렬

    {

        scanf("%d", &m);

        a[m]++; //값에 해당하는 인덱스의 원소를 1씩 증가

    }

    for (int i=0; i<MAX_VALUE; i++)

    {

        while (a[i]!=0) //특정 원소의 크기만큼 해당 인덱스를 출력

        {

            printf("%d ", i);

            a[i]--;

        }

    }

    

    return 0;

}

-----------

 

 

위의 코드를 작성하고,

5 (n, 원소의 개수)

1 4 3 1 7

을 입력했을 때

 

원했던대로 

1 1 3 4 7 의 순서대로 출력되는 것을 볼 수 있다.

 

 

 

 

 

 

소프트웨어 베이직 - 자료구조와 알고리즘 - 10. 정렬 - 기수 정렬

 

- 기수 정렬 (Radix sort)은 자릿수를 기준으로 차례대로 데이터를 정렬하는 알고리즘 

 

 

데이터를 자릿수를 기준으로 분류,

가장 큰 자릿수를 D라고 했을 때 O(DN)의 시간 복잡도를 갖는다.

- 사실상 N에 가깝기 때문에 계수정렬만큼 빠른 알고리즘

계수 정렬보다는 더 느리지만, 숫자가 매우 큰 상황에서도 사용할 수 있다.

(계수정렬에서는 숫자의 크기가 커지면 사용이 어렵다.)

 

ex) 180 -> D=3

 

 

위의 예제에서 원소를 살펴보면

가장 큰 값은 341로, 백의 자리가 가장 큰 값이므로

총 세 번만 확인하면 된다.

 

 

 

먼저, 1의 자리를 확인했을 때 결과는 위와 같다.

 

 

 

다음으로, 각 인덱스에 도달할 때까지의 누적값을 구한다.

(결과배열을 만들기 위해 필요하다.)

 

 

 

결과배열을 만들 때는

원소를 뒤에서부터 확인한다.

제일 뒤에 있는 원소가 34 이고,

1의 자리의 값이 4 이기 때문에 (누적값에 해당하는 값이 인덱스로 사용된다.)

기존에 4에 해당하는 위치, 즉 4번째 값으로 34가 들어가게 된다.

또한 

결과배열으로 처리했기 때문에 누적값에서 -1을 해준다.

 

 

 

앞에서 사용했던 방법대로 순서대로 정렬해주게 되면

결과는 위와 같다.

 

누적값에 해당하는 값이 인덱스로 적용되었고

결과값을 살펴보면 1의 자리가 0,1,4,4,5,5,7로 정렬된 것을 볼 수 있다.

 

 

 

10의 자리를 기준으로 정렬을 해 볼 예정이다.

 

먼저 자릿수 배열을 하고,

 

 

1의자리에서와 마찬가지로 누적값을 구해주고

원소를 뒤에서부터 확인하면서 결과배열을 만들어준다.

누적값을 인덱스로 사용하고 -1을 해준다.

 

 

 

정렬이 끝나면 결과 배열은 위와 같다.

10의 자리를 기준으로,

0,2,3,3,4,6,8 로 정렬된 것을 볼 수 있다.

 

 

 

100의 자리가 0이 아닌 원소는 341 하나 뿐이기 때문에

 

 

자릿수 배열의 결과는 위와 같고,

 

누적값은 위와 같게 된다.

 

역시 원소의 뒤에서부터 확인하면서 정렬을 해 주게 되면

 

 

정렬이 끝나면 결과 배열은 위와 같이 나오게 된다.

100의 자리를 기준으로 

0,0,0,0,0,0,3으로 정렬된 것을 볼 수 있다.

 

 

 

 

- c언어로 기수 정렬 구현하기

 

 

 

 

코드를 위와 같이 작성했다.

 

 

제대로 구현되었는지 확인을 위해

원소의 갯수 = 5

132, 27, 476, 277, 1을 차례대로 배열에 넣은 후

radixSort (기수정렬) 함수에 돌리면

결과값은 위의 그림과 같이, 내가 원하던대로 순서대로 정렬되었다는 것을 확인할 수 있다.

 

 

 

 

 

운영체제 - 쓰레드의 이해 - 01. 스레드 개념

 

- Thread (스레드)

 

 

* Light Weight Process 라고도 함

 

* 프로세스 간에는 각 프로세스의 데이터 접근 불가 (IPC를 사용해야 접근 가능)

 

* 스레드

• 하나의 프로세스에 여러 개의 스레드 생성 가능

• 스레드들은 동시에 실행 가능

• 하나의 프로세스 안에 있으므로, 프로세스의 데이터에 모두 접근 가능 (IPC와 같이 특별한 기법 필요없다)

 

* Thread는 각기 실행이 가능한 stack 존재

 

 

 

 

 

 

 

- Multi Thread (멀티 스레드)

 

 

소프트웨어 병행 작업 처리를 위해 multi thread 사용

 

 

 

부모 프로세스 안에 

thread A, thread B가 생성되었을 경우

Code, Data (BSS/Data), Heap 영역은 공유하고

 

각각 thread를 위한 Stack 영역을 별도로 가지고 있다.

 

 

 

 

- 멀티 프로세싱과 Thread

 

 

출처 : http://donghoson.tistory.com/15

 

 

* Multi Tasking (1 cpu & multi process)

single cpu 환경 & 멀티 프로세스가 있을 때 수시로 cpu의 실행을 바꿔주어서

사람의 관점에서 모든 프로세스가 동시에 실행되는 것처럼 보이게 된다.

 

* Multi Processing (multi cpu & multi process)

하나의 process를 여러 개의 cpu를 사용해서 실행 -> 실행 속도를 높임 

=> Thread를 여러 개 만들면 가능

또는

여러 개의 process를 여러 개의 cpu에 나누어서 실행 -> 실행 속도를 높임

(둘 다 병렬실행)

 

운영체제를 만들 때 정해볼 수 있는 구성

one process & one thread - 예전에 다루었던 batch system을 생각해보면 된다.

 

최근에 나오는 cpu는 멀티 코어를 가지기 때문에 복잡도는 조금 높다고 하더라도

마지막 multi process & multi thread와 같은 방식을 주로 채택한다.

 

 

 

 

 

 

 

 

 

운영체제 - 쓰레드의 이해 - 02. 스레드 장단점

운영체제 - 쓰레드의 이해 - 03. 스레드 동기화 문제

 

 

 

 

 

 

 

올인원 패키지 : 컴퓨터 공학 전공 필수👉https://bit.ly/3i4sCVE