Dobi coding

1. 너비우선탐색

   - 큐를 이용하여 깊이가 같은 노드를 모두 방문하고 깊이를 증가시키며 탐색하는 알고리즘이다.

2. 동작원리

   1) 지정한 시작 노드에서부터 시작

   2) 자식 노드들을 큐에 저장한다

   3) 큐에 저장된 노드를 차례로 방문하면서 방문한 노드의 자식들을 큐에 저장

   4) 큐에 있는 요소를 방문하면서 2) 3)의 과정을 반복

   5) 모든 노드를 방문하면 탐색을 종료

3. 소스

1. #include<stdio.h>
2.  
3.  
4. int front = -1;
5. int rear;
6.  
7. void inqueue(int *,int);  // 큐에 데이터를 삽입하는 연산
8. int dequeue(int *);  // 큐에서 데이터를 빼는 연산
9. int queueempty(); // 큐가 비어있는지 검사
10.  
11. int matrix[6][6] = {{0,1,1,0,0,0},
12.                     {1,0,1,1,0,0},
13.                     {1,1,0,1,1,0},
14.                     {0,1,1,0,1,1},
15.                     {0,0,1,1,0,0},
16.                     {0,0,0,1,0,0}};
17. int visit[6];
18.  
19.  
20. int main(void)
21. {
22.     int a=0;
23.     int b=0;
24.     int now = 0;
25.  
26.     int queue[40] = {0,};
27.  
28.     visit[0] = 1; // 처음방문할 정점
29.  
30.     inqueue(queue,0);
31.     printf("%d ",now);
32.  
33.  
34.     while(queueempty())
35.     {
36.         now = dequeue(queue); // 큐의 원소를 빼내 인접 노드를 찾는다
37.  
38.         if(visit[now] == 0)  // 인접노드중 방문하지 않은 노드를 찾기위해 vist배열을 검사
39.         {
40.             printf("%d ",now);
41.             visit[now] = 1;
42.         }
43.  
44.         for(a=0;a<6;a++) // 현재 노드의 인접 노드를 큐에 저장하기 위한 for문
45.         {
46.             if(matrix[now][a] == 1 && visit[a] == 0)
47.                     inqueue(queue,a);
48.         }
49.        
50.     }
51.     return 0;
52. }
53.  
54. int queueempty()
55. {
56.     if(front == rear)
57.         return 0;
58.     else
59.         return 1;
60. }
61.  
62. void inqueue(int *queue, int data)
63. {
64.     if(rear == 40)
65.         printf("큐가 꽉찾습니다.\n");
66.     else
67.         (*(queue + (rear++))) = data;
68. }
69.  
70. int dequeue(int * queue)
71. {
72.     int data;
73.  
74.         data = (*(queue+(++front)));   
75.         return data;
76.    
77.  
78. }

4. 결과

1. 대푯값과 평균 

   - 대푯값 : 자료 전체의 특징을 하나의 수로 나타낸 값

   - 평균 : 변량의 총합을 변량의 개수로 나눈 값,  (평균) = (변량의 총합) / (변량의 개수)

1. 사건과 경우의 수

   - 사건 : 실험이나 관찰에 의하여 일어나는 결과

   - 경우의 수 : 어떤 사건이 일어날 수 있는 모든 가짓수

2. 사건 a 또는 사건 b가 일어나는 경우의 수(합의법칙)

   - 두 사건 a, b가 동시에 일어나지 않을 때, 한 사건 a가 일어나는 경우의 수가 m가지이고, 다른 사건 b가 일어나는 경우의 수      가 n가지 이면 (사건 a또는 사건 b가 일어나는 경우의 수) = m + n (가지)

3. 사건 a또는 사건 b가 동시에 일어나는 경우의 수 (곱의 법칙)

   - 한사건 a가 일어나는 경우의 수가 m가지이고, 그 각각에 대하여 다른 사건 b가 일어나는 경우의 수가 n가지이면

     (사건 a와 사건 b가 동시에 일어나는 경우의 수) = m * n (가지)

