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;

}

시간을 들여야 한다.

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

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

만드는 것 같다.

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

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

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

KMP 부분을 좀 강조해서 적었으나 원래 PPT 와는 약간 달라짐.