성장하고 싶은 신입 개발자

너비 우선 탐색 ( Breath First Search )

• 데이터를 탐색할 때 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘
• 현재 노드에서 가까운 것을 먼저 탐색하는 방식
• 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것

너비 우선 탐색 특징

• 재귀적으로 동작 X
• FIFO 원칙으로 탐색 ( Queue가 필요함 )
• 그래프 탐색 알고리즘은 방문한 노드를 꼭 방문 처리 해줘야 한다. ( 하지 않을 경우 무한 루프에 빠질 수 있음 )

너비 우선 탐색 장점과 단점

< 장점 >

• 출발노드에서 목표노드까지의 최단 길이 경로 보장

< 단점 >

• 경로가 매우 길 경우 탐색 가지가 급격히 증가함에 따라 보다 많은 저장 공간이 필요함
• 해가 존재하지 않는다면 유한 그래프의 경우 모든 그래프를 탐색한 후 실패로 끝남
• 무한 그래프의 경우 해가 없는 경우 해를 찾지도 못하고 끝내지도 못하게 됨

너비 우선 탐색을 사용하는 경우

• 두 노드 사이의 최단경로 즉, 최단 길이를 보장해야 할 때 많이 사용된다.
   ex) 미로 찾기 같은 문제를 풀 때 많이 사용된다.

너비 우선 탐색 ( BFS ) 동작 방식

BFS는 다음과 같은 간단한 방식으로 작동한다.

1. 큐에서 하나의 노드를 꺼낸다.

2. 해당 노드에 연결된 노드 중 방문하지 않은 노드를 방문하고, 차례대로 큐에 삽입한다.

-> 위의 1번과 2번을 계속해서 반복한다.

초기 상태

- 큐와 그래프를 준비

1. 

시작 노드(Start Node)를 큐에 삽입하면서 시작한다. 그리고 시작 노드를 '방문 처리' 해준다. ( 방문 처리 = 빨간색 )

2.

1. 시작 노드 1을 큐에서 꺼낸다.

2. 꺼낸 노드 1의 주변 노드인 2와 3이 모두 방문된 적이 없으므로 큐에 넣어준다.

3. 

1. 큐에서 2를 꺼낸다.

2. 꺼낸 이후 2와 인접한 노드 1,3,4,5 중에서 1과 3은 이미 방문한 적이 있으므로 패스하고 
   4와 5를 큐에 삽입한다.

4. 

1. 노드 3을 큐에서 꺼낸다.

2. 꺼낸 노드 3에 인접한 노드인 1,2,6,7 중에서 1과 2는 방문한 적이 있으므로 패스하고 
   6과 7만 큐에 삽입한다.

  => 위와 같이 모든 노드가 방문처리가 된 후에는 남은 노드들을 큐에서 꺼내주기만 하면 된다.

최종 상태

 차례대로 큐에서 꺼내면 위와 같다. 큐에서 꺼낸 순서를 보면 1,2,3,4,5,6,7이다.
 아무렇게나 막 탐색하는 것이 아니라 1부터 시작해서 '가까운 노드'들부터 탐색이 이루어진다는 점에서
 너비 우선 탐색이라고 한다. 거리가 먼 노드인 4,5,6,7은 가장 마지막에 탐색이 이루어지게 된다.

BFS 구현 코드

#include<iostream>
#include<queue>
#include<vector>

using namespace std;

int number = 7; // 노드의 갯수
int c[7]; // 방문처리를 위한 배열 생성
vector<int> a[8]; // 이차원 배열

void bfs(int start){
  queue<int> q;
  q.push(start);
  c[start] = true;
  while(!q.empty()){
    int x = q.front(); // 큐에서 제일 앞에 값을 저장
    q.pop(); // 큐에서 제일 앞에 값을 삭제
    printf("%d ",x);
    for(int i = 0; i < a[x].size(); i++){
      int y = a[x][i];
      if(!c[y]){ // 방문하지 않았으면
        q.push(y);
        c[y] = true;
      }
    }
  }
}

