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

오늘의 실습 내용

최단경로 선수과목 수 정렬하기 2 수 정렬하기 3

신원준

최단경로

(코드를 여기에)

선수과목

(코드를 여기에)

수 정렬하기 2

(코드를 여기에)

수 정렬하기 3

(코드를 여기에)

이민욱

최단경로

#include <stdio.h>
#include <vector>
#include <queue>

using namespace std;

int V, E, K;

int dist[20001];

queue<int> q;
vector<pair<int, int>> edge[20001]; //index : from, first : to, second: cost

int main(){
    scanf("%d %d", &V, &E);
    scanf("%d", &K);
    for(int i=1;i<=V;i++){
        dist[i] = -1;
        q.push(i);
    }
    dist[K] = 0;
    for(int i=0;i<E;i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        edge[u].push_back(make_pair(v, w));
        if(u == K){
            dist[v]= w;
        }
    }
    while(!q.empty()){
        int i = q.front();
        q.pop();
        int length = edge[i].size();
        for (int j = 0; j < length; j++) {
            if (dist[i] != -1) {
                if(dist[edge[i][j].first]==-1){
                    dist[edge[i][j].first] = dist[i]+edge[i][j].second;
                    q.push(edge[i][j].first);
                }
                if (dist[i] + edge[i][j].second < dist[edge[i][j].first]) {
                    dist[edge[i][j].first] = dist[i] + edge[i][j].second;
                    q.push(edge[i][j].first);
                }
            }
        }
    }

    for(int i=1;i<=V;i++){
        if(dist[i]==-1){
            printf("INF\n");
        }
        else{
            printf("%d\n", dist[i]);
        }
    }
    return 0;
}

선수과목

(코드를 여기에)

수 정렬하기 2

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


void MergeSort(int DataSet[], int StartIndex, int EndIndex);
void Merge(int DataSet[], int StartIndex, int MiddleIndex, int EndIndex);

int main(){
    int N;
    int Input[1000010];
    int i;
    scanf("%d", &N);
    for(i=0;i<N;i++){
        scanf("%d", &Input[i]);
    }
    MergeSort(Input, 0, N-1);
    for(i=0;i<N;i++){
        printf("%d\n", Input[i]);
    }
    return 0;
}

void MergeSort(int DataSet[], int StartIndex, int EndIndex){
    int MiddleIndex;
    if(EndIndex - StartIndex < 1)
        return;
    MiddleIndex = (StartIndex + EndIndex) / 2;
    MergeSort(DataSet, StartIndex, MiddleIndex);
    MergeSort(DataSet, MiddleIndex+1, EndIndex);

    Merge(DataSet, StartIndex, MiddleIndex, EndIndex);
}

void Merge(int DataSet[], int StartIndex, int MiddleIndex, int EndIndex){
    int i;
    int LeftIndex = StartIndex;
    int RightIndex = MiddleIndex + 1;
    int DestIndex = 0;

    int * Destination = (int*)malloc(sizeof(int)*(EndIndex- StartIndex +1));

    while(LeftIndex <= MiddleIndex && RightIndex <= EndIndex){
        if(DataSet[LeftIndex] < DataSet[RightIndex]){
            Destination[DestIndex] = DataSet[LeftIndex];
            LeftIndex++;
        }
        else{
            Destination[DestIndex] = DataSet[RightIndex];
            RightIndex++;
        }

        DestIndex++;
    }

    while(LeftIndex <= MiddleIndex)
        Destination[DestIndex++] = DataSet[LeftIndex++];

    while(RightIndex <= EndIndex)
        Destination[DestIndex++] = DataSet[RightIndex++];

    DestIndex = 0;
    for(i= StartIndex; i <= EndIndex ; i++){
        DataSet[i] = Destination[DestIndex++];
    }

    free(Destination);
}

수 정렬하기 3

#include <stdio.h>
int Number[10010];

int main(){
        int N, a;
        scanf("%d", &N);
        for(int i =0; i<N;i++){
                scanf("%d", &a);
                Number[a]++;
        }
        for(int i=0;i<10010;i++){
                for(int j=0;j<Number[i];j++){
                        printf("%d\n", i);
                }
        }
        return 0;
}

정석우

최단경로

(코드를 여기에)

선수과목

(코드를 여기에)

수 정렬하기 2

(코드를 여기에)

수 정렬하기 3

(코드를 여기에)