//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 번 탐색을 수행하면 메모리는 낭비하지만 같은 루틴으로 작업을 하여 코딩 실수를 방지 할 수 있다.

//Data Structure

//Binary Tree Traversal Pre-order, In-order, Post-order

#include <iostream>

#include <stdio.h>

#define MAX_M 26

using namespace std;

//adjacent list

char tree[MAX_M][2];

int tree_len[MAX_M];

void preorder_traverse(int node){

cout <<" "<< (char)(node + 'A');

if(tree_len[node] > 0) preorder_traverse(tree[node][0]);

if(tree_len[node] > 1) preorder_traverse(tree[node][1]);

}

void inorder_traverse(int node){

if(tree_len[node] > 0) inorder_traverse(tree[node][0]);

cout <<" "<< (char)(node + 'A');

if(tree_len[node] > 1) inorder_traverse(tree[node][1]);

}

void postorder_traverse(int node){

if(tree_len[node] > 0) postorder_traverse(tree[node][0]);

if(tree_len[node] > 1) postorder_traverse(tree[node][1]);

cout <<" "<< (char)(node + 'A');

}

int main(){

int T, test_case;

int N;

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

cin >> T;

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

//initialization

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

tree_len[i]=0;

}

//input

cin >> N;

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

char cp,cc;

cin >> cp >> cc;

tree[cp-'A'][tree_len[cp-'A']] = cc - 'A';

tree_len[cp - 'A']++;

if(tree_len[cp - 'A']>2){

cout << "OOPS!!" << endl;

}

}

cout << "adjacent tree" << endl;

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

if(tree_len[i]!=0){

cout << (char)(i+'A') << ":";

for(int j=0;j<tree_len[i];j++){

cout << " " << (char)(tree[i][j] + 'A');

}

cout << endl;

}

}

//pre-order traversal(binary tree only)

cout << "preorder_traverse : " << endl;

preorder_traverse(0);

cout << endl;

//in-order traversal(binary tree only)

cout << "inorder_traverse : " << endl;

inorder_traverse(0);

cout << endl;

//post-order traversal(binar tree only)

cout << "postorder_traverse : " << endl;

postorder_traverse(0);

cout << endl;

//DFS

//BSF

}

return 0;

}

시간을 들여야 한다.

시간을 들이지 않는 이유는 게을러서 일 수 도 있지만 아무래도 나의 경우에는

오히려 짧은 시간에 무언가 이루어야 한다는 불안과 조급함이 그 무엇도 시작하지 못하게

만드는 것 같다.

다행히 확실하게 무엇을 언제까지 마무리 해야한다는 것이 정해져 있을때는 집중 할 수도 있겠지만,

그렇게 단기적인 계획을 성취하는 것 만으로는 도약을 할 수는 없다.

시간을 들여 무엇을 하는 자체에 큰 의미가 있음을 잊지말아야 하며 실패나 더딘 진전도 과정이라는 점을 명심해야 한다.