int main(){
  //1과 2를 연결
  a[1].push_back(2);
  a[2].push_back(1);
  
  //1과 3을 연결
  a[1].push_back(3);
  a[3].push_back(1);

  //2와 3을 연결
  a[2].push_back(3);
  a[3].push_back(2);

  //2와 4를 연결
  a[2].push_back(4);
  a[4].push_back(2);
  
  //2와 5를 연결
  a[2].push_back(5);
  a[5].push_back(2);

  //3과 6을 연결
  a[3].push_back(6);
  a[6].push_back(3);

  //3과 7을 연결
  a[3].push_back(7);
  a[7].push_back(3);

  //4와 5를 연결
  a[4].push_back(5);
  a[5].push_back(4);

  //6과 7을 연결
  a[6].push_back(7);
  a[7].push_back(6);

  //BFS를 수행
  bfs(1);
  
}

결론

• BFS는 너비를 우선으로 하여 탐색한다.
• BFS를 다른 알고리즘에 적용해 응용하는 것이 핵심이다. BFS 그 자체로는 그냥 탐색 알고리즘 중 하나일 뿐
  별 의미가 없다.

스택

- 제일 나중에 들어온 원소가 제일 먼저 나가는 구조 ( LIFO - Last In First Out )

- 알고리즘보다는 자료구조에 가까운 개념이다.

  -> 알고리즘은 이러한 스택이나 큐를 이용해서 문제를 해결하는 방법이다.

#include<iostream>
#include<stack>

using namespace std;

int main(){
  stack<int> s;
  s.push(7);
  s.push(5);
  s.push(4);
  s.pop();
  s.push(6);
  s.pop();

  while(!s.empty()){
    cout << s.top() << " ";
    s.pop();
  }
}

- STL 라이브러리 문법을 이용해 사용한다.

- 직접 구현해 볼 수 있지만 너무 간단하므로 생략하기로 한다.

큐

- 들어온 것이 먼저 나가는 구조 ( FIFO - First In First Out )

#include<iostream>
#include<queue>

using namespace std;

int main(){
  queue<int> q;
  q.push(7);
  q.push(5);
  q.push(4);
  q.pop();
  q.push(6);
  q.pop();

  while(!q.empty()){
    cout << q.front() << " ";
    q.pop();
  }
}

- STL 라이브러리 문법을 이용해 사용한다.

- 스택과 마찬가지로 직접 구현해 볼 수 있지만 너무 간단하므로 생략하기로 한다.

계수 정렬

• '범위 조건'이 있는 경우에 한해서 굉장히 빠른 알고리즘 -> 속도 : O(N)
• 단순하게 '크기를 기준'으로 세는 알고리즘

문제) 주어진 5 이하 자연수 데이터들을 오름차순 정렬하시오.
     1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1

• 크기를 기준으로 갯수만 세주면 되기 때문에 다른 정렬들처럼 위치를 바꿀 필요가 없다.
• 모든 데이터에 한 번씩만 접근하면 된다는 점에서 매우 효율적이다.

초기 상태

1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1

1. 첫번째 상태

1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1

2. 두번째 상태

1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1

3. 세번째 상태

1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1

4. 네번째 상태

1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1

5. 다섯번째 상태

1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1

.  .  . ( 위와 같이 계속 반복 )

최종 상태

1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1

- 이제 크기 1부터 5까지 해당 숫자만큼 순서대로 출력하면 된다. 

- 이게 바로 '크기를 기준'으로 정렬하는 계수정렬의 정렬 방법이다.

계수 정렬 구현 코드

#include<stdio.h>

int main(){
  int temp;
  int count[5] = {0,}; // 범위가 5이하이기 때문에 5개까지 들어갈 공간을 만들어줌
  int array[30] = {
    1,3,2,4,3,2,5,3,1,2,
    3,4,4,3,5,1,2,3,5,2,
    3,1,4,3,5,1,2,1,1,1
  };

  for(int i = 0; i < 30; i++){
    count[array[i] - 1]++;
  }

  for(int i = 0; i < 5; i++){
    if(count[i] != 0){
      for(int j = 0; j < count[i]; j++){
        printf("%d", i + 1);
      }
    }
  }
}

