솔

위상 정렬이란?위상 정렬은 그래프 알고리즘 중 DAG(Directed Acyclic Graph), 즉 방향성이 있으면서 싸이클이 없는 그래프에서 정점들을 순서대로 정렬하는 방법이다.  위상 정렬은 다음과 같은 상황에서 유용하다.- 작업 스케쥴링- 선수 과목에 대한 문제- 데이터 처리 파이프라인 위상 정렬의 조건위상 정렬을 사용하기 위해선 위에서 언급한 것처럼1. edge(간선) 에 방향이 있어야 한다.2. 비순환 그래프 즉, 싸이클이 없어야 한다. 이 두가지 조건을 만족해야 한다. 위상 정렬은 큐 기반 위상 정렬과 dfs 기반 위상 정렬로 나뉜다.두 방식에 대해 각각 알아보자.큐 기반 위상정렬큐 기반 위상정렬은 다음과 같은 단계를 따른다.1.각 정점의 진입 차수(inDegree)를 계산한다.2.진입 차수..

https://www.acmicpc.net/problem/1931  여러 시간대가 주어지고, 시간이 겹치지 않으면서 가능한 한 많은 회의실 사용 횟수를 구하려고 한다. 이를 구하기 위해서는, 가장 빨리 끝나는 회의를 찾고, 그 이후에 시작하는 회의 중 가장 빨리 끝나는 회의를 찾고, 이렇게 찾아나가면 될 것 같다. 위와 같이 회의 시간을 찾기 위해서는, 끝나는 시간을 기준으로 정렬되어 있어야 한다.  이를 위해 다음과 같은 구조체와 배열을 만들어 주고,이렇게 끝나는 시간을 기준으로 정렬해주는 cmp함수까지 완성해주면 준비는 끝났다.(끝나는 시간이 같은 경우 시작 시간을 기준으로 정렬)bool cmp(const t& a, const t& b) { if (a.eTime != b.eTime) return a..

8.1 Lower Bounds for Searching Only by Comparisons of Keys 이 섹션에서는 키 비교만을 사용하여 배열에서 특정 키를 검색할 때 소모되는 최악의 경우 비교 횟수의 하한을 다룹니다.특히, Binary Search와 Sequential Search의 의사결정 트리(Decision Tree)를 사용하여 검색 과정의 효율성을 분석합니다. 의사결정 트리 (Decision Tree) • 정의:의사결정 트리는 키 를 배열에서 검색하는 과정에서 발생하는 모든 비교를 나타냅니다. • 각 내부 노드는 키 비교를 나타냅니다. • 각 리프 노드는 검색 결과를 나타냅니다 (성공적으로 검색된 위치 또는 실패). • 예시: • Figure 8.1: 정렬된 배열에서 이진 탐색(Binary ..

7.1 Computational Complexity 계산 복잡도란?  • **계산 복잡도(Computational Complexity)**는 특정 문제를 해결할 수 있는 모든 가능한 알고리즘의 효율성을 분석하는 학문이다. • 주로 다음 두 가지를 분석한다:  1. 시간 복잡도(Time Complexity): 알고리즘이 실행되는 데 필요한 시간. 2. 공간 복잡도(Space Complexity): 알고리즘이 사용하는 메모리 양. 여기서 중요한 것은 알고리즘을 개별적으로 분석하는 것이 아니라 문제 자체의 본질적인 복잡도를 분석한다는 점이다.예를 들어, 행렬 곱셈 문제에서는 최선의 알고리즘이라도 Θ(n²) 이상의 시간 복잡도를 가지며,이를 문제의 **하한(Lower Bound)**이라고 한다. 정렬 문제의 계..

다이나믹 프로그래밍(DP)은 다음 두 가지 특성을 만족하는 문제에 적용할 수 있습니다:  1. 중복되는 하위 문제 (Overlapping Subproblems): 문제를 해결하는 과정에서 동일한 하위 문제가 여러 번 등장합니다. 2. 최적 부분 구조 (Optimal Substructure): 문제의 최적 해결 방법이 하위 문제의 최적 해결 방법으로부터 구성될 수 있습니다. DP는 이러한 특성을 이용하여 하위 문제의 결과를 저장하고, 이를 재사용함으로써 전체 문제를 효율적으로 해결합니다. DP의 접근 방식  • 메모이제이션 (Memoization): 재귀적으로 문제를 해결하면서, 이미 계산된 결과를 저장하여 다시 계산하지 않도록 하는 방법입니다. • 타뷸레이션 (Tabulation): 작은 하위 문제부터 ..

큰 수의 곱셈을 분할해서 푸는문제.

1. Write an algorithm that finds the largest number in a list (an array) of n numbers.int fintLargest(std::vector& v){ int largest = v[0]; for(int i=1; i largest) largest = v[i]; }} 2. Write an algorithm that finds the m smallest numbers in a list of n numbers.std::vector findSmallThanM(std::vector& v, int m){ std::sort(v.begin(), v,end()); std::vector result(v.begin(), v.begin()+m); retur..

이번에는 c++ 표준 라이브러리인 std::map, std::unordered_map 에 대해 알아보겠습니다. 라이브러리의 이름이 map 이라고 지어진 이유는 mapping 과 관련이 있기 때문입니다.  std::map (Ordered Map)map 은 BST (이진탐색트리) , RedBlackTree(레드블랙트리) 로 구현되어 있어서키의 순서가 자동으로 정렬되고O(log N) 을 기대할 수 있습니다. 또, 트리의 형태를 유지하기 위해 추가적인 메모리를 사용하지만 Unordered_mapd 에 비하면 적고,중복된 값은 허용하지 않습니다. ( 덮어쓰기 ) std::unordered_map (Unordered Map)unordered_map 은 해시테이블로 구현되어 있어서키의 순서가 정렬되지 않고평균적으로 ..

앞에서 AVL Tree와 RedBlackTree에 대해 알아보았는데요. 이번에는 두 트리를 비교해보겠습니다. https://sol248.tistory.com/61 AVL TreeAVL트리는 발명자의 이름인 Geory Adelson-Velsky and Evgeii LanDis을 따서 지어졌습니다. 스스로 균형을 맞추는 이진 탐색 트리여서 self-balancing binary search tree 라고 부르기도 합니다.  이진 트리에서, 데sol248.tistory.com https://sol248.tistory.com/64 RedBlackTree (레드-블랙 트리)레드블랙 트리는 스스로 균형을 잡는 이진트리 라는 점에서  앞에서 살펴본 AVL과 비슷합니다.https://sol248.tistory.com/..

https://sol248.tistory.com/50 MergeSort (병합 정렬)이번에는 병합 정렬에 대해 알아보겠습니다. 병합 정렬은 이전에 살펴봤던 Karatsuba algorithm 과 비슷하게, 데이터의 크기를 작게 쪼갠 후합치면서 정렬하는 방식입니다. Karatsuba algorithm이 궁금하sol248.tistory.comhttps://sol248.tistory.com/51 QuickSort (퀵정렬)이번에는 퀵정렬에 대해 알아보겠습니다. 퀵정렬은 배열을 두 부분으로 나누고 다시 합치는 과정에서 병합 정렬과 비슷한 면이 있지만,  배열을 절반으로 자르는 병합 정렬과는 달리 퀵정렬sol248.tistory.com  앞서 살펴본 퀵정렬과 병합정렬을 비교해보겠습니다. 먼저, 퀵정렬은 난수를 사..