어제의 나보다 성장한 오늘의 나

백준 1197번 문제는 MST( Minimum - Spanning -Tree )를 구하는 문제이다. 알고리듬으로 Union - Find 를 이용하여 구하면 간단하게 구할 수 있다. 문제 알고리듬 ① 입력 Edge들을 먼저 가중치 기준으로 오름차순 정렬 한다. - 정수 A,B,C 를 tuple 사용하여 묶어서 vector에 저장 - algorithm stl의 sort 함수 사용 (가중치 기준 정렬이므로 cmp 함수 추가) ② 정렬된 Edge들을 하나씩 꺼내며 싸이클이 생기는 지 확인 (Tree 이기 때문에 싸이클이 생기면 안됨) - 정렬된 edge들을 하나씩 꺼내며 정수 A,B의 find 값이 같은 지 확인 - 같다면 Union(A,B) 해주고 다르다면 무시 - 같을 때 Union 해주면서 그 edge의 ..

알고리듬 문제를 풀 때 시간이 굉장히 중요한데요 당연 시간 복잡도가 적게 드는 알고리듬을 선택하는 것이 관건이지요. 하지만 그 외에도 실행 시간을 줄여주는 꿀팁들이 있습니다. 이것 들을 습관화 해서 더 좋은 코드들로 발전 시켜 봅시다. ※ 참고 : C++에서의 팁입니다. 1) endl 대신 \n 사용 cout 을 해줄 때 다들 endl을 많이들 사용하시는데요. endl은 개행 문자 출력 + 버퍼 비우기 를 시행하기 때문에 시간이 더 많이 걸립니다. cout

우리는 가끔 엄청 큰 값 , 엄청 작은 값으로 특정 변수를 초기화 해야 할 때가 있다. 특히 알고리듬 공부를 할 때, Graph 나 Tree에서도 사용이 된다. C 언어로 , C++로 어떻게 해야 하는 지 각각 알아보자. 1) C언어 헤더 파일 #include Code int min = INT_MIN; // min int max = INT_MAX; // max 예제 #include #include int main(void){ int min = INT_MIN; int max = INT_MAX; printf("Min : %d\n", min); printf("Max : %d" , max); } 결과 2) C++ 헤더 파일 #include Code int min = std::numeric_limits::min(..

Red - Black Tree Binary search tree 중 하나인 AVL Tree 이다. Binary search tree -> 왼쪽 서브트리에는 루트 보다 작은 값이 , 오른쪽 서브트리에는 루트 보다 큰 값이 들어간다. AVL tree -> height가 2이상 차이나지 않는다. Red - Black tree는 이 두 가지 특징을 모두 가진다. Red - Black tree의 5 가지 특징 1) 모든 노드가 red or black 이다. 2) 모든 Leaf 노드는 black 이다. 3) 만약 노드가 red 이라면 Child 노드들은 black 이다. 4) 모든 노드 -> 자식 노드 중 Leaf 노드 경로의 black의 갯수가 같다. 5) 루트는 항상 black 위 다섯 가지 조건을 만족하면 R..

문자열 매칭 문제를 해결하는 Knuth-Morris-Pratt Algorithm 에 대해서 공부해보자. 문자열 매칭 문제란? 문자열에 주어진 패턴(특정 문자열)이 몇번 나타나는 지 찾는 문제 Knuth-Morris-Pratt Algorithm 소개 Text T = "bacbababaabcbab" Pattern P = "ababaca" 문자열 T에서 패턴 P를 찾는 과정에서 처음 index부터 차례로 비교하다가 이렇게 일부가 매칭 되다가 틀렸다면..! 일반 적인 매칭 방법에서는 패턴이 시작한 부분(ababa 의 맨 앞 a) 의 그 다음 부분 (ababa 의 앞에 있는 b) 에서 다시 매칭을 시작해야 한다. 이 것보다 더 효율 적으로 하는 방법은 없을까? 그러니까 어차피 b 부터 시작하면 패턴이 a 부터 시..

i-th order statistic 란?? i 번째로 작은 원소를 뜻한다. The Selection Problem 란?? i 번째 작은 원소를 찾는 것이다. 오늘은 세 가지 Selection Problem Algorithm에 대해서 배워 볼 것이다. Selection Problem Algorithm 3 가지 1) Naive Algorithm 2) Randomized Selection 3) Worst-Case Linear-Time Selection 1) Naive Algorithm 정렬 후 i 번째 작은 값을 고르는 방법 시간 복잡도 Θ(n lgn) merge sort + Pick i-th smallest element = Θ(n lgn) + Θ(1) = Θ(n lgn) 간단하지만 오래 걸린다. 2) R..

String matching problem 특정 Text에서 주어진 Pattern이 나타나는 모든 index를 구한다. 이 때의 index를 valid shift 라고 부른다. Valid shift Example 위 그림에서 Pattern P가 text T에서 index 3에서 나타난다. (s = 3 부분) 이 때 3은 valid shift 가 된다. (Index 0 , 1 , 2는 각각 abca , bcab , caba로 pattern이 나타나지 않는다. 그래서 Index 0 , 1, 2는 invalid shift) s = valid shift 일때 Text[s + i] = Pattern[i] 만족 valid shift를 모두 구하는 알고리즘 두 가지 1) Naïve - String - Matching..

Hardware support를 기반으로 한 Synchronization Problem을 해결법에 대해 알아보자 1) 싱글 코어 프로세서 인터럽트를 사용할 수 없게 끔 싱글 코어 프로세서를 사용하는 것이다. 그러면 Synchronization이 발생하지 않는다. 멀티 프로세스 시스템에서는 이 방식이 매우 비효율적이다. 확장되어 있는 OS들 에서는 이 방식을 채택하지 않는다. 2) Hardware Support 세 가지 ◎ Memory barriers ◎ Hardware instructions ◎ Atomic variables ① Memory barriers 오퍼레이션들의 순서를 보장해주는 장치 보통 store 오퍼레이션들 전후로 위치 한다 ◎ memory_Barrier를 설치함으로써 reorder방지 ◎..