- count[]를 문제에 주어진 수의 범위만큼 생성해줘야 한다.

  만약 주어진 숫자 중에 10000이 있다면 count[]도 10000까지 잡아줘야 한다.
  그렇기 때문에 보통의 상황에 자주 쓸 수 있는 알고리즘은 아니다.
  -> 정렬할 데이터의 범위에 영향을 매우 크게 받는 정렬 알고리즘이다.

문제)

다솜이는 기타를 많이 가지고 있다. 그리고 각각의 기타는 모두 다른 시리얼 번호를 가지고 있다. 다솜이는 기타를 빨리 찾아서 빨리 사람들에게 연주해주기 위해서 기타를 시리얼 번호 순서대로 정렬하고자 한다.

모든 시리얼 번호는 알파벳 대문자 (A-Z)와 숫자 (0-9)로 이루어져 있다.

시리얼번호 A가 시리얼번호 B의 앞에 오는 경우는 다음과 같다.

1. A와 B의 길이가 다르면, 짧은 것이 먼저 온다.
2. 만약 서로 길이가 같다면, A의 모든 자리수의 합과 B의 모든 자리수의 합을 비교해서 작은 합을 가지는 것이 먼저온다. (숫자인 것만 더한다)
3. 만약 1,2번 둘 조건으로도 비교할 수 없으면, 사전순으로 비교한다. 숫자가 알파벳보다 사전순으로 작다.

시리얼이 주어졌을 때, 정렬해서 출력하는 프로그램을 작성하시오.

어려웠던 점)

- string 배열에 시리얼 번호들을 저장했는데 저장된 시리얼 번호에서 숫자일 때만 골라서 그 숫자들의 합을 구하는
  부분이 시간이 조금 걸렸다.

해결 방법)

- 문자는 아스키 코드이므로 문자가  '0' 과 '9' 사이일 때만 숫자이다. 그렇게 조건을 걸고 그 조건에 성립한다면
  숫자이기 때문에 그 값을 sum 변수에 더해준다. 이 때 string 변수의 안에 있는 숫자('9' 같은 문자)들을 더한 총합을
  구하려면 각 숫자에 해당하는 만큼 sum변수에 더해줘야 하는데 이 방법은 a[i] - '0' 으로 하면 아스키코드 값의 차이
  만큼이 그 숫자를 의미하게 되므로 이 값을 더해주면 된다.

1. 배열 색인의 유효성 체크

char str[8]; 

이 경우 str 배열의 범위를 벗어난 str[8]을 사용하여 값을 대입하면 어떤 일이 발생할까?
      
      [ 문법 오류가 아니다. ]
       - str[8]이라는 표현은 배열 문법이긴 하지만 메모리 주소를 표현하는 하나의 형식이기 때문에 
         컴파일러는 해당 주소에 대한 유효성 검사를 하지 않는다. 따라서 str[8]이 명백하게 str 배열의 범위를
         벗어났다고 해도 컴파일러는 이 명령문에 대해 오류 처리를 하지 않는다.

       - 이런 경우 오류 처리를 하지 않기 때문에 컴파일이 잘 된다. 하지만 프로그램의 메모리 할당 구조에 따라
         운 좋게 아무 문제 없이 동작하거나, 오류가 나서 프로그램이 중단되거나 혹은 오류는 발생하지 않지만
          원하는 결과가 나오지 않는 경우가 생길 수 있다.  -> 프로그램에 버그(Bug)가 생기게 된다

      [ 개발자가 직접 오류 처리를 해야 함 ]
       - if(index >= 0 && index <= 7) str[index]= '5'; 
       - c언어 컴파일러가 모든 상황에 대해 판단하지 못한다면 이런 식으로 개발자가 직접 색인에 대한 유효성을
         판단하는 것이 옳다.

2. 배열의 범위를 넘어서 사용한다면?

#include<stdio.h>

int main(){
    char str[10];
    fgets(str, 50, stdin); // 두번째 인자에 10을 사용해야 하지만 버그를 만들기 위해 50을 사용
    
    printf("input string : %s\n", str);
    return 0;
}

