Dobi coding

퀵 정렬(Quick-Sort)

- 퀵 정렬은 평균 수행시간이 O(n log n)으로 매우 효율적인 정렬이다.

- 최악의 경우에는 O(n^2)의 시간까지 걸리기도 한다.

동작원리

 - 배열의 가장 끝 원소를 키값으로 삼아 배열의 첫 원소부터 비교해 작은 범위와 큰범위로 나누어 나누어진 범위에 대해 다시 정렬을 하는 원리로 동작한다.

소스 

- partition 함수

1. /*
2.  퀵정렬을 하기위해 내부에서 재배치하는 함수
3.  기준값보다 큰값이오면 j 범위에 넣고 작으면 i 범위에 넣어 배치
4. */
5. int partition(int *arr,int a , int b)
6. {
7.     int x = (*(arr+b));
8.     int i = a-1;
9.     int j = 0;
10.     int temp = 0;
11.  
12.     for(j=a; j<b; j++)
13.     {
14.         if( (*(arr+j)) <= x) // j 부분의 값을 검사 기준값 보다 작을시 i 범위에 넣기위해 값을 교체
15.         {
16.             i = i+1;
17.             temp = (*(arr+i));
18.             (*(arr+i)) = (*(arr+j));
19.             (*(arr+j)) = temp;
20.         }
21.     }
22.  
23.     // 기준값을 j범위의 첫 요소와 교체
24.     temp = (*(arr+i+1));
25.     (*(arr+i+1)) = (*(arr+b));
26.     (*(arr+b)) = temp;
27.  
28.  
29.  
30.         return i+1; //교체한 기준값을 포함한 i 범위를 반환
31. }

- quicksort 함수

1. /*
2. 퀵 정렬하는 함수
3. */
4. void quicksort(int *arr,int a, int b)
5. {
6.     int q = 0;
7.  
8.     if(a<b)
9.     {
10.         q = partition(arr,a, b);
11.  
12.         quicksort(arr,a, q-1); // 기준값을 뺀 나머지 i 범위를 정렬
13.         quicksort(arr,q +1, b); // 기준값을 뺀 나머지 j 범위를 정렬
14.     }
15.  
16. }

결과

삽입 정렬 (Insertion-Sort)

- 삽입 정렬은 복잡도가 O(n^2)인 느린 알고리즘이다.

- 정렬 되지 않은 임의의 데이터를 이미 정렬된 부분의 적절한 위치에 삽입하며 정렬하는 알고리즘이다.

동작 원리

- 처음 배열의 두번째 원소를 키값으로 설정하고 자신의 앞부분 배열의 원소들과 비교해 자신의 자리를 찾는다

- 자신의 자리를 찾은 곳에 원소를 배치한다

- 다음 원소를 키값으로 앞부분의 배열의 원소들과 비교해 자신의 자리를 찾아나가 배열의 정렬을 한다.

소스 

1. #include<stdio.h>
2.  
3. int main(void)
4. {
5.     int arr[5] = {5,4,3,1,2};
6.     int key =   0;
7.     int temp =  1;
8.     int temp2 = 0;
9.     int dis =   0;
10.    
11.     for(;temp < 5; temp++)
12.     {
13.         key = arr[temp];
14.         temp2  = temp - 1;
15.  
16.         while(arr[temp2] > key && temp2 >=0)
17.         {
18.             arr[temp2+1] = arr[temp2];
19.             temp2 --;
20.         }
21.  
22.         arr[temp2+1] = key;
23.  
24.  
25.     }
26.  
27.     for(dis = 0; dis<5;dis++)
28.     {
29.         printf("%d ",arr[dis]);
30.     }      
31.     printf("\n");
32.  
33.     return 0;
34. }

결과 

1. 일차함수

    

    

1. 함수

   - 변수 : x, y 와 같이 여러 가지로 변하는 값을 나타내는 문자

   - 상수 : 일정한 값을 가지는 수나 문자

   - 함수 : 두 변수 x, y 에 대하여 x의 값이 정해짐에 따라 y의 값이 오직 하나로 정해질 때, y 는 x의 감수라 하고 기호로 y=f(x)

   - 함수값 : 함수 y=f(x)에서 x의 값에 따라 하나로 결정되는 y의 값을 x에서의 함숫값이라 하고 f(x)와 같이 나타냄

               y=f(x) 에서 f(a) 는 x=a 일 때의 함숫값 즉 y의 값이다

2. 수직선 위의 점의 좌표

    - 수직선 위의 한 점에 대응하는 수를 그 점의 좌표라고 한다.

    - 점 P의 좌표가 a일 때 기호 P(a)로 나타낸다.

