새싹교실/2017/따라와반/과제방/자료구조/6회차

오늘의 실습 내용

• 필수
  • 최대 힙
  • DFS와 BFS
  • 네트워크 연결
• 선택
  • 이진 탐색 트리
  • 집합의 표현
  • 오일러 회로
  • 연결 요소의 갯수

신원준

최대 힙

(코드를 여기에)

DFS와 BFS

(코드를 여기에)

네트워크 연결

(코드를 여기에)

이민욱

최대 힙

#include <stdio.h>

int Heap[200000];
int idx=1;

void push(int x);
int pop();
void balance(int now_idx);

int main() {
    int N, i, O;
    scanf("%d", &N);
    for(i=0;i<N;i++){
        scanf("%d", &O);
        if(O==0){
            printf("%d\n", pop());
        }
        else{
            push(O);
        }
    }
    return 0;
}

void push(int x){
    Heap[idx] = x;
    balance(idx);
    idx++;
}

int pop(){
    if(idx==1) return 0;
    int out = Heap[1];
    Heap[1] = Heap[idx-1];
    Heap[idx-1] = 0;
    balance_down(1);
    idx--;
    return out;
}

void balance(int now_idx){
    int tmp;
    if(now_idx==1) return;
    if(Heap[now_idx]>Heap[now_idx/2]){
        tmp = Heap[now_idx];
        Heap[now_idx] = Heap[now_idx/2];
        Heap[now_idx/2] = tmp;
    }
    balance(now_idx/2);
}

void balance_down(int now_idx){
    int tmp, max_idx;
    if(now_idx>=idx) return;
    max_idx = Heap[now_idx*2]>Heap[now_idx*2+1] ? now_idx*2 : now_idx*2 +1;
    if(Heap[now_idx]<Heap[max_idx]){
        tmp = Heap[now_idx];
        Heap[now_idx] = Heap[max_idx];
        Heap[max_idx] = tmp;
        balance_down(max_idx);
    }
}

DFS와 BFS

(코드를 여기에)

네트워크 연결

(코드를 여기에)

정석우

최대 힙

(코드를 여기에)

DFS와 BFS

(코드를 여기에)

네트워크 연결

(코드를 여기에)