이 예제어서 사용된 str배열은 최대 9개의 문자열을 입력받아야 정상적으로 문자열을 처리할 수 있다.

[ 정상 수행 ]

[ Bug 발생 ]

- 사용자가 str배열의 범위를 초과하는 16개의 문자를 입력하면 이처럼 fgets와 printf는 정상 동작했지만
   이 프로그램은 문자열을 출력한 후 오류가 발생하며 중단되었다.
- 사실 처음 메모리를 초과하는 시점인 fgets() 함수에서 오류가 나야 하지만 해당 오류가 치명적인 종료 상황을
  만들지 않아서 운 좋게 진행된 것이다. 
   -> 이처럼 오류와 상관없는 지점인 프로그램의 마지막 부분에서 오류가 발생하기 때문에 오류를 찾는 입장에서
        이런 메모리 관련 버그는 더 찾기 어렵다.

3. 지역 변수들의 메모리 할당 방법

2번의 코드를 아래처럼 수정한다.

#include<stdio.h>

int main(){
    char str[10];
    char dummy[32] = {0,};
    fgets(str,50,stdin); // 2번째 인자에 10을 사용해야 하지만 버그를 만들기 위해 50 사용
    
    printf("input string : %s\n", str);
    return 0;
}

위 코드는 버그 상황이긴 하지만 더 이상 오류가 발생하지 않고 잘 동작한다.
-> 범위를 벗어나는 문자를 입력받아 str배열의 저장 범위를 초과하더라도 str 변수 아래에 선언된 dummy 배열에
     저장되어 정상적으로 동작하는 것처럼 보이는 것이다. 즉, 지역 변수들은 메모리에 순차적으로 나열되기 때문에
     str 변수의 영역을 넘어서게 되면 dummy 변수가 영향을 받게 된다.

[ 실행 결과 ]

실제 얼마나 초과되는지 확인 코드를 추가해서 확인해 보자.

#include<stdio.h>

int main(){
    char str[10];
    char dummy[32] = {0,};
    fgets(str, 50, stdin);
    
    printf("input string : %s\n", str);
    printf("dummy : %s\n", dummy);
    return 0;
}

[ 실행 결과 ]

[ printf가 정상적으로 문자열을 출력한 이유 ]

- printf함수의 %s 옵션은 사용자가 지정한 주소에서 시작하여 'NULL문자(\0)'가 나올 때까지 계속 문자를 출력하기
  때문에 str 배열의 범위를 벗어났는지는 체크하지 않는다.

 [ 결론 ]

  - 지역 변수로 선언된 배열은 다른 지역 변수 or 배열과 순차적으로 메모리에 나열되기 때문에 자신의 영역을 벗어나
    면 다른 지역 변수들에게 영향을 미치게 된다. 따라서 이런 문제가 발견되었는데 프로그램이 오류가 없이 동작
    한다고 해서 그냥 둔다면 나중에 버그로 고생하게 될 것이다.

힙정렬

• 시간복잡도가 O(nlogn)으로 퀵정렬, 병합정렬과 같은 시간복잡도를 가진 정렬 알고리즘
• 병합정렬과는 다르게 추가적인 메모리 필요 X
• 항상 O(nlogn)의 성능을 보여주기 때문에 최악의 경우 O(n^2)의 성능을 보이는
  퀵정렬보다 안정적인 성능을 보인다.
• 이론적으로는 퀵 정렬 병합 정렬보다 우위에 있지만, 단순히 속도만 가지고 본다면 퀵 정렬이
  평균적으로 더 빠르기 때문에 힙 정렬이 많이 사용되지는 않는다.
• 배열을 최대힙 or 최소힙으로 만들어 root에 있는 값을 정렬하는 식으로 구현한다.

힙(Heap)

• 완전이진트리 형태의 자료구조
• 힙은 최소힙과 최대힙 두가지로 나뉜다.
• 힙은 일반적인 배열로 표현할 수 있다.

  최대 힙 : "부모 노드 > 자식 노드"를 모든 노드에서 만족하는 완전이진트리 
  최소 힙 : "부모 노드 < 자식 노드"를 모든 노드에서 만족하는 완전이진트리

