06. 6차시 수업

01.cpp - 큐 queue

큐는 우리 주변에서 가장 쉽게 접할 수 있는 개념입니다. 먼저 들어간 데이터가 먼저 나가는 형태죠. 자세한 내용은 http://sunrinnote.tistory.com/38 여기에 있답니다~

#include <stdio.h>
int Queue[100000];
int d=-1, e=-1;
void enqueue(int n){
    if(n>=100000){
        printf("overflow\n");
        return;
    }
    Queue[++e]=n;
}
 
int dequeue(){
    if(d>=e){
        printf("underflow. return -1\n");
        return -1;
    }
    return Queue[++d];
}
 
int main(){
    while(1){
        int n;
        printf("1enqueue 2dequeue >> ");
        scanf("%d", &n);
        if(n==1){
            scanf("%d", &n);
            enqueue(n);
        }
        else{
            printf("%d\n", dequeue());
        }
    }
}

02.cpp - 이진트리 : 힙 ( heapify )

우선 트리의 값을 탐색하는 법을 알아봅시다.

배열 하나를 선언해줍시다. int tree[100000]; 그리고 편의상 1번의 인덱스부터 시작하며 i번째 인덱스에는 i의 값이 들어가있다고 가정합시다.

현재 1번을 보고 있다고 하겠습니다.

왼쪽 아래로 가려면 현재 값에 *2를 한 값, 오른쪽 아래로 가려면 현재 값에 *2+1 한 값으로 이동하면 됩니다.

거꾸로 올라갈때는 자료형이 int인 것을 이용하여 현재 값/2하면 됩니다.

힙 중 MAX-heap은 부모가 자식보다 항상 큰 힙을 말합니다.

heapify() 함수는 부모가 자식보다 작을 때, 자식 중 더 큰 자식과 swap해주는 함수입니다.

검사하는 곳이 사이즈를 넘어섰을 때, 혹은 모든 곳의 부모가 자식보다 클때 종료합니다.

위는 제 코드고 밑은 쌤코드입니다.

#include <stdio.h>
#include <algorithm>
using namespace std;
int size;
int heap[100000];//1부터 시작.
void heapify(int i){
    if(i>size) return;
    if(heap[i]>heap[i*2] && heap[i]>heap[i*2+1]) return;
    else if(heap[i*2] > heap[i*2+1]){
        swap(heap[i], heap[i*2]);
        heapify(i*2);
    }
    else if(heap[i*2] < heap[i*2+1]){
        swap(heap[i], heap[i*2+1]);
        heapify(i*2+1);
    }
}
int main(){
    printf("size : ");
    scanf("%d", &size);
    for(int i=0; i<size; ++i){
        scanf("%d", &heap[i+1]);
    }
    heapify(1);
    for(int i=0; i<size; ++i){
        printf("%d ", heap[i+1]);
    }
}

void max_heapify(int *tree, const unsigned int i, const unsigned int heap_size){
  int l = left(i);
  int r = right(i);
  int largest;
 
  if( l <= heap_size && tree[l] > tree[i] )
    largest = l;
  else
    largest = i;
  
  if( r <= heap_size && tree[r] > tree[largest])
    largest = r;
  
  if( largest != i ){
    swap(&tree[i], &tree[largest]);
    max_heapify(tree, largest, heap_size);
  }
}

03.cpp - Build_Max_heap : 힙만들기

02.cpp 에선 위에서부터 차례대로 내려갔다면, 이번엔 아래서부터 시작해서 위로 올라갑니다. 시작은 맨 끝의 데이터를 자식으로 갖고 있는 부모부터 시작합니다. 

#include <stdio.h>
#include <algorithm>
using namespace std;
int size;
int heap[100000];//1부터 시작.
void heapify(int i){
    if(heap[i]>heap[i*2] && heap[i]>heap[i*2+1]) return;
    else if(heap[i*2] > heap[i*2+1]){
        swap(heap[i], heap[i*2]);
        heapify(i*2);
    }
    else if(heap[i*2] < heap[i*2+1]){
        swap(heap[i], heap[i*2+1]);
        heapify(i*2+1);
    }
    return;
}
 