4. 동전, 주사위를 던지는 경우의 수

   1) n개의 동전을 동시에 던질 때 일어나는 모든 경우의 수

      각각의 동전에 대하여 앞면, 뒷면의 2가지이므로 2ⁿ 가지 이다.

   2) n개의 주사위를 동시에 던질 때 일어나는 모든 경우의 수

      각각의 주사위에 대하여  1,2,3,4,5,6 의 6가지 이므로 6ⁿ 가지 이다.

   3) m개의 동전과 n개의 주사위를 동시에 던질 때 일어나는 모든 경우의 수

      두 사건이 동시에 일어나므로 2^m * 6^n 가지 이다.

5. 한 줄로 세우는 경우의 수

   1) n명을 한 줄로 세우는 경우의 수 

       n * (n-1) * (n - 2) * ... * 2 * 1 (가지)

   2) n명중 2명을 뽑아 한 줄로 세우는 경우의 수 

       n * (n-1)가지

6. 하 줄로 세울 때 이웃하여 세우는 경우의 수

   1) 이웃하는 것을 하나로 묶어 한 줄로 세우는 경우의 수를 구한다.

   2) 묶음 안에서 자리를 바꾸는 경우의 수를 곱한다.

7. 정수를 만드는 경우의 수

   1) 0이 아닌 서로 다른 한 자리 숫자가 각각 적힌 n장의 카드에서

       - 2장을 뽑아 두 자리의 정수를 만드는 경우의 수  >>>  n * (n-1)가지

       - 3장을 뽑아 세 자리의 정수를 만드는 경우의 수  >>>  n * (n-1) * (n-2) 가지

   2) 0이 포함된 서로 다른 한 자리 숫자가 각각 적힌 n장의 카드에서

       - 2장을 뽑아 두 자리의 정수를 만드는 경우의 수  >>>  (n-1) * (n-1)가지

       - 3장을 뽑아 세 자리의 정수를 만드는 경우의 수  >>>  (n-1) * (n-1) * (n-2) 가지

         (n장의 카드에 0이 포함된 경우, 정수의 맨 앞자리에는 0이 올 수 없음으로 맨 앞 자리에 올 수 있는 숫자는 0을 제외)

8. 대표를 뽑는 경우의 수 

    1) 자격이 다른 대표를 뽑는 경우

       - n명 중 자격이 다른 대표 2명을 뽑는 경우의 수  >>>  n * (n-1)가지

       - n명 중 자격이 다른 대표 3명을 뽑는 경우의 수  >>>  n * (n-1) * (n-2) 가지

    2) 자격이 같은 대표를 뽑는 경우

       - n명 중 자격이 같은 대표 2명을 뽑는 경우의 수  >>>  n*(n-1)/2 가지 

       - n명 중 자격이 같은 대표 3명을 뽑는 경우의 수  >>>  n * (n-1) * (n-2) / 3 * 2 * 1 가지

9. 확률의 뜻 

   - 어떤 실험이나 관찰에서 일어날 수 있는 모든 경우의 수가 n가지이고, 각 경우가 일어날 가능성이 같을 때, 어떤 사건 A가 일

     어나는 경우의 수가 a가지면 사건 A가 일어날 확률 p는

     p = (사건 A가 일어나는 경우의 수) / (모든 경우의 수) = a/n

10. 확률의 성질

    1) 확률의 범위

      - 어떤 사건이 일어날 확률을 p라 하면 0 ≤ p ≤ 1 이다 

      - 반드시 일어나는 사건의 확률은 1이다

      - 절대로 일어날 수 없는 사건의 확률은 0이다

    2) 어떤 사건이 일어나지 않을 확률

      - 사건 A가 일어날 확률을 p라 할 때, 사건 A가 일어나지 않을 확률은 1 - p이다

11. 사건 A 또는 사건 B가 일어날 확률(확률의 덧셈)

     사건 A와 사건 B가 동시에 일어나지 않을 때, 사건 A가 일어날 확률을 p, 사건 B가 일어날 확률을 q라 하면

      (사건 A 또는 사건 B가 일어날 확률) = p + q