완전이진트리

 - 노드를 삽입할 때 왼쪽부터 차례대로 추가하는 이진트리 ( 모든 노드의 차수가 2 이하로 구성된 트리 )

완전이진트리(각 노드의 왼쪽부터 채워진 이진트리)	그냥 이진트리

힙을 일반적인 배열로 표현

 a = {-1,3,4,5,1,7,2,8}; 이라는 배열이 있다고 가정하자.
 a[1]을 루트노드로 잡고 힙트리를 완성하면 밑에 그림과 같다.

 i = 현재 노드의 인덱스

 ☞ 부모노드 = i / 2 (i > 0)

 ☞ 왼쪽 자식 노드     = i * 2

 ☞ 오른쪽 자식 노드  = i * 2 + 1

배열을 최대힙(or 최소힙)으로 만들어주는 힙 생성 알고리즘 ( heapify )
  - 힙 구조(최대힙 or 최소힙 구조)로 만들어 주기 위해 하나의 노드에 대해서 수행하는 알고리즘
  - 특정 노드의 두 자식 중에 더 큰 자식 <-> 자기 자신 스위칭
     ( 이 과정을 모든 노드에 대해서 반복 )

5 때문에 최대 힙 구조 X	heapify() 후 최대 힙 구조 O

  - 하나의 노드에 대해 한 번 heapify()를 수행하는데 걸리는 시간 : O(logN)
 
  - 전체 노드가 힙 구조를 다 만족하도록 만드는데 걸리는 시간 ( 제일 왼쪽 아래 노드부터 heapify() 시작 )
     ( == 트리에 있는 모든 노드에 대해 heapify()를 수행하는데 걸리는 시간 )
     => O(N * logN) ( 노드 개수 * 특정 노드에 대해 heapify() 1번 할 때 걸리는 시간 )

  - 실제로 전체를 힙 구조를 만족하도록 만드는데 걸리는 시간
        Ex)  이진탐색트리의 높이 : logN / 총 노드 갯수 : N
             - 실제로는 노드 갯수의 반만큼만 heapifiy()를 하면 되므로 ( 리프 노드들은 자식이 없기 때문에 할 필요 x )
                => N/2 * logN 이 된다.
                => N이 무한히 커진다면 N/2  >  logN라서 logN은 상수급으로 작아진다.
                => 그러므로 시간복잡도가 O(N * logN)이긴 하지만 logN이 상수급으로 작아지기 때문에 거의 O(N)에
                     가까운 속도를 낼 수 있다.

힙정렬의 원리

- 힙을 이용해 정렬을 하기 위해서는 이 힙을 최소힙이나 최대힙으로 만들어야 한다.
  힙이 최소힙 or 최대힙이 되었을 때 root는 항상 힙에서 최대값 or 최소값이 나오게 되어 있다.
  이 때 root를 힙의 마지막 노드와 교체한 뒤 힙의 마지막을 제외한 후 다시 최소힙이나 최대힙을
  만들어 준 후 root를 마지막 노드와 교체하는 방식으로 계속 반복한다. 

  힙 정렬 순서
  1) 정렬되지 않은 배열 생성

  2) 제일 처음에 이 배열을 최소힙 or 최대힙으로 구성 ( 모든 노드에 대해 힙 생성 알고리즘 heapify() 사용 )
  3) root <-> 마지막 노드 교체
  4) 마지막 노드를 제외한 상태로 다시 최소힙 or 최대힙 구성 ( root노드에 대해 다운힙 : O(logN) )
  5) 3 ~ 4번 반복

  => 최종적으로 힙정렬하는데 드는 시간
       => 처음 최대힙으로 만드는데 걸린 시간 + 스위칭한 후 root에 대해 다운힙하는데 걸리는 시간
            => O(N)  +  O(N * logN)
                 => O(N * logN)

힙 정렬 구현 코드

#include<stdio.h>
#include<iostream>

using namespace std;

int n = 7;
int heap[8] = {-100,1,9,5,4,7,2,8}; 

