[CS50 4주차] 알고리즘

1. 검색 알고리즘

배열은 한 자료형의 여러 값들이 모여있는 구조. 배열 안에 있는 어떤 값을 찾기 위해서는 선형 검색, 이진 검색 등의 검색 알고리즘을 사용.

 

✔  선형 검색 : 배열의 인덱스를 처음부터 끝까지 하나하나 증가시키면서 방문하여 그 값이 속하는지 확인 (a to z)

✔  이진 검색 : 정렬된 배열이라면, 배열 중간 인덱스부터 시작하여 비교, 다시 중간 인덱스부터 비교를 반복

 

 

2. 알고리즘 표기법

[출처] 부스트코스 모두를 위한 컴퓨터 과학(CS50 2019)

Big O 표기법

✔  Big O 는 알고리즘 실행시간의 상한을 의미한다

✔  선형 검색에서는 n개의 항목이 있을 때, 최대 n번의 검색을 해야 하므로 상한이 Big O(n) 이 된다

✔  이진 검색은 (이미 정렬된 데이터의 경우) 선형 검색보다 빠르고, 1번 이상의 검색을 해야 하므로상한이 Big O(log n)이 된다

✔  Big O 표기법은 아래와 같이 사용되는데, 괄호 내부의 계산식은 실제 횟수를 구하는 공식이라기보다 대소 관계를 확인하기 위함

✔  Big O(n^2) > Big O(n log n) > Big O(n) > Big O(log n) > Big O(1)

 

Big Ω 표기법

✔  Big Ω 는 알고리즘 실행시간의 하한을 의미한다

✔  선형 검색에서는 n개의 항목이 있을 때, 최소 1번의 검색이 가능하므로 하한은 Big Ω(1) 이 된다

✔  이진 검색 또한 최소 1번의 검색이 가능하므로, 하한은 Big Ω(1) 이 된다

✔  Big Ω  표기법은 아래와 같이 사용되는데, 괄호 내부의 계산식은 실제 횟수를 구하는 공식이라기보다 대소 관계를 확인하기 위함

✔  Big Ω(n^2) > Big Ω(n log n) > Big Ω(n) > Big Ω(log n) > Big Ω(1)

 

3. 선형 검색

✔  배열의 인덱스를 처음부터 끝까지 하나하나 증가시키면서 방문하여 그 값이 속하는 지 확인 (a to z)

include <stdio.h>

int main(void){
//배열 내부에 5가 있는가?
  
  int arr[5] = { 1, 4, 3, 5, 2 };
  
  for(int i=0; i<5; i++){
 	 if(arr[i]==5){
  		printf("5가 있습니다");
	  	break;
 	 }
  }
  
  return 0;
}

 

4. 버블 정렬

✔  인접한 값 두개를 비교하며 위치를 교환하는 방법

✔  두 개의 값을 비교해 더 작은 값을 앞 순서로 바꾸고, 그다음 한 쌍을 비교하고 순서를 바꾸는 방법을 끝까지 진행

✔  값을 비교했을 때 더 이상 순서에 변화가 없다면 정렬 완료 

✔  int arr[8] = { 3, 6, 5, 2, 7, 4, 1, 8}을 버블 정렬로 정렬한다면 아래와 같은 순서로 정렬이 진행된다

 

3 6 5 2 7 4 1 8

3 6 5 2 7 4 1 8 (교환)

3 5 6 2 7 4 1 8 (교환)

3 5 2 6 7 4 1 8 

3 5 2 6 7 4 1 8 (교환)

3 5 2 6 4 7 1 8 (교환)

3 5 2 6 4 1 7 8

        ......

1 2 3 4 5 6 7 8

 

#include <stdio.h>

int main(void){
//배열에 저장된 숫자를 버블 정렬하자

  int arr[8] = { 3, 6, 5, 2, 7, 4, 1, 8 };
  int temp = 0;
  int check; //순서가 한 번도 바뀌지 않는 경우(check=0) 정렬을 멈추기위한 변수

  for(int i=0; i<8; i++){
    check = 0;
    for(int j=0; j<7; j++){ //index j+1을 비교해야하기때문에 j의 조건식이 j<7
      if (arr[j]>arr[j+1]){
        temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;
        check++; //순서 변경 시 check++
      } 
    }
    if(check==0) break;
  }
  for(int i=0; i<8; i++){
  	printf("%d\t",arr[i]);
  }
  return 0;
}

 

5. 선택 정렬

✔  방법1. 가장 작은 수를 찾아 가장 앞 순서의 숫자와 위치 교환을 반복하여 정렬

✔  방법2. 가장 큰 수를 찾아 가장 마지막 순서의 숫자와 위치 교환을 반복하여 정렬

#include <stdio.h>

int main(void){
//배열 내부에 저장된 숫자를 선택 정렬하자

  int arr[6] = { 3, 6, 5, 2, 1, 4};
  int min_index, min;
  
  for(int i=0; i<6; i++){
    min=arr[i];
    index=i;
    for(int j=i+1; j<6; j++){
      if(min>arr[j]){
          min=arr[j];
          min_index=j;
      }
    }
    arr[min_index]=arr[i];
    arr[i]=min;
  }
  
  //출력
  for(int i=0; i<6; i++){
    printf("%d\t",arr[i]);
  }
  
  return 0;
}

 

 

6. 정렬 알고리즘의 실행 시간

실행시간의 상한(Big O)

Big O(n^2)	버블정렬, 선택 정렬
Big O(n log n)	병합정렬
Big O(n)	선형검색	순서대로 검색하므로, 최대 n 번
Big O(log n)	이진검색	선형검색보다 빠르고, 1번 이상 검색하기 때문
Big O(1)

 

실행시간의 하한(Big Ω)

Big Ω(n^2)	버블정렬, 선택정렬	이미 정렬되어 있어도 다시 확인해야하기 때문
Big Ω(n log n)	병합정렬
Big Ω(n)	버블정렬	교환이 하나도 일어나지 않는 경우
Big Ω(log n)
Big Ω(1)	선형검색, 이진검색

 

실행시간 상한 = 하한 (Big Θ : Theta 표기법)

Big Θ(n^2)	선택정렬	실행시간의 상한과 하한이 모두 n^2
Big Θ(n log n)	병합정렬	실행시간의 상한과 하한이 모두 n log n
Big Θ(n)
Big Θ(log n)
Big Θ(1)

 

 

7. 재귀

✔  함수가 본인 스스로를 호출해서 사용하는 경우를 재귀라고 한다

✔  함수 내부에서 계속 함수를 호출하므로, stack 공간을 많이 차지해 스택 오버플로우가 발생할 수 있다 (5주차 참고)

✔  하지만 반복문보다 코드가 더 간결해 가독성이 높다는 장점이 있다.

 

#include <stdio.h>

void draw(int h);

int main(void){
    int height = 5;
    draw(height);
    return 0;
}

void draw(int h){
    if (h == 0) {return;} 	//재귀가 끝나는 조건
    draw(h - 1); 		// 높이가 h-1인 피라미드 그리기

    // 피라미드에서 폭이 h인 한 층 그리기
    for (int i = 0; i < h; i++){
        printf("*");
    }
    printf("\n");
}

 

 

8. 병합정렬 (합병 정렬)

✔  원소가 하나가 될 때까지 나누다가 다시 합쳐나가며 정렬하는 방식

#include <stdio.h>

int main(void){
	//추 후 업데이트!
    
	return 0;	
}

 

 

 

 

[출처] 부스트코스 | 모두를 위한 컴퓨터 과학(CS50 2019)