12. 사건 A와 사건 B가 동시에 일어날 확률(확률의 곱셈)

     두 사건 A, B 가 서로 영향을 끼치지 않을 때, 사건 A가 일어날 확률을 p, 사건 B가 일어날 확률을 q라 하면

      (사건 A와 사건 B가 동시에 일어날 확률) = p * q

13. 연속하여 뽑는 경우의 확률

    1) 꺼낸 것을 다시 넣고 연속하여 뽑는 경우의 확률 

       - 처음 뽑을 때의 전체 개수와 다시 뽑을 때의 전체 개수가 같다.  >>>  처음 사건이 나중 사건에 영향을 주지 않는다 

    2) 꺼낸 것을 다시 넣지 않고 연속하여 뽑는 경우의 확률

       - 처음 뽑을 때의 전체 개수와 다시 뽑을 때의 전체 개수가 다르다  >>>  처음 사건이 나중 사건에 영향을 준다

14. 도형에서의 확률

    - 모든 경우의 수를 도형의 전체 넓이로, 어떤 사건이 일어나는 경우의 수를 사건에 해당하는 부분의 넓이로 생각하여 도형

      에서의 확률을 구할 수 있다.

      (도형에서의 확률) = (사건에 해당하는 부분의 넓이) / (도형의 전체 넓이)

1. 큐

   - 큐는 '줄을 서서 기다리다' 라는 뜻을 가지고 있다.

   - 큐는 선입선출 (FIFO : First In, First Out)원리의 자료구조이다.

   - 큐 구조는 컴퓨터 과학 전반에 자주 쓰이는 자료구이다. 예) 버퍼

2. queue 함수

   - void inqueue(int *,int);  // 큐에 데이터를 삽입하는 연산

   - int dequeue(int *);  // 큐에서 데이터를 빼는 연산

4. 결과화면 

1. 도수분포표

   1) 계급 : 변량을 일정한 간격으로 나눈 구간

      - 계급의 크기 : 구간의 너비 또는 계급의 양 끝값의 차

      - 계급의 개수 : 변량을 나눈 구간의 수

      - 계급값 : 계급을 대표하는 값으로 그 계급의 가운데 값

                 계급값 = (계급의 양 끝값의 합)/2

   2) 도수 : 각 계급에 속하는 자료의 개수

   3) 도수분포표 : 주어진 자료를 몇 개의 계급으로 나누고, 각 계급에 속하는 도수를 조사하여 나타낸 표

   4) 자료의 평균 : (변량의 총합) / (변량의 총 개수)

   5) 도수분포표에서의 평균 : ((계급값 x 도수)의 총합) / (도수)의 총합

2. 히스토그램

    - 도수분포표의 각 계급을 가로축에, 그 계급에 속하는 도수를 세로축에 표시하여 직사각형으로 나타낸 그래프

    - 히스토그램의 특징

      1) 도수분포표보다 자료의 분포 상태를 쉽게 알 수 있다.

      2) 각 직사각형의 넓이는 그 계급의 도수에 정비례한다.

      3) 직사각형의 넓이의 합 = 계급의 크기 x 도수의 총합

3. 도수분포다각형

    - 히스토그램에서 각 직사각형의 윗변의 가운데 점을 차례로 선분으로 연결하여 그린 다각형 모양의 그래프

    - 도수분포다각형의 특징

      1) 도수의 분포상태를 연속적으로 관찰할 수 있다.

      2) (도수분포다각형과 가로죽으로 둘러싸인 부분의 넓이) = (히스토그램의 각 직사각형의 넓이의 합)

      3) 2개 이상의 자료의 분포 상태를 한눈에 비교할 수 있다.

4. 상대도수

    - 각 계급의 도수가 전체 도수에서 차지하는 비율

      (어떤 계급의 상대도수) = (그 계급의 도수) / (전체 도수)

    - 상대도수의 특징

      1) 상대도수의 총합은 항상 1이다.

      2) 각 계급의 상대도수는 그 계급의 도수에 정비례한다.

      3) 전체 도수가 다른 두 집단의 분포 상태를 비교할 때 상대도수를 이용하면 편리하다.

