새싹교실/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

• 큐 구현은 안하고 C++ STL 쓸께요.

#include <stdio.h>
#include <queue>
using namespace std;

int N, M, V;

int Ver[1001][1001]={0};
int Ver1[1001][1001]={0};
int Already[1001];

queue<int> q;

void DFS(int Node);
void BFS();

int main() {
    int A, B, i;
    scanf("%d %d %d", &N, &M, &V);
    for(i=0;i<M;i++){
        scanf("%d %d", &A, &B);
        Ver[A][B]=1;
        Ver[B][A]=1;
        Ver1[A][B]=1;
        Ver1[B][A]=1;
    }
    DFS(V);
    printf("\n");
    for(i=1;i<=N;i++){
        Already[i]=0;
    }
    q.push(V);
    while(!q.empty()) {
        BFS();
    }
    return 0;
}

void DFS(int Node){
    int i;
    if(Already[Node]) return;
    printf("%d ", Node);
    Already[Node]=1;
    for(i=1;i<=N;i++){
        if(Ver[Node][i]){
            Ver[Node][i]=0;
            Ver[i][Node]=0;
            DFS(i);
        }
    }
}

void BFS(){
    int i;
    int Node = q.front();
    if(Already[Node]) {
        q.pop();
        return;
    }
    q.pop();
    printf("%d ", Node);
    Already[Node]=1;
    for(i=1;i<=N;i++){
        if(Ver1[Node][i]){
            Ver1[Node][i]=0;
            Ver1[i][Node]=0;
            q.push(i);
        }
    }
}

네트워크 연결

(코드를 여기에)

정석우

최대 힙

#include <stdio.h>
#include <stdlib.h>

#define left_child(x) (2*x)
#define right_child(x) (2*x+1)
#define parent(x) (x/2)

int heap[200001];
int index = 1;

void push(int target);
int pop();
void heap_maint(int cursor);
void heap_chk(int cursor);

void swap(int* a, int* b)
{
	int temp;
	temp = *a;
	*a = *b;
	*b = temp;
}

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

void push(int target)
{
	heap[index] = target;
	heap_maint(index);
	index++;
}

int pop()
{
	int foo;
	if (index == 1)
	{
		return 0;
	}
	foo = heap[1];
	heap[1] = heap[index - 1];
	heap[index - 1] = 0;
	heap_chk(1);
	index--;
	return foo;
}

void heap_maint(int cursor)
{
	if (cursor == 1)
	{
		return;
	}

	if (heap[cursor] > heap[parent(cursor)])
	{
		swap(&heap[cursor], &heap[parent(cursor)]);
	}
	heap_maint(parent(cursor));
}

void heap_chk(int cursor)
{
	if (cursor >= index)
	{
		return;
	}
	int max = heap[left_child(cursor)] > heap[right_child(cursor)] ? left_child(cursor) : right_child(cursor);
	if (heap[cursor] < heap[max])
	{
		swap(&heap[cursor], &heap[max]);
		heap_chk(max);
	}
}

DFS와 BFS

(코드를 여기에)

네트워크 연결

(코드를 여기에)