3. 좌표평면 위의 점의 좌표

    1) 좌표 평면 : 두 수직선이 점 O에서 서로 수직으로 만날 때

       (1) 가로의 수직선을 x축, 세로의 수직선을 y축이라 하고, x축과 y축을 통틀어 좌표측이라 한다.

       (2) 두 좌표축의 교점 O를 원점이라 한다.

    2) 좌표평면 위의 점의 좌표

       (1) 두 수의 순서를 정하여 쌍으로 나타낸 것을 순서쌍이라 한다.

       (2) 좌표평면 위의 점 P의 x좌표가 a, y의 좌표가 b일 때 순서쌍 (a, b) 를 점 P의 좌표라 하고 기호 P(a, b)로 나타낸다

4. 사분면

    - 좌표축은 좌표평면을 네 부분으로 나누는데 그 각각을 제 1사분면, 2사분면, 3사분면, 4사분면이라고 한다.

5. 디칭인 점의 좌표

   - 점 (a,b)에 대하여

    (1) x축에 대하여 대칭인 점의 좌표 : (a, -b)

    (2) y축에 대하여 대칭인 점의 좌표 : (-a,b)

    (3) 원점에 대하여 대칭인 점의 좌표 : (-a, -b)

6. 함수의 그래프 

   함수 y=f(x)에서 각 x의 값을 x좌표로 하고 x의 값에 대한 함숫값 y를 y의 좌표로 하는 순서쌍 (x,y)를 모두 좌표위에 나타낸 것

7. 함수 y=ax(a!=0)의 그래프

   원점 (0,0)을 지나는 직선이다.

         [a > 0 일때]                         [a < 0 일때]

8. 함수 y = a/x(a!=0)의 그래프

    두 좌표축에 접근하면서 한없이 뻗어 나가는 한 쌍의 매끄러운 곡선이다.

         [a > 0 일때]               [a < 0 일때]

9. 함수의 식 구하기

  1) 그래프가 원점을 지나는 직선인 경우

    (1) 함수의 식을 y = ax로 놓는다.

    (2) 함수의 그래프가 점 (p,q)를 지날 때, y=ax에 x = p, y = q를 대입 하여 상수 a 값을 구한다.

  2) 그래프가 좌표축에 접근하면서 한없이 뻗어나가는 한 쌍의 매끄러운 곡선일 경우

    (1) 함수의 식을 y=a/x로 놓는다.

    (2) 함수의 그래프가 점 (p, q)를 지날 때, y = a/x에 x = p, y= q를 대입하여 상수 a의 값을 구한다.

10. 함수 y = ax의 활용

     - 변화하는 두 양을 변수로 x, y 로 놓고, x, y 가 서로 정비례하는지 알아본다.

     - 관계식을 y = ax 꼴로 나타낸다.

     - 함수의 식, 그래프, 표를 이용하여 문제에서 요구하는 답을 구한다.

11. 함수 y = a/x의 활용

     - 변화하는 두 양을 변수로 x, y 로 놓고, x, y 가 서로 반비례하는지 알아본다.

     - 관계식을 y = a/x 꼴로 나타낸다.

     - 함수의 식, 그래프, 표를 이용하여 문제에서 요구하는 답을 구한다.

1. 인수분해 

(1) 이차항의 계수로 양변을 나누어 이차항의 계수를 1로 만든다

(2) 상수항을 우면으로 이항한다

(3) 양변에 (x의계수 /2)² 을 더한다

(4) 좌변을 완전제곱식으로 정리한다

(5) 제곱근을 이용하여 방정식을 푼다

      

(1) b² - 4ac > 0 이면 서로 다른 두 근을 갖는다

(2) b² - 4ac = 0 이면 한 개의 근(중근)을 갖는다

(3) b² - 4ac < 0 이면 근이 없다 

1. 부등식

1. 미지수가 2개인 일차방정식 

   1) 미지수가 2개이고 차수가 모두 1인 방정식

      ax + by +c = 0 (a,b,c는 상수, a!=0,b!=0)

   2) 미지수가 2개인 일차방정식의 해

      미지수가 2개인 일차방정식을 만족하는 x, y의 값 또는 그 순서쌍 (x, y)

   3) 일차방정식을 푼다

2. 미지수가 2개인 연립일차방정식

   1) 미지수가 2개인 연립일차방정식

      미지수가 2개인 두 일차방정식을 한 쌍으로 묶어 놓은 것

   2) 미지수가 2개인 연립일차방정식의 해

      두 일차방정식을 동시에 만족하는 x, y의 값 또는 그 순서쌍 (x, y)

   3) 연립방정식 풀기

3. 연립방적식의 풀이 

   1) 가감법

     - 소거 : 미지수가 2개인 일차방정식에서 두 미지수 중 하나를 없애는 것

     - 가감법 : 연립방정식의 두 식을 변끼리 더하거나 빼어서 한 미지수를 소거하여 해를 구하는 방법

     - 가감법을 이용한 연립방정식의 풀이

       (1) 두 식에 적당한 수를 곱하여 소거하려는 미지수의 계수의 절댓값을 같게 만든다

       (2) 소거하려는 미지수의 계수의 부호가 같으면 빼고, 다르면 더해서 한 미지수를 소거한다

    2) 대입법

       - 대입법 : 연립방정식에서 한 미지수에 관한 식을 다른 방정식에 대입하여 해를 구하는 방법

       - 대입법을 이용한 연립방정식의 풀이

         (1) 한 방정식을 한 미지수에 관하여 푼다.

         (2) (1) 에서 정리한 식을 다른 방정식에 대입하여 한 미지수를 소거