void heapify(int i){
  int parent = i;
  int child = i * 2;

  if(heap[child] < heap[child+1]) child++;

  if(heap[parent] < heap[child]){
    swap(heap[parent],heap[child]);
    if(child <= n / 2){
      heapify(child);
    }
  }
}

void heapSort(int i){
  int root = 1;
  int child = 2;
  swap(heap[root], heap[i]);

  //마지막 노드를 제외하고 최대힙으로 구성
  do{
    child = root * 2;
    if((heap[child] < heap[child + 1]) && (child < i - 1)){
      child++;
    } 

    if(heap[root] < heap[child] && child < i){
      swap(heap[root],heap[child]);
    }

    root = child;
  }while(child < i);
}

int main(){

  //처음에 최대 힙으로 만들기
  for(int i = n / 2; i >= 1; i--){
    heapify(i);
  }

  //힙 정렬 수행
  for(int i = n; i > 0; i--){
    heapSort(i);
    // printf("%d : ",i);
    // for(int j = 1; j <= n; j++){
    //   printf("%d ",heap[j]);
    // }
    // printf("\n");
  }


}

실제 알고리즘 대회에서 정렬 문제가 나올 때 빠르게 풀기 위해 sort()를 사용해 간단하게 정렬을 구현한다.

sort()

• <algorithm> 헤더에 정의되어 있다.
• default 설정  => 오름차순으로 정렬
• 퀵 정렬을 기반으로 구현되어 있다. 
• 퀵 정렬과 달리 모든 경우에 시간 복잡도 O(N * logN)을 보장한다.
• sort(start, end, 정렬기준);

사용 예시

1) sort(arr, arr + n);                                     

    => 세번째 인자를 안 쓰면 default로 오름차순 정렬됨

2) sort(v.begin(), v.end());

    => 세번째 인자를 안 쓰면 default로 오름차순 정렬됨

3) sort(v.begin(), v.end(), greater<자료형>());     

    => 내림차순으로 정렬

4) sort(arr, arr + n, compare);                         

    => 함수를 지정해서 세번째 인자로 넣으면 정렬할 기준을 내 마음대로 지정할 수 있음

일반 배열 정렬 

#include<iostream>
#include<algorithm>

using namespace std;

int main(){
  int a[10] = {9,3,5,4,1,10,8,6,7,2};
  sort(a, a+10);
  for(int i = 0; i < 10; i++){
    printf("%d ",a[i]);
  }
}

정렬 기준을 사용자가 직접 함수를 정의해서 정렬

#include<iostream>
#include<algorithm>

using namespace std;

bool compare(int a, int b){
  return a > b;   // a가 b보다 클 때 우선적으로 출력하도록 함 (내림차순)
}

int main(){
  int a[10] = {9,3,5,4,1,10,8,6,7,2};
  sort(a, a+10, compare);
  for(int i = 0; i < 10; i++){
    printf("%d ",a[i]);
  }
}

실무에서 실제로 sort()를 사용하는 경우

- 실무에서는 알고리즘 문제에서처럼 숫자만 나열되어 있는 데이터는 거의 없고
  데이터들이 객체화 되어 있는 경우가 많기 때문에 객체를 비교해서 정렬하는 경우가 많음

#include<iostream>
#include<algorithm>

using namespace std;

class Student{
public:
  string name;
  int score;
  Student(string name, int score){
    this->name = name;
    this->score = score; 
  }

  /*
  정렬 기준 : 점수가 작은 순서
  다른 학생(student)과 비교할 때 내 점수(this->score)가 더 낮다면 우선순위가 높다라는 뜻 
  => 점수가 작은 순서부터 출력하겠다는 말임
  */
  bool operator < (Student& student){
    return this->score < student.score;
  }

};

int main(){
  Student students[] = {
    Student("김일병", 90),
    Student("김이병", 93),
    Student("김상병", 97),
    Student("김사병", 87),
    Student("김오병", 92)
  };
  
  sort(students,students + 5); // 클래스 내에서 연산자 오버로딩으로 정렬 기준을 정해줌
                               // => 따로 세번째 인자에 값을 넣어주지 않아도 됨
  for(int i = 0; i < 5; i++){
    cout << students[i].name << " ";
  }
}

