Introduction Tarjan's algorithm is a popular algorithm for finding strongly connected components (SCCs) in a directed graph. A strongly connected component is a subset of vertices in a directed graph where every vertex is reachable from every other vertex in the subset. In other words, the vertices in an SCC are strongly connected to each other.The algorithm works by performing a depth-first sea..

Dynamic programming이란? 복잡한 문제를 여러 간단한 문제로 쪼개서 푸는 것 기본적으로 고등학교 때 학습하였던, 점화식을 활용하여 푸는 방법론이라고 이해해도 무방한다. 구현 방법 구현 방법은 크게 2가지가 있다. 반복분 장점 빠르고 메모리 측면에서 이득을 본다. DP 최적화 작용이 쉽다. (덱 DP, 세그 DP) 단점 테이블을 채우는 순서를 고려해야 한다. 순서가 복잡한 경우 사용하기 어렵다. (트리 DP, 비트 DP) 재귀 (Memoization을 사용) 장점 DP를 채우는 순서를 고려하지 않아도 되나, memoization을 사용하여 동일 반복 계산을 피한다. 순서가 복잡한 경우에도 처리하기 쉬움 (트리 DP, 비트 DP) 단점 반복문에 비해 느리고 메모리가 많이 든다. DP 최적화 작..

위의 STL 자료는 유명한 자료구조이므로 잘 학습해 두어야 한다. Deque 이 알고리즘을 활용하기 위해서는 상단에 반드시 #include 을 선언해야 한다. 이 자료구조의 특징은 stack의 특징과 queue의 특징을 섞었다는 것이다. 즉, LIFO(Last In First Out)이다. 즉, 나중에 들어온 것이 먼저 나가는 자료구조이다. Deque는 기본적으로 vector container와 매우 유사하나, vector보다는 앞과 뒤의 원소로 삽입이나 삭제가 빈번한 경우에 사용하는 것이 일반적이다. vector의 경우에는 뒤의 자료만 추가하고 삭제가 가능하다. 선언 방법은 "deque 변수이름"이다. 만약 선언하면서 초기화를 시키고 싶은 경우에는 사용방법은 다음과 같다. dq.push_front(va..

우선순위 큐 (Priority queue) 이 알고리즘을 활용하기 위해서는 반드시 #include 를 선언해야 한다. 컨셉자체는 Queue와 거의 유사하나 방식이 다르다. 다만, 나오는 순서가 우선순위를 부여하여 해당 우선순위에 해당하는 값이 먼저 pop한 값으로 나오게 된다. (기본적인 default자체는 가장 큰 값이 먼저 빠져나오게 된다.) 선언 방법은 "priority_queue 변수이름"이다. 자료형에는 int, double, class가 들어갈 수 있고, 구현체의 경우는 값을 어떠한 방식으로 저장할지를 설정해주는 것인데 기본적으로는는 vector이다. 비교연산자의 경우 일반적으로는 less을 사용하나 greater을 입력하게 되면 오름차순으로 우선순위큐가 정렬된다. 즉, 낮은 숫자가 우선순위가..

위의 STL 자료는 유명한 자료구조이므로 잘 학습해 두어야 한다. 1.Stack 이 알고리즘을 활용하기 위해서는 상단에 반드시 #include 을 선언해야 한다. 이 자료구조의 특징은 LIFO(Last In First Out)이다. 즉, 나중에 들어온 것이 먼저 나가는 자료구조이다. Stack을 사용하는 경우는 일반적으로 LIFO상황에 맞는 유형일 때 많이 사용된다. 물론 vector나 array를 활용해서 사용할 수도 있으나 컴파일 에러 등의 문제를 걱정하지 않아도 된다는 점에서 Stack STL을 사용하는 것이 유리하다. 선언 방법은 "stack 변수이름"이다. 사용방법은 다음과 같다. s.push(value) : 스택에 원소를 추가 s.pop() : 스택의 마지막 원소를 제거 (LIFO이므로 나가는..

위의 STL 자료구조는 매우 자주 쓰이는 형태이므로 잘 정리해 두어야 한다. Map 이 알고리즘을 활용하기 위해서는 상단에 반드시 #include 을 선언해야 한다. 이 자료구조의 경우는, vector나 배열과는 다르게 index를 활용하여 접근하는 것이 아니라 다른 자료형을 사용할 수 있는 것이다. 이 방법의 경우에는 검색, 삽입, 삭제 등의 속도가 빠른 편에 속한다. 선언 방법은 "map 변수이름"이다. Map을 사용해야 하는 경우는, 단순히 기존에 vector나 배열을 사용하는 방식처럼 index와 숫자를 매칭시킬 수 없는 상황이거나 연관있는 2개의 값을 매개하여 저장해야할 때 사용하게 된다. 사용방법은 다음과 같다. m.size() : m의 원소의 개수 m.empty() : m의 노드의 개수가 0..

이분탐색 (Binary search) 이분탐색은 결과적으로 나오는 index의 값을 기준으로 upper_bound와 lower_bound로 나뉜다. 단,이분탐색으로 접근하기 위해서는, 데이터가 연속적으로 이어져있어야 하기때문에 반드시 sorting을 하고 나서 진행해야 한다. 일반적으로 중복되는 수가 없는 경우 중간값이 compare하는 값보다 작을 때는, start부터 mid값까지의 값은 compare하는 값보다 무조건 작을 수 밖에 없으므로 판단해야하는 범위는 (mid + 1, end)로 이동하게 된다. 반면에, compare하는 값보다 클 때는, mid부터 end까지의 값은 compare하는 값보다 무조건 클 수 밖에 없으므로 판단해야하는 범위는 (start, mid -1)로 이동하게 된다. 만약,..

1. 사용법 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산할 수 있을 때 사용한다. 2. 구성요소 Divide: 커다란 상황을 작은 상황으로 구획한다. Conquer: 작은 상황에서의 정답을 토대로 커다란 상황에서의 답을 도출한다. Base case: 가장 기본적인 상황 (더이상 작은 상황으로 구획할 수 없는 경우를 설정해야 한다.) 3. 조건 문제를 부분 문제로 나눠 풀기가 수월해야 한다. 부분문제들의 답을 토대로 원래 문제의 답을 쉽게 도출할 수 있어야 한다. 4. 예시 1) 백준 1629번 곱셈 (거듭제곱에서의 활용) 만약 단순하게 A를 B번 곱하고 이를 C로 나누어 나머지를 구하는 방식으로 이 문..