4. 해가 특수한 연립방정식

   1) 해가 무수히 많은 연립방정식

      두 방정식을 변형하였을 때, 미지수의 계수와 상수항이 각각 같은 경우

   2) 해가 없는 연립방정식

      두 방정식을 변형하였을 때, 미지수의 계수는 각각 같고 상수항이 다른 경우

5. 연립방정식 활용

   1) 수의 문제

       두 자리의 자연수가 십의 자리 숫자x , 일의 자리 숫자 y 일 때

       (1) 처음 수 = 10x + y  , (2) 십의 자리와 일의자리 수를 바꾼 수 : 10y + x

   2) 나이에 관한 문제

       올해 x 살 일때

       (1) a년 전의 나이 : x - a,  (2) b년 후의 나이 : x + b

   3) 거리, 속력, 시간에 관한 문제

      (1) 거리 = 속력 x 시간  (2) 속력 = 거리/시간  (3) 시간 = 거리 / 속력

   4) 농도에 관한 문제

      (1) 소금물의 농도 = 소금양/소금물양 x 100  ,  (2) 소금양 = 소금물농도/100 x 소금물양

   5) 증가와 감소에 관한 문제

       증가하거나 감소하는 기준이 되는 시점을 미지수로 두는 것이 편리

        (1) x가 a% 증가했을 때

          증가량 : x * 1/100,  증가한 후의 양 : x * (1 + a/100)

        (2) x가 a% 감소했을 때

          감소량 : x * 1/100,  감소한 후의 양 : x * (1 - a/100)

1. 지수법칙 

1. 등식

    등호( = ) 를 사용하여 두 수 또는 두 식이 서로 같음을 나타낸 식

2. 방정식과 항등식

    - 방정식 : 미지수의 값에 따라 참이 되기도 것짓이 되기도 하는 등식

       1) 미지수 : 방정식에 있는 x, y등의 문자

       2) 방정식의 해(근) : 방정식을 참이 되게 하는 미지수의 값

       3) 방적식을 푼다 : 방정식의 해를 구한다

    - 항등식 : 미지수에 어떤 수를 대입해도 항상 참이 되는 등식

3. 등식의 성질

    1) 등식의 양번에 같은 수를 더하여도 등식은 성립

    2) 등식의 양변에서 같은 수를 빼어도 등식은 성립

    3) 등식의 양변에 같은 수를 곱하여도 등식은 성립

    4) 등식의 양변을 0이 아닌 같은 수로 나누어도 등식은 성립

4. 일차방정식

   - 이항 : 등식의 한 변에 있는 항을 부호를 바꾸어 다른 변으로 옮기는 것

   - 일차방정식 : 방정식의 우변의 모든 항을 좌변으로 이항하여 정리했을 때

                        (x에 관한 일차식) = 0, ax + b = 0 (a != 0)의 꼴로 변형되는 방정식

5. 일차방정식의 풀이

    1) x를 포함한 항은 좌변으로, 상수항은 우변으로 이항한다.

    2) 양변을 정리하여 ax = b (a!=0)의 꼴로 바꾼다.

    3) 양변을 x의 계수 a로 나누어 해 x = b/a 를 구한다.

    괄호가 있는 방정식인 경우 분배법칙을 이용하여 괄호를 풀고 일차방정식의 풀이에 따라 해를 구한다.

6. 비례식 형태로 주어진 방정식

   비례식의 성질을 이용하여 괄호가 있는 경우로 바꾼후 일차방정식의 풀이 방법에 따라 해를 구한다.

   a : b = c : d   ->   ad = bc

7. 계수에 소수가 있는 방정식인 경우

    양변에 10, 1000, 1000 ...의 10의 거듭제곱을 곱하여 계수를 정수로 고친 후 일차방정식의 풀이 방법에 따라 해를 구한다.

8. 계수에 분수가 있는 방정식인 경우

   양변에 분모의 최소공배수를 곱하여 계수를 정수로 고친후 일차방정식의 풀이 방법에 따라 해를 구한다.

9. 정가, 원가 문제

    정가 = (원가) + (이익) , 판매 금액 = (정가) - (할인 금액), 이익 = (판매금액) - (원가)

10. 거리, 속력, 시간 문제

    속력 = 거리/시간,  시간 = 거리/속력 , 거리 = 속력 * 시간

11. 농도 문제

     소금물 농도 = 소금의양/소금물의 양 *100,  소금의 양 = 소금물의 농도/100 * 소금물의 양