실제 알고리즘 문제에서 여러 개의 변수가 존재하는 상황에 "특정한 변수" 를 기준으로 정렬해야 할 때
실무에서처럼 클래스를 정의해서 푸는 방식은 빨리 풀어야 할 때는 유리하지 않다.

=> 일반적으로 빠른 코드 구현이 필요할 경우 페어(Pair) STL 라이브러리를 사용하는 것이 더 효율적이다.

pair STL 사용 예시

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(){
	vector<pair<int,string>> v;
	v.push_back(pair<int, string>(90,"김일병"));
	v.push_back(pair<int, string>(85,"김이병"));
	v.push_back(pair<int, string>(82,"김상병"));
	v.push_back(pair<int, string>(98,"김사병"));
	v.push_back(pair<int, string>(79,"김오병"));

	sort(v.begin(), v.end());
	for(int i = 0; i < v.size(); i++) {
		cout << v[i].second << " ";
	}
}

vector STL : 마치 배열과 같이 동작하는데, 배열을 보다 사용하기 쉽도록 개편한 자료구조

Pair STL    : 한 쌓의 데이터를 처리할 수 있도록 해주는 자료구조

변수가 3개일 때 "두 개" 의 변수를 기준으로 정렬해야 하는 경우

예를 들어 학생 이름을 기준에 맞게 정렬하는 상황이라고 가정하도록 하겠다.

학생 정보 : 이름, 성적, 생년월일

정렬 기준 : 학생의 이름을 성적 순서대로 나열 ( 단, 성적이 동일한 경우 나이가 더 어린 학생을 먼저 나열 )

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool compare(pair<string, pair<int,int>> a, pair<string,pair<int,int>> b){
  if(a.second.first == b.second.first){
    return a.second.second > b.second.second;
  }else{
    return a.second.first > b.second.first;
  }
}

int main(){
  vector<pair<string, pair<int, int>>> v;

  v.push_back(pair<string,pair<int, int>>("김일병", make_pair(90, 19961001)));
  v.push_back(pair<string,pair<int, int>>("김이병", make_pair(97, 19940505)));
  v.push_back(pair<string,pair<int, int>>("김상병", make_pair(95, 19940101)));
  v.push_back(pair<string,pair<int, int>>("김사병", make_pair(90, 19910909)));
  v.push_back(pair<string,pair<int, int>>("김오병", make_pair(88, 19850303)));

  sort(v.begin(), v.end(), compare);

  for(int i = 0; i < v.size(); i++){
    cout << v[i].first << " ";
  }
}

병합 정렬

- 분할 정복(Divide & Conquer) 방법을 사용하는 알고리즘

- 알고리즘을 구현함에 있어서 추가적인 임시 배열이 필요 ( 다른 정렬 알고리즘보다 메모리를 더 잡아먹음 )

시간 복잡도

O(N * logN) 

퀵 정렬 vs 병합 정렬

• 퀵 정렬은 최악의 경우 O(N * logN) 을 보장하지 못함 ( 최악의 경우 => O(N^2) )
• 병합 정렬은 최악의 경우에도 O(N * logN)을 보장함
• 둘 다 O(N*logN)만큼 걸리더라도 보통 병합 정렬보다 퀵 정렬이 더 빠름

병합 정렬의 동작 원리

1.  분할 ( 가장 작은 단위까지 분할 )   :   하나의 list를 두 개의 균등한 크기로 분할
2.  정렬 ( 가장 작은 단위부터 정렬 )   :   분할된 부분 list를 정렬

          =>  위 1,2 과정을 정렬이 완료될 때까지 반복 ( 재귀호출 )

분할된 부분 list를 정렬병합하는 과정

       (1) 각 요소의 첫번째 원소끼리 비교 시작

       (2) 비교한 후 작은 수를 임시 배열에 넣고 i++

       (3) 어느 한 쪽이 범위를 넘어가면 멈추고 남은 list의 값들을 뒤에 그대로 집어넣는다(정렬이 되어 있으므로)

