#include <iostream>

#define MAX_N 1000

using namespace std;

//map의 0 에 사이즈를 저장한 인접배열

int map[MAX_N+1][MAX_N+1];

int visit[MAX_N+1];

void DFS_Recursive(int n){

    cout << " " << n;

    visit [n] = 1;

    for(int i=1;i<=map[n][0];i++){

        if(!visit[map[n][i]])

        DFS_Recursive(map[n][i]);

    }

}

int stack[MAX_N+1];

int stack_p =0 ;

void DFS_Stack(int v){

    stack[stack_p++] = v;

    while (stack_p > 0){

        v = stack[--stack_p];

        if(!visit[v]){

            cout << " " << v;

            visit[v] = 1;

            for(int w=1;w<=map[v][0];w++){

                if(!visit[map[v][w]])

                    stack[stack_p++] = map[v][w];

            }

        }

    }

}

int queue_p_begin = 0;

int queue_p_end = 0;

int queue[MAX_N+1];

void BFS_Queue(int v){

    queue_p_begin = 0;

    queue[queue_p_begin] = v;

    queue_p_end = 1;

    while (queue_p_begin < queue_p_end){

        v = queue[queue_p_begin++];

        if(!visit[v]){

            cout << " " << v;

            visit[v] = 1;

            for(int w=1;w<=map[v][0];w++){

                if(!visit[map[v][w]])

                    queue[queue_p_end++] = map[v][w];

            }

        }

    }

}

int main(){

    int T, test_case;

    int N;

    int src,dst;

    freopen ( "sample_input.txt", "r", stdin );

    cin >> T;

    for(test_case = 1; test_case <= T; test_case++){

        for(int i=0;i<=MAX_N; i++){

            map[i][0] = 0;

        }

        cin >> N;

        cout << "Graph" <<endl;

        for(int i=0;i<N;i++){

            cin >> src &\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0gt;> dst;

            map[src][0]++;

            map[src][map[src][0]] = dst;

            cout << src << " -> "<<dst << endl;

        }

        for(int i=0;i<=MAX_N; i++) visit[i] = 0;

        //BFS(Queue)

        cout << "BFS(Queue):";

        BFS_Queue(1);

        cout << endl;

        //DFS(Recursive)

        cout << "DFS(Recu.):";

        for(int i=0;i<=MAX_N; i++) visit[i] = 0;

        DFS_Recursive(1);

        cout << endl;

        //DFS(Stack)

        cout << "DFS(Stack):";

        for(int i=0;i<=MAX_N; i++) visit[i] = 0;

        stack_p =0;

        DFS_Stack(1);

        cout << endl;

        //Dijkstra

    }

    return 0;

}

#include <iostream>

#define MAX_N 1000

using namespace std;

//adjacent array version

//A의 0 에 사이즈를 저장한 인접배열

int A[MAX_N+1][MAX_N+1];

int maxNode;

int D[MAX_N+1]; // distance

int U[MAX_N+1]; // selected vertex set

int UN=0;

void dijkstra(int s){

    U[s] = 1;

    cout << (char)(s+'a') <<" ";

    UN++;

    //0 에서 해당 정점까지의 거리를 초기값으로 입력한다.

    for(int i=0;i<=maxNode;i++){

        D[i] = A[s][i];

    }

    while(UN<=maxNode){

        //이미 선택되지 않은 정점중 가장 가까운 것을 찾는다.

        int min = 1000;

        int minIdx ;

        for (int i=0;i<=maxNode;i++){

            if( i!=s && !U[i] && min > D[i] && D[i]!=-1){

                minIdx = i;

                min = D[i];

            }

        }

        U[minIdx] = 1;

        UN++;

        cout << (char)(minIdx + 'a') <<" ";

        if(UN>maxNode){ break;} //it is really needed??

        for(int i=0;i<=maxNode;i++){

            if(A[minIdx][i]!=-1){

                //i 로 바로갈까 아니면 다른데 들러서 갈까?

                D[i] = (D[i] !=-1 && (D[i] < (D[minIdx] + A[minIdx][i])))?D[i]:(D[minIdx] + A[minIdx][i]);

            }

        }

    }

    //for(int i=0;i<=maxNode;i++){

    //    if(U[i]==0){

    //        cout << (char)(i + 'a') ;

    //    }

    //}

    cout << endl;

}

