yongmin

• selection sort
• insertion sort
• bubble sort

Selection Sort

• 제자리 정렬(in-place sorting) 알고리즘의 하나
  • 입력 배열(정렬되지 않은 값들) 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법
• 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘
  • 첫 번째 순서에는 첫 번째 위치에 가장 최솟값을 넣는다.
  • 두 번째 순서에는 두 번째 위치에 남은 값 중에서의 최솟값을 넣는다.
• 과정 설명
  1. 주어진 배열 중에서 최솟값을 찾는다.
  2. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
  3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
  4. 하나의 원소만 남을 때까지 위의 1~3 과정을 반복한다.
• time complexity
  • worst : O(n^2)
  • average : O(n^2)
  • best : O(n^2)

//selection sort

#include <iostream>
#include <vector>
using namespace std;

void selectionSort(vector<int>& arr);

int main() {

  vector<int> arr;
  arr.push_back(9);
  arr.push_back(6);
  arr.push_back(7);
  arr.push_back(3);
  arr.push_back(5);

  for(int n=0; n<arr.size(); n++){
    cout << arr[n] << " "; // 9 6 7 3 5
  }

  selectionSort(arr);
  cout << endl;
  
  for(int n=0; n<arr.size(); n++){
    cout << arr[n] << " "; // 3 5 6 7 9
  }
}

void selectionSort(vector<int>& arr){
  int min, minIdx, swap ;

  for(int i=0; i<arr.size(); i++){
    min = arr[i];

    for(int j=i+1; j<arr.size(); j++){
      if(min > arr[j]){
         min = arr[j];    
         minIdx = j;
      }
    }
    
    swap = arr[i];
    arr[i] = arr[minIdx];
    arr[minIdx] = swap;
  }
}

Insertion Sort

• 정의
  • 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘
• 과정 설명
  • 삽입 정렬은 두 번째 자료부터 시작하여 그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬
  • 즉, 두 번째 자료는 첫 번째 자료, 세 번째 자료는 두 번째와 첫 번째 자료, 네 번째 자료는 세 번째, 두 번째, 첫 번째 자료와 비교한 후 자료가 삽입될 위치를 찾는다. 자료가 삽입될 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 자료를 한 칸씩 뒤로 이동시킨다.
  • 처음 Key 값은 두 번째 자료부터 시작한다.
• time complexity
  • worst : O(n^2)
  • average : O(n^2)
  • best : O(n)

//insertion sort

#include <iostream>
#include <vector>
using namespace std;

void insertionSort(vector<int>& arr);

int main() {

  vector<int> arr;
  arr.push_back(9);
  arr.push_back(6);
  arr.push_back(7);
  arr.push_back(3);
  arr.push_back(5);

  for(int n=0; n<arr.size(); n++){
    cout << arr[n] << " "; // 9 6 7 3 5
  }

  insertionSort(arr);
  cout << endl;
  
  for(int n=0; n<arr.size(); n++){
    cout << arr[n] << " "; // 3 5 6 7 9
  }
}

void insertionSort(vector<int>& arr){
  int key, i , val;
  for(i=1; i<arr.size(); i++){
    key = i-1;
    while(key >= 0 && arr[key] > arr[i]){
      key--;
    }
    val = arr[i];
    arr.erase(arr.begin()+i);
    arr.insert(arr.begin()+key+1, val);
  }
}

Bubble Sort

• 정의
  • 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘
• 과정 설명
  • 버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, … 이런 식으로 (마지막-1) 번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다.
  • 1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 자료까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.
• time complexity
  • worst : O(n^2)
  • average : O(n^2)
  • best : O(n)

//bubble sort


#include <iostream>
#include <vector>
using namespace std;

void bubbleSort(vector<int>& arr);

int main() {

  vector<int> arr;
  arr.push_back(9);
  arr.push_back(6);
  arr.push_back(7);
  arr.push_back(3);
  arr.push_back(5);

  for(int n=0; n<arr.size(); n++){
    cout << arr[n] << " "; // 9 6 7 3 5
  }

  bubbleSort(arr);
  cout << endl;
  
  for(int n=0; n<arr.size(); n++){
    cout << arr[n] << " "; // 3 5 6 7 9
  }
}