void Build_Max_heap(){
    for(int i=(size/2); i>=1; --i){
        heapify(i);
    }
    return;
}
 
int main(){
    printf("size : ");
    scanf("%d", &size);
    for(int i=0; i<size; ++i){
        scanf("%d", &heap[i+1]);
    }
    Build_Max_heap();
    for(int i=0; i<size; ++i){
        printf("%d ", heap[i+1]);
    }
}

04.cpp - 힙 정렬

Build_Max_heap을 이용해서 정렬하는 방법입니다.

구현은 쉽습니다. Build_Max_heap() 하면 가장 큰 것이 인덱스[1]번으로 오겠죠? 그걸 현재 사이즈에서 맨 뒤에 있는 값과 바꿔주고 사이즈를 하나씩 줄여나갑니다. 그러면 자동으로 큰게 뒤에서부터 정렬되겠죠?(오름차순)

위는 제소스고 밑은 쌤소스입니다.

#include <stdio.h>
#include <algorithm>
using namespace std;
int size;
int size_temp;
int heap[100000];//1부터 시작.
void heapify(int i){
    if(i>size) return;
    else if(heap[i]>heap[i*2] && heap[i]>heap[i*2+1]) return;
    else if(i*2>size) return;
    else if(i*2+1>size){ swap(heap[i], heap[i*2]); heapify(i*2); }
    else if(heap[i*2] > heap[i*2+1]){
        swap(heap[i], heap[i*2]);
        heapify(i*2);
    }
    else if(heap[i*2] < heap[i*2+1]){
        swap(heap[i], heap[i*2+1]);
        heapify(i*2+1);
    }
}
void Build_Max_heap(){
    for(int i=(size/2); i>=1; --i){
        heapify(i);
    }
    return;
}
 
int main(){
    int size_temp;
 
    printf("size : ");
    scanf("%d", &size);
    size_temp=size;
    for(int i=0; i<size; ++i){
        scanf("%d", &heap[i+1]);
    }
    Build_Max_heap();
    for(int i=1; i<=size_temp; ++i){
        swap(heap[1], heap[size]);
        --size;
        heapify(1);
    }
    swap(heap[1], heap[2]);
    for(int i=0; i<size_temp; ++i){
        printf("%d ", heap[i+1]);
    }
}

#include <stdio.h>
 
int parent(const unsigned int i){
  return i / 2;
}
 
int left(const unsigned int i){
  return 2 * i;
}
 
int right(const unsigned int i){
  return 2 * i + 1;
}
 
void swap(int *a, int *b){
  int tmp = *a;
  *a = *b;
  *b = tmp;
}
 
void max_heapify(int *tree, const unsigned int i, const unsigned int heap_size){
  int l = left(i);
  int r = right(i);
  int largest;
 
  if( l <= heap_size && tree[l] > tree[i] )
    largest = l;
  else
    largest = i;
  
  if( r <= heap_size && tree[r] > tree[largest])
    largest = r;
  
  if( largest != i ){
    swap(&tree[i], &tree[largest]);
    max_heapify(tree, largest, heap_size);
  }
}
 
void build_max_heap(int *tree, const unsigned int heap_size){
  int i;
  for(i = heap_size/2; i > 0; --i)
    max_heapify(tree, i, heap_size);
}
 
void heapsort(int *tree, unsigned int size){
  int i;
  build_max_heap(tree, size);
 
  for(i = size; i > 0; --i){
    swap(&tree[1], &tree[i]);
    max_heapify(tree, 1, --size);
  }
}
 
int main(){
  int i;
  int tree[] = {0, 5, 4, 3, 2, 1, 10, 9, 8, 7, 6};
 
  heapsort(tree, 10);
 
  for(i = 1; i < 11; i++){
    printf("%d ", tree[i]);
  }
 
}

05.cpp - Fenwick tree

구체적인 추가적인 설명은 안하도록 하겠습니다. 이 알고리즘 알아도 ps할때 외워서 못써먹을것같네요. 이런문제 나오면 틀리겠다는 마인드로 하겠습니다 ㅎ

아 물론 제 코드 아니고 쌤코드랍니다~

//Fenwick tree
/* https://www.acmicpc.net/problem/7578 */
 