int main(){

    int T, test_case;

    int N;

    char src,dst;

    int weight;

    freopen ( "sample_input.txt", "r", stdin );

    cin >> T;

    for(test_case = 1; test_case <= T; test_case++){

        for(int i=0;i<=MAX_N; i++){

            for (int j=0;j<=MAX_N;j++){

                if(i==j)

   \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0                 A[i][j] = 0;

                else

                    A[i][j] =-1; // dijkstra 는 - 값을 다루지 않는다.

            }

        }

        cin >> N;

        cout << "Graph" <<endl;

        maxNode =0;

        for(int i=0;i<N;i++){

            cin >> src >> dst >> weight;

            A[src-'a'][dst-'a'] = weight;

            if (src-'a'> maxNode){

                maxNode = src-'a';

            }

            if (dst-'a'> maxNode){

                maxNode = dst -'a';

            }

        }

        for(int i=0;i<=maxNode;i++){

        for(int j=0;j<=maxNode;j++)

            cout << A[i][j] <<" ";

        cout << endl;

        }

        //Aijkstra

        dijkstra(0);

    }

    return 0;

}

//String quick sort

#include <iostream>

#include <stdio.h>

#define MAX_N 6

#define SWAP(a, b) do { a ^= b; b ^= a; a ^= b; } while ( 0 )

using namespace std;

inline int my_strlen(const char* str){int n=0;for(n=0;str[n]!='\0';n++);return n;}

int my_strcmp(const char* str1, const char* str2){

    if(str1[0]=='\0'|| str2[0]=='\0') return str2[0] - str1[0];

    int diff=0;

    for(int n=0;str1[n]!='\0' && str2[n]!='\0';n++){

        diff = str2[n] - str1[n];

        if(diff!=0) return diff;

    }

    return diff;

}

int getLCP(const char* str1, const char* str2){

    int n;

    for(n=0;str1[n]!='\0' && str2[n]!='\0';n++){

        if(str2[n] - str1[n]) break;

    }

    return n;

}

//adjacent list

int N;

char str[MAX_N + 1];

int suffixArray[MAX_N + 1];

int LCP[MAX_N + 1];

void quick_sort(int first, int last){

    int pivot, j, temp, i;

    if(first < last){

        pivot = first;

        i = first;

        j = last;

        while ( i < j){

            while (my_strcmp((char*)(str + suffixArray[i]),(char*)(str + suffixArray[pivot])) >= 0 && i<last) i++;

            while (my_strcmp((char*)(str + suffixArray[j]),(char*)(str + suffixArray[pivot])) < 0) j--;

            if(i<j){

                temp = suffixArray[i];

                suffixArray[i] = suffixArray[j];

                suffixArray[j] = temp;

            }

        }

        temp = suffixArray[pivot];

        suffixArray[pivot] = suffixArray[j];

        suffixArray[j] = temp;

        quick_sort(first,j-1);

        quick_sort(j+1,last);

    }

}

void calculateLCP(){

    LCP[0] = 0;

    for(int i=1;i<=N;i++){

        LCP[i] = getLCP((char*)(str+suffixArray[i - 1]), (char*)(str+suffixArray[i]));

    }

}

int main(){

    int T, test_case;

    freopen ( "sample_input.txt", "r", stdin );

    cin >> T;

    for(test_case = 1; test_case <= T; test_case++){

        //initialization

        //input

       \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0; cin >> str;

        cout << "["<<str<<"]" << endl;

        N = my_strlen(str);

        str[N] = '$';

        str[N+1] = '\0';

        //print suffix

        cout << "1. Suffix list" << endl;

        for(int i=0;i<=N;i++){

            suffixArray[i] = i;

            cout << "\t" << (i + 1) << " " << (char*)(str+suffixArray[i]) << endl;

        }

        quick_sort(0,N);

        cout << "2. Suffix array" << endl;

        for(int i=0;i<=N;i++){

            cout << "\t" << (i + 1) << " " << (char*)(str+suffixArray[i]) << endl;

        }

        calculateLCP();

        cout << "3. Suffix array and LCP" << endl;

        for(int i=0;i<=N;i++){

            cout << "\t" << (i + 1) << " "<< LCP[i] <<" " << (char*)(str+suffixArray[i]) << endl;

        }

    }

    return 0;

}

Basic

- 상태공간 트리, Binary Search

Data Structure

- Tree 순회(Pre-order, In-order, Post-order)

String

- Suffix Array, LCP(Longest Common Prifix)

Graph

- BFS(Queue), DFS(Stack), Dijkstra, Fluid Warshall, KRUSKAL(Quick Sort)

Sort

- Quick Sort, Counting Sort

Tip.

- Map

- Bound check 는 별도 체크함수를 사용한다.

- 4방향을 배열에 넣고 상하좌우 넣고 반복문을 돌린다.

- Visit 여부는 맵자체에 값을 표기하여 갔던 곳을 다시 안가도록 처리한다. 돌아오면서 복원하게 되므로 다음번 시작할때는 문제가 발생하지 않는다. 물론, 변경, 복원 시점은 잘 생각해야한다.

- 2차원 배열의 행, 열을 탐색해야 할 때 transpose 하여 같은 방향으로 2 번 탐색을 수행하면 메모리는 낭비하지만 같은 루틴으로 작업을 하여 코딩 실수를 방지 할 수 있다.