void bubbleSort(vector<int>& arr){
  for(int i=arr.size(); i>=1; i--){
    for(int j=0; j<i-1; j++){
      if(arr[j+1] < arr[j]){
        int swap = arr[j+1];
        arr[j+1] = arr[j];
        arr[j] = swap;
      }
    }
  }
}

Dynamic Programming, 동적계획법

• DP란 어떤 문제가 여러 단계의 반복되는 부분 문제로 이루어질 때, 각 단계에 있는 부분 문제의 답을 기반으로 전체 문제의 답을 구하는 방법
• 분할정복은 문제를 위에서 아래로 쪼개지만 (top-down), DP는 작은 부분 문제부터 상위에 있는 문제로 풀어 올라간다(bottom-up).
• 분할정복의 쪼갠 문제는 완전히 독립적인 하나의 새로운 문제이지만, DP는 각 단계의 부분 문제들이 이전 단계에 있는 문제들의 답에 의존한다. => DP는 한번 푼 적이 있는 부분 문제의 답은 다시 푸는 일이 없도록 테이블에 저장하여 재활용
• 메모이제이션 (memoization) : 결과를 저장하는 장소를 마련해 두고, 한번 계산한 값을 저장해 뒀다 재활용하는 최적화 기법.
• 메모이제이션 구현 패턴
  1. 항상 기저 사례를 제일 먼저 처리하고 테이블에 저장
  2. 점진적으로 상위 부분 문제를 풀때 해당 답을 구한 적이 있으면 테이블에서 곧장 반환
  3. 구한적이 없으면 답을 계산하고 테이블에 저장
• 다이나믹 프로그래밍 동작 방식
  1. 문제를 부분 문제들로 나눈다
  2. 가장 작은 부분 문제(base case)부터 해를 구한 뒤 테이블에 저장한다
  3. 상위 부분 문제의 해를 구하는데 해당 답을 구한적이 있으면 테이블에서 곧장 반환
  4. 구한적이 없으면 답을 계산하고 테이블에 저장
  5. 위와 같이 테이블을 이용하여 점차적으로 상위 부분 문제의 최적해를 구한다.
• 타일링 문제 : boj.kr/11726
  • base case : n==1 -> return 1 ;
  • base case : n==2 -> return2 ;
  • 규칙을 찾아 점화식을 정의 D[n] = D[n-2] + D[n-1]

#include <iostream>
#include <vector>
using namespace std;

vector<int> D(1001);

int solve(int n);

int main() {
  int N=0;
  cin >> N;
  int res = solve(N);
  cout << res<< endl;
}

int solve(int n){
  if(n ==1 ){
    return 1;
  }
  if(n == 2){
    return 2;
  } 
  if(D[n]!=0){
    return D[n];
  }

  return D[n]= (solve(n-2)+solve(n-1)) % 10007;
}

Divide & Conquer

• 문제를 더 이상 나눌 수 없을 때까지 나누고, 이렇게 나누어진 문제들을 각각 풂으로써 결국 전체 문제의 답을 얻는 알고리즘
• 분할정복 알고리즘의 핵심은 "문제를 잘게 쪼개기", 하지만 문제를 쪼개는 방법에 대해서 정해진 규칙은 없다
• 분할정복의 3가지 구성요소
  1. divide : 문제를 더 작은 문제로 분할
  2. base case : 더 이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제
  3. merge : 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합
• 분할시 생기는 각 하위 문제는 완전히 독립접이므로 네트워크상의 여러 컴퓨터에 의해 병렬처리가 가능
• 예제 BOJ 1780 - 종이의 갯수 https://www.acmicpc.net/problem/1780

#include <iostream>
#include <vector>
using namespace std;

// 종이 갯수
int Zero =0;
int One = 0;
int MinOne =0;

