일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |
- connected_component
- deletion
- template
- Heap
- 백준
- list
- '0'
- 문법
- c++
- class_template
- 구현
- Biconnected_Component
- singly Linked List
- 5397
- function_template
- qsort
- 알고리즘
- Algorithm
- 13305
- 자료구조
- 예제
- red-black tree
- sstream
- sort
- 총정리
- Pair
- Articulation_Point
- STL
- data_structure
- Critical_Path_Analysis
- Today
- Total
- Today
- Total
- 방명록
목록분류 전체보기 (85)
어제의 나보다 성장한 오늘의 나
알고리듬 문제를 풀 때 시간이 굉장히 중요한데요 당연 시간 복잡도가 적게 드는 알고리듬을 선택하는 것이 관건이지요. 하지만 그 외에도 실행 시간을 줄여주는 꿀팁들이 있습니다. 이것 들을 습관화 해서 더 좋은 코드들로 발전 시켜 봅시다. ※ 참고 : C++에서의 팁입니다. 1) endl 대신 \n 사용 cout 을 해줄 때 다들 endl을 많이들 사용하시는데요. endl은 개행 문자 출력 + 버퍼 비우기 를 시행하기 때문에 시간이 더 많이 걸립니다. cout
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/9P0to/btrF4exOmpB/f5L4Ti6Cy1Nm6Sa3U9UAfK/img.png)
우리는 가끔 엄청 큰 값 , 엄청 작은 값으로 특정 변수를 초기화 해야 할 때가 있다. 특히 알고리듬 공부를 할 때, 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(..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/bloZbp/btrEqhO9jIC/kEfqwnWnoiIrycNvTup8z1/img.jpg)
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..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/cvGdof/btrD5OIqL3o/3O29EqAUIrKXVu1h2M01fK/img.png)
문자열 매칭 문제를 해결하는 Knuth-Morris-Pratt Algorithm 에 대해서 공부해보자. 문자열 매칭 문제란? 문자열에 주어진 패턴(특정 문자열)이 몇번 나타나는 지 찾는 문제 Knuth-Morris-Pratt Algorithm 소개 Text T = "bacbababaabcbab" Pattern P = "ababaca" 문자열 T에서 패턴 P를 찾는 과정에서 처음 index부터 차례로 비교하다가 이렇게 일부가 매칭 되다가 틀렸다면..! 일반 적인 매칭 방법에서는 패턴이 시작한 부분(ababa 의 맨 앞 a) 의 그 다음 부분 (ababa 의 앞에 있는 b) 에서 다시 매칭을 시작해야 한다. 이 것보다 더 효율 적으로 하는 방법은 없을까? 그러니까 어차피 b 부터 시작하면 패턴이 a 부터 시..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/bpCVv4/btrD6yxBFA4/0Vrzmgh2iT25BqvfKummxK/img.png)
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..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/cvE9xk/btrD3SpNxkC/qP4oGfDgSvxwLuYAiOyCK1/img.png)
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..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/bZ1I5g/btrDj09YHfK/UHKwgx5HW6PC8gH3pTioSk/img.jpg)
Hardware support를 기반으로 한 Synchronization Problem을 해결법에 대해 알아보자 1) 싱글 코어 프로세서 인터럽트를 사용할 수 없게 끔 싱글 코어 프로세서를 사용하는 것이다. 그러면 Synchronization이 발생하지 않는다. 멀티 프로세스 시스템에서는 이 방식이 매우 비효율적이다. 확장되어 있는 OS들 에서는 이 방식을 채택하지 않는다. 2) Hardware Support 세 가지 ◎ Memory barriers ◎ Hardware instructions ◎ Atomic variables ① Memory barriers 오퍼레이션들의 순서를 보장해주는 장치 보통 store 오퍼레이션들 전후로 위치 한다 ◎ memory_Barrier를 설치함으로써 reorder방지 ◎..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/qDUIt/btrDi4xhHoW/YRUWcZkBbVmEMf0kOIFLL0/img.png)
Peterson’s Solution 두 개 이상의 프로세스의 동기화(Synchronization) 문제를 해결하는 방법 중 하나 ※ Critical-section problem 의 예전 버전 해결 방법이다. 예전 버전이므로 현대 버전에 적용되는 것이 보장 되지 않지만 알고리즘 자체가 동기화 문제 해결 방법 들의 기반이 된다. Peterson’s Solution Code variables int turn; boolean flag[2]; Turn 은 critical section에 들어갈 수 있는 프로세스를 나타내는 변수 Flag 는 critical section에 들어갈 준비 상태를 나타내는 변수 Algorithm // P_i 프로세스 의 알고리즘 while (true) { flag[i] = true; t..