#include <stdio.h>
#define MACHINES 500001
#define N 1000001
 
int up[MACHINES];
int down[MACHINES];
int temp[MACHINES];
int tree[N];
int hash[N];//hash[일련번호] = 1;, N=일련번호의 최대값.
 
int sum(int *tree, int i){ //sum : 1~i까지의 합.
  int ret = 0;
  while(i > 0){
    ret += tree[i];
    i -= (i & -i); //-비트연산을 이용합니다.흔히 보수라고 하죠. (~해서 +1한 값.)
  }
  return ret;
}
 
//update : 원소 하나가 오면(업데이트되면) 팬윅트리도 같이 업데이트 해줍니다.
void update(int *tree, int i, const int num, const unsigned int size){
  while(i <= size){
    tree[i] += num;
    i += (i & -i);
  }
}
 
int main(){
  int i, n;
  int ret = 0;
 
  scanf("%d", &n);
 
  for(i = 1; i <= n; ++i){
    scanf("%d", &up[i]);
    hash[up[i]] = i;
  }
 
  for(i = 1; i <= n; ++i){
    scanf("%d", &down[i]);
    update(tree, hash[down[i]], 1, N);
    ret += sum(tree, N) - sum(tree, hash[down[i]]);
  }
 
  printf("%d", ret);
 
}

그래도 예를 하나 들어보죠. 원래 배열의 1~13까지 구하고싶으면 

13 = 1101 (이진수) 이므로 이진수에서 맨 뒤에 있는 1을 지워주면서 더해주면 됩니다.

tree[1101] + tree[1100] + tree[1000] 같이요.

또, sum()을 잠깐 설명드리면 우선 i를 이진수로 바꿔서 생각합니다. i에서 가장 마지막으로 1이 나오는 순간을 생각해 봅시다.

예를 들면, 

3을 2진수로 바꾸면 11 이죠? 그럼 마지막 1은 2^0의자리수에 옵니다. (2의 0승자리수) 따라서 앞으로 2^0개가 tree[3]에 있는거죠.

4을 2진수로 바꾸면 100이죠? 그럼 마지막 1은 2^2자리수에 옵니다. 따라서 앞으로 2^2개가 tree[4]에 있는거죠.

6을 2진수로 바꾸면 110이죠? 그럼 마지막 1은 2^1자리수에 옵니다. 따라서 앞으로 2^1개가 tree[6]에 있는거죠.

새로운 값이 들어오면 update를 해줘야합니다. 값을 변경해줘야 하는 것은 해당 비트에서 맨 오른쪽에 있는 1을 기준으로 그곳에 +1을 해주면 됩니다.

예를 들면, 

13을 2진수로 바꾸면 1101입니다. 그럼 맨 오른쪽에 있는 1은 2^0자리수에 있으므로 그곳에 +1을 해주면 1110, 즉 14가 됩니다. 따라서 13에 값이 들어오면 첫째로 tree[13]에, 둘째로  tree[14]에 업데이트를 해주면 됩니다.

현재 1110에서 맨 오른쪽에 있는 1은 2^1자리수에 있습니다. 그곳에 +1을 해주면 10000, 즉 16이 됩니다. 따라서 tree[16]에도 값을 업데이트 해주면 됩니다.

만약 전체 길이가 16이라고 가정하면, 이진수 10000에서 같은 연산을 해주면 1000000, 즉 32가 되므로 사이즈를 초과합니다. 그만하면 됩니다.

그리고 코드 43, 44번째줄 보시면 입력 받자마자 업데이트에 넣어줍니다. 즉 처음 배열은 초기화된 상태에서 업데이트만으로 배열 값(트리배열도 같이)을 채워준다는거죠.

이 문제를 풀때는 hash 배열을 선언합니다. 첫번째(첫번째줄)로 입력받는 일련번호값에 몇번째로 들어왔는지 저장해주고, 두번째(두번째줄)로 입력받는 일련번호값에 그게 몇번째인지 hash배열에 쭉 입력받는 순서대로 저장합니다.

더이상은 안하겠습니다. 하지 마세요

(어째 갈수록 불친절해지는것같..)