병합정렬 알고리즘 구현

#include<iostream>
using namespace std;

int arr[10] = {1,3,5,7,9,2,4,6,8,10};
int* arr2;

void merge(int start, int end){
  int mid = (start + end) / 2;

  int i = start;
  int j = mid + 1;
  int temp = start;

  while(i <= mid && j <= end){
    if(arr[i] <= arr[j]){
      arr2[temp++] = arr[i++];
    }else{
      arr2[temp++] = arr[j++];
    }
  }

  int remain_idx = i > mid ? j : i;
  while(temp <= end){
    arr2[temp++] = arr[remain_idx++];
  }

  for(int i = start; i <= end; i++){
    arr[i] = arr2[i];
  }
}

void mergeSort(int start, int end){
  int mid;
  if(start < end){
    mid = (start + end) / 2;
    mergeSort(start,mid);
    mergeSort(mid+1,end);
    merge(start,end);
  }
}

int main(){
  arr2 = new int[10];
  mergeSort(0,9);

  for(int i = 0;i < 10; i++){
    printf("%d ",arr[i]);
  }

  delete[] arr2;
}

버블 정렬

- 바로 옆에 있는 값과 비교하면서 비교할 때마다 값을 스위칭하면서 이동

- 선택 정렬과 시간 복잡도는 같지만 실제 수행시간이 가장 느림
   => 버블 정렬 : 매번 비교할 때마다 값을 스위칭
   => 선택 정렬 : 전체 원소를 비교해서 최솟값을 찾은 후 가장 마지막에만 값을 스위칭

시간 복잡도

- O(N^2)

#include<stdio.h>
#include<iostream>

int main(){
  int data[] = {1,5,9,8,2,5,6,3,7,10};
  int i,j;

  for(i = 0; i < 10; i++){
    for(j = 0; j < 9 - i; j++){ //인덱스를 넘어가지 않도록 마지막 인덱스 전까지만 돔
      if(data[j] > data[j+1]) std::swap(data[j],data[j+1]);
    }
  }

  for(i=0;i<10;i++){
    printf("%d ",data[i]);
  }
}

삽입 정렬

• 적절한 위치에 삽입한다.
• 버블 정렬, 선택 정렬보다 빠르다.
• 삽입 정렬은 옆의 값과 비교해서 더 클 때만 스위칭하기 때문에 더 빠르다.

• 특정한 경우에 굉장히 빠르게 작용할 수 있다. ( 예 : 거의 정렬되어 있는 데이터일 때 )

시간 복잡도    =>    O(N^2)

동작 원리

- 특정한 위치에서 앞의 원소들과 비교해서 적당한 위치에 들어간다.

ex) 1 5 6 7 8 10 4 3 2 9   

     => 4가 적절한 위치에 들어갈 때 이미 앞 부분은 다 정렬이 되어 있기 때문에 4만 앞의 원소들과 하나씩
          비교해가며 들어가면 되기 때문에 매번 비교할 때마다 선택이나 버블처럼 교환하지 않아도 된다.
   

     1 5 6 7 8 4 10 3 2 9  ->  4와 8 비교해서 자리 바꿈
     1 5 6 7 4 8 10 3 2 9  ->  4와 7 비교해서 자리 바꿈
     1 5 6 4 7 8 10 3 2 9  ->  4와 6 비교해서 자리 바꿈
     1 5 4 6 7 8 10 3 2 9  ->  4와 5 비교해서 자리 바꿈
     1 4 5 6 7 8 10 3 2 9  ->  1과 4 비교해서 4가 더 크므로 여기서 정지 ( 멈출 때에 정지할 수 있다는게 장점 )
  

삽입 정렬 코드

#include<stdio.h>

int main(){
  int i,j,temp;
  int array[10]={1,10,5,8,6,5,4,3,2,9};
  for(i = 0;i < 9; i++){
    j = i;
    while(array[j] > array[j+1]){
      temp = array[j];
      array[j] =  array[j+1];
      array[j+1] = temp;
      j--;
    }
    printf("\n");
  }

}