5. 상대도수의 분포를 나타낸 그래프

    - 상대도수의 분포표를 히스토그램이나 도수분포다각형과 같은 모양으로 나타낸 그래프

    - 상대도수의 분포를 나타낸 그래프 그리기

      1) 가로축에 계급의 양 끝값, 세로축에 상대도수를 차례로 표시한다.

      2) 히스토그램이나 도수분포다각형과 같은 모양으로 그린다.

    - 활용

      1) 한 그래프에 나타내어 비교하면 한눈에 두 자료의 분포 상태를 쉽게 알 수 있다.

      2) 도수를 그대로 비교하지 않고 상대도수를 구하여 각 계급별로 비교한다.

1. 이차함수

1. 깊이 우선 탐색(DFS: Depth First Search)

2. 동작원리

  1) 정점 i 를 방문한다

  2) 정점 i에 인접한 정점 중에서 아직 방문하지 않은 정점이 있으면 이 정점들을 모두 스택에 저장

  3) 스택에서 정점을 삭제하여 새로운 i를 설정하고 단계1)을 수행

  4) 스택이 공백이 되면 연산을 종료한다

3. 소스

1. void DFS(int * arr, int now,int n) // arr : 스택배열, now : 처음 정점, n : 노드의 개수
2. {
3.     int a = 0;
4.    
5.     stackpush(arr,0); // 시작 노드를 스택에 push
6.  
7.     while(stackempty(top) != -1)
8.     {
9.         now = stackpop(arr);       
10.         if(visit[now] == 0)
11.         { // 아직 노드를 방문 하지 않음
12.             printf("%d ",now);
13.             visit[now] = 1;  // 방문했던 노드를 표시
14.             for(a=n;a>0;a--)
15.             {
16.                 if(visit[a] == 0 && matrix[now][a] == 1) // 인접한 노드중에 방문 안했던 노드를 push
17.                     stackpush(arr,a);
18.             }
19.         }
20.     }
21.     printf("\n");
22.  
23. }

4. 결과

1. 스택 

    - 후입선출(Last-In-First-Out(LIFO)) 원리의 자료구조이다.

    - 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형구조로 되어있다. 

2. stack 함수

   - int stackpop(int *) : 스택에서 top이 가리키는 요소를 꺼내는 함수

   - void stackpush(int *,int) : 스택에 요소를 삽입하는 함수

   - int stackempty(int) : 스택이 비어있는지 검사 하는 함수

   

1. 스택

   - 후입선출(Last-In-First-Out(LIFO)) 원리의 자료구조이다.

   - 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형구조로 되어있다. 

2. stack 함수

   - int stackpop(int *) : 스택에서 top이 가리키는 요소를 꺼내는 함수

   - void stackpush(int *,int) : 스택에 요소를 삽입하는 함수

   - int stackempty(int) : 스택이 비어있는지 검사 하는 함수

3. 소스 

1. #include<stdio.h>
2.  
3. int stackpop(int *);  // 스택에서 top이 가리키는 요소를 꺼내는 함수
4. void stackpush(int *,int);  // 스택에 요소를 삽입하는 함수
5. int stackempty(int);  // 스택이 비어있는지 검사 하는 함수
6.  
7. int top = -1;
8.  
9. int main(void)
10. {
11.     int arr[10] = {0,};
12.    
13.    
14.     stackpush(arr,10);
15.  
16.    
17.     printf("%d\n",stackpop(arr));
18.  
19.     stackpop(arr);
20.  
21.     return 0;
22. }
23.  
24. int stackpop(int *arr)
25. {
26.     int data = 0;
27.  
28.     if(stackempty(top) < 0)  // top 의 위치를 검사하고 스택이 비어있으면 NULL을 반환한다.
29.         return NULL;
30.     else    // top의 위치를 검사하고 데이터가있으면 스택의 가장 위의 데이터가 반환된다.
31.     {
32.         printf("pop -> ");
33.         data = (*(arr+(top--)));   
34.         return data;
35.     }
36. }
37.  
38. void stackpush(int * arr, int data) // 스택에 데이터를 삽입하는 함수
39. {
40.     printf("push -> %d\n",data);
41.     (*(arr+(++top))) = data;
42. }
43.  
44. int stackempty(int top)     // top위치를 검사해 스택의 상태를 반환한다.
45. {
46.     if(top < 0)
47.     {
48.         printf("Stack empty\n");
49.         return -1;
50.     }
51.     else
52.         return 1;
53. }