// (r2-r1+1) x (c2-c1+1) 행렬
short check(vector< vector<short> >& arr, int r1, int r2, int c1, int c2){ 
  //종이가 모두 같은 수로 있는지 검사
  // 모두 같은 수 이면 해당 수 카운트, 하나라도 다르면 -2

  int size = r2-r1+1;
  short res = arr[r1][c1];

  for(int i=r1; i<=r2; i++){
    if( res == -2){
      break;
    }
    for(int j=c1; j<=c2; j++){
      if( res != arr[i][j]){
        res = -2;
        break;
      }
    }
  }

  if( res == -1)
      MinOne++;
  else if (res == 1)
      One++;
  else if( res == 0)
      Zero++;
  return res;
};

// 
void cut( vector< vector<short> >& arr, int r1, int r2, int c1, int c2){
  int size = r2-r1+1;
  
  // base case - 사이즈 확인
  if( size <3){  // 1x1 행렬 
    check(arr, r1, r2, c1, c2); // 해당 숫자 카운트
    return;
  }
  else{ // 3이상, 자를 수 있을정도로 크기 큼
  // 모두 같은 수 인지 check
    short arrSize = (size/3);
    short chk;
    // 11
      chk = check(arr, r1, (r1+arrSize-1), c1, (c1+arrSize-1));
      if(chk == -2)
        cut(arr, r1, (r1+arrSize-1), c1, (c1+arrSize-1));

    // 12
    chk = check(arr, (r1+arrSize), (r1+arrSize+arrSize-1), c1, (c1+arrSize-1));
    if(chk == -2)
      cut(arr, (r1+arrSize), (r1+arrSize+arrSize-1), c1, (c1+arrSize-1));

    //13 *
    chk = check( arr, (r1+arrSize+arrSize), r2, c1, (c1+arrSize-1));
    if(chk == -2)
     cut( arr, (r1+arrSize+arrSize), r2, c1, (c1+arrSize-1));

    // 21
    chk = check(arr, r1, (r1+arrSize-1), (c1+arrSize), (c1+arrSize+arrSize-1));
    if(chk == -2)
      cut(arr, r1, (r1+arrSize-1), (c1+arrSize), (c1+arrSize+arrSize-1));

    // 22
    chk = check(arr, (r1+arrSize), (r1+arrSize+arrSize-1), (c1+arrSize), (c1+arrSize+arrSize-1));
    if(chk == -2)
      cut(arr, (r1+arrSize), (r1+arrSize+arrSize-1), (c1+arrSize), (c1+arrSize+arrSize-1));

    // 23 *
    chk = check(arr, (r1+arrSize+arrSize), r2, (c1+arrSize), (c1+arrSize+arrSize-1) );
    if(chk == -2)
       cut(arr, (r1+arrSize+arrSize), r2, (c1+arrSize), (c1+arrSize+arrSize-1));

    // 31
    chk = check(arr, r1, (r1+arrSize-1), (c1+arrSize+arrSize), c2);
    if(chk == -2)
      cut(arr, r1, (r1+arrSize-1), (c1+arrSize+arrSize), c2);

    // 32
    chk = check(arr, (r1+arrSize), (r1+arrSize+arrSize-1),(c1+arrSize+arrSize), c2);
    if(chk == -2)
      cut(arr, (r1+arrSize), (r1+arrSize+arrSize-1),(c1+arrSize+arrSize), c2);

    // 33
    chk = check(arr, (r1+arrSize+arrSize), r2,(c1+arrSize+arrSize), c2);
    if(chk == -2)
      cut(arr, (r1+arrSize+arrSize), r2,(c1+arrSize+arrSize), c2);

  }

};

int main(){

  //배열 만들기
int N =0;
cin >> N;
vector<vector<short> > arr;
arr.resize(N);

for(int i=0; i<N; i++){
  for(int j=0; j<N; j++){
    short num;
    cin >> num;
    arr[i].push_back(num);
  }
}

short chk = check(arr, 0, (N-1), 0, (N-1));
if( chk == -2)
  cut(arr, 0, (N-1), 0, (N-1));

cout << MinOne <<endl;
cout << Zero << endl;
cout << One << endl;

return 0;
}