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. 도형에서의 확률

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

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

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