4. 결과

힙 정렬 (Heap-Sort)

- 힙 정렬의 수행시간은 O(n log n) 이다.

- 삽입 정렬과 같이 내부 정렬이다.( 정렬시 입력 배열의 원소를 초과해 배열 밖에 저장하는 일이 없다)

동작 원리

1. 최대(최소) 힙을 구성한다 

2. 루트에 위치한 수와 가장 작은 수를 교환

3. 교환한 수를 제외하고 힙 특성을 유지

4. 2-3의 과정 반복

소스

1. #include<stdio.h>
2.  
3. int * maxheapify(int *,int); // max heap 유지함수
4.  
5. int * buildmaxheap(int *, int); // heap 만들기 함수
6.  
7. int * heapsort(int *, int); // heap 정렬함수
8.  
9. int heapsize;
10.  
11. int main(void)
12. {
13.     int arr[10] = {69, 10, 30, 2, 16, 8, 31, 30, 35, 70 }; // 초기 입력 값
14.     int * heap;
15.     int a = 0;
16.  
17.     printf("변경전 : ");
18.     for(a= 0;a<10;a++)
19.     {
20.         printf("%d ",arr[a]);
21.     }
22.  
23.     heapsize = sizeof(arr)/sizeof(arr[0]);
24.  
25.     heap = heapsort(arr, heapsize);
26.    
27.    
28.  
29.     printf("\n변경후 : ");
30.     for(a= 0;a<10;a++)
31.     {
32.         printf("%d ",arr[a]);
33.     }
34.  
35.  
36.     return 0;
37. }
38.  
39. int * heapsort(int *arr, int size)
40. {
41.     int ch = 0;
42.     int a = 9;
43.     int temp = 0;
44.     int build = 3;
45.     arr = buildmaxheap(arr,size);
46.  
47.     for(;a > 1; a --) // 루트와 맨끝 노드의 값을 변경
48.     {
49.         temp = (*arr);
50.         (*arr) = (*(arr+a));
51.         (*(arr+a)) = temp;
52.  
53.         heapsize --;
54.  
55.         arr=    maxheapify(arr,0);
56.     }
57.    
58.     return arr;
59. }  
60.  
61. int * buildmaxheap(int * arr, int a)
62. {
63.     int b = a/2 -1;
64.  
65.     for(;b >= 0 ;b--)
66.     {
67.         maxheapify(arr,b);
68.     }
69.  
70.     return arr;
71. }
72.  
73. int * maxheapify(int  *arr, int a)
74. {
75.     int left = 0;
76.     int right = 0;
77.     int largest = 0;
78.     int temp =  0;
79.     int ch = 0;
80.  
81.     if(a == 0)
82.     {
83.         left = 1;
84.         right = 2;
85.     }
86.     else
87.     {
88.         left = a*2+1;
89.         right = a*2+2;
90.     }  
91.  
92.     if(left < heapsize && (*(arr+left)) >= (*(arr+a))) // 왼쪽 노드가 더 클때
93.         largest = left;
94.     else
95.         largest = a;    // 아니면 루트
96.  
97.     if(right < heapsize && (*(arr+right)) >= (*(arr+largest))) // 오른쪽 노드가 클때
98.         largest = right;
99.  
100.     if(largest != a) //더 큰값으로 루트를 교환한다.
101.     {
102.         temp = (*(arr+a));
103.         (*(arr+a)) = (*(arr+largest));
104.         (*(arr+largest)) = temp;
105.  
106.         maxheapify(arr,largest);
107.     }
108.  
109.     return arr;
110. }

결과