알고리즘_부산코딩대회준비_01. 탐색 및 정렬

이번주 토요일에 있을 코딩대회를 준비하며,알고리즘 기본을 다시 보도록 한다. 

01. 탐색 및 정렬

02. DFS 및 BFS

03. DP 및 백트랙킹

04. 수학적 사고

순으로 진행해보려고 한다. 

 

1-1 탐색

 

우선 탐색에는 완전 탐색과 이분 탐색이 있다. 

 

 1) 완전 탐색

완전 탐색은 우리가 흔히 아는 처음부터 끝까지 다해보는 것이다. 

   1. for문을 이용한 방법

   2. 재귀를 이용한 방법

아마 간단하게 구현 가능하므로 넘어간다. 

 

 2) 이분 탐색 

 이분 탐색은 반으로 짤라서 탐색을 하는 것이다. 보통 정렬된 상태로 탐색을 진행한다. 정렬이 되어 있는 경우 O(logN)의 시간 복잡도를 가진다. 

 

 아래  binarySearch라는 배열에 10개의 숫자가 정렬되어 있다. 우리는 29를 찾으려고 한다. 그러면 처음 배열의 Index와 끝의 Index를 더하여 나누기 2를 해준다. 그러면 중앙값이 나온다. 아래의 중앙 값은 (0 + 9) / 2 = 4.5 소숫점 뒤에 값을 버리면 중앙 index값은 4로 중앙값은 11이 된다.

1

5

6

7

11

15

17

22

29

32

 그럼 11과 29를 비교해준다. 11보다 비교값이 크기 때문에 11 밑에 값은 다 버리고, 첫 인덱스를 중앙값 인덱스 + 1을 해준다. 

1

5

6

7

11

15

17

22

29

32

그럼 첫 인덱스는 4+1 = 5 이고 끝 인덱스는 9 이므로 (5 + 9) / 2 = 7이므로 binarySearch[7] = 22의 값과 29를 비교해준다. 29가 더 크기 때문에 index 값을 중앙값에서 +1 해준다. 

 

그럼 첫 index의 값은 8이고 끝 index 값은 9이다. 이를 통해 중앙값은 (8 + 9) / 2 = 8.5 이므로 임을 알 수 있다. binarySearch[8] = 29이므로, 우리가 비교하는 값을 찾았다.  이렇게 탐색이 끝나게 된다. 

 

// 
int binarySearch(vector<int>& binaryArr, int data) {
	//초기값은 start = 0 , end = 배열의 제일 마지막으로 설정 
	int start = 0, end = seq.size() - 1;
    while(end < start){
      // mid 값을 구해준다.	
      int mid = (start + end)/2;
      if(binaryArr[mid] == data){
      // 발견시 index 값을 반환
      	return mid;
      }else if(binaryArr[mid] < data){
      	// data 값이 더 크면 start 값을 이동
        start = mid + 1;
      }else{
      	// data 값이 더 크면 end 값을 이동
      	end = mid - 1;
      }
	}
	return -1;
}

1-2 정렬

• 버블 정렬
• 선택 정렬
• 삽입 정렬
• 병합 정렬
• 힙 정렬
• 퀵 정렬

 정렬에는 위에 6가지가 기본적인 정렬이라고 할 수 있다. 그 중 시간 복잡도가 O(n^2)가 나오는 버블, 선택, 삽입은 굳이 볼 필요가 없을 꺼 같고, O(nlogn)정도의 시간 복잡도를 가지는 정렬을 살펴보려고 한다. 그중 병합정렬을 살펴 보겠다.

 

 1) 병합 정렬

병합 정렬은 분할 정복의 대표적인 문제이다. 분할 정복은 전체 문제를 분할하여 풀 수 있을 만큼 작은 문제로 분할한 다음, 작은 문제를 각각 풀어 얻은 답들을 토대로 전체 문제의 답을 구하는 알고리즘 이다.  전체 문제를 분할하여 푼다는 것이 동적 계획법과 유사하다고 할 수 있으나 분할 정복은 작은 문제로 나눌 때 문제가 겹치지 않게 나눈다는 차이점을 가진다. 

 분할 정복은 분할 -> 문제 해결 -> 결합 의 과정을 거친다. 

 

 아래는 분할 정복 법의 예로 a^n을 구하는 예이다.

// ex1 a = 2, n = 4
// ex2 a = 2, n = 2
// ex3 a = 2, n = 1
int pow(int a, int n){
	if(n == 0) return 1;
    //ex3 return a = 2;
	if(n == 1) return a;
	
	int res;
    // ex1 4 % 2 = 0
    // ex2 2 % 2 = 0
	if(n % 2)
		res = a * pow(a, n - 1);
	else{
    // ex1 res = pow(2, 4 / 2);
    // ex2 res = pow(2, 2 / 2);
		res = pow(a, n / 2);
        // ex2 res = 2;
        // ex1 res = 2^2;
		res *= res;
        // ex2 res = 2^2;
        // ex1 res = 2^4;
	}
	return res;
}

병합정렬의 '분할' 과정

병합정렬의 '합병' 과정

 

저런식으로 하나씩 까지 분할한 다음 다시 합병해준다. 그 과정중에 sorting이 필요한다. 코드를 통해 sorting 과정을 보도록 하자. 분할 과정의 함수와 병합 과정의 함수가 필요하다 우선 분할을 해주는 함수 부터 생성하도록 하자. 

 

void mergeSort(int merge[], int left, int right){
 int mid;
 
 
 if(left < right){
  mid = (left + right)/2;
  
  mergeSort(merge, left, mid-1);
  mergeSort(merge, mid, right);
  mergeSort(merge, left, mid, right);
 }
 
}

 다음은 병합해주는 과정이다. 

void merge(int merge[], int left, int mid, int right){

   int i, j, k;

   i = left;
   j = mid +1;
   k = left;

   int temp[allindex]; 

   while(i <= mid || j <= right ){
      if(merge[i] < merge[j]){
          temp[k] = merge[i];
          i++;
      }else{
          temp[k] = merge[j];
          j++;
      }
      k++;
   }

   if(i > mid){
      while(k > right){
          temp[k++] = merge[j++];
      }else{
          temp[k++] = merge[i++];
      }	
  }

  for(int i = 0; i <= right; i++){
      merge[i] = temp[i];
  }

}