솔

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

문제 1: 다이나믹 프로그래밍의 기본 개념 다이나믹 프로그래밍이 적용될 수 있는 문제의 두 가지 핵심 특성을 설명하고, 각각의 특성이 왜 중요한지 간략히 서술하시오.1. 중복되는 하위 문제 (Overlapping Subproblems):•설명: 문제를 해결하는 과정에서 동일한 하위 문제가 여러 번 반복하여 계산됩니다.•중요성: 중복 계산을 효율적으로 처리하기 위해 하위 문제의 결과를 저장(메모이제이션)하고 재사용할 수 있습니다. 이는 전체 문제의 시간 복잡도를 크게 줄여줍니다.2. 최적 부분 구조 (Optimal Substructure):•설명: 문제의 최적 해가 하위 문제들의 최적 해로부터 구성될 수 있습니다.•중요성: 최적 해를 구성하는 과정에서 하위 문제의 최적 해를 활용할 수 있으므로, 전체 문제..

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

이번에는 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/..

레드블랙 트리는 스스로 균형을 잡는 이진트리 라는 점에서  앞에서 살펴본 AVL과 비슷합니다.https://sol248.tistory.com/61 AVL TreeAVL트리는 발명자의 이름인 Geory Adelson-Velsky and Evgeii LanDis을 따서 지어졌습니다. 스스로 균형을 맞추는 이진 탐색 트리여서 self-balancing binary search tree 라고 부르기도 합니다.  이진 트리에서, 데sol248.tistory.com 또한, 레드블랙 트리는 실제로 키값을 2개 가지진 않지만 2-3트리의 성질도 가지고 있습니다.https://sol248.tistory.com/63 2-3Tree (2-3트리)다음에 알아볼 레드블랙트리를 더 쉽게 이해하기 위해, 2-3트리에 대해 먼저 알..

다음에 알아볼 레드블랙트리를 더 쉽게 이해하기 위해, 2-3트리에 대해 먼저 알아보겠습니다. 2-3트리는 이진트리의 확장 버전입니다. 이진트리에서는, 한 노드가 하나의 키값을 가지고 최대 두개의 자식을 가질 수 있었습니다. 하지만 2-3트리에서는 한 노드가 두개의 키값을 가질 수 있고, 세개의 자식을 가질 수 있습니다. 이진트리에서는 leftChild , rightChild 이렇게 두개의 자식이 있었다면 2-3트리에서는 leftChild , midChild , rightChild 이렇게 세개의 자식을 가질 수 있다고 생각하면 됩니다. 2-3트리는 이진 트리와 비교했을 때 무슨 장점이 있을까요?  먼저,데이터 삽입의 예시를 살펴보겠습니다. 1. 데이터를 삽입할 때 키 값이 2개 있는 노드가 일시적으로 3개..

https://sol248.tistory.com/61 AVL TreeAVL트리는 발명자의 이름인 Geory Adelson-Velsky and Evgeii LanDis을 따서 지어졌습니다. 스스로 균형을 맞추는 이진 탐색 트리여서 self-balancing binary search tree 라고 부르기도 합니다.  이진 트리에서, 데sol248.tistory.com이전에 AVL트리의 특징과 구현하는 방법에 대해 알아보았습니다. 이번에는 AVL트리를 활용하여 간단한 영어사전을 만들어보겠습니다. AVL트리는 알아서 균형을 맞춰주는 트리 형태이기에  삽입, 삭제, 탐색의 시간 복잡도가 최악의 경우에도 O(log N) 이라는 장점이 있었죠. 마침 영어사전은 빠른 삽입, 빠른 삭제, 빠른 탐색이 요구되므로 한번 구..

AVL트리는 발명자의 이름인 Geory Adelson-Velsky and Evgeii LanDis을 따서 지어졌습니다. 스스로 균형을 맞추는 이진 탐색 트리여서 self-balancing binary search tree 라고 부르기도 합니다.  이진 트리에서, 데이터가 마치 연결리스트처럼 한줄로 쭉 나열되는 최악의 경우 트리의 이점을 살리지 못한다는 단점이 있었습니다바로 아래의 그림처럼 말이죠.  이런 일이 발생하지 않기 위해서는 데이터를 추가할 때 한쪽으로 몰리지 않게 조절해주는 기능이 필요합니다. 이것을 가능하게 한 것이 바로 AVL 트리 입니다. 먼저 이진탐색트리의 코드부터 보겠습니다. 이진탐색트리 클래스)연습을 위해 동일한 기능을 하는 함수를 재귀를 사용한 것과 사용하지 않은 것 둘다 구현했습니..

버킷 정렬이란?bucket은 바구니를 의미합니다. 말 그래도 버킷 정렬은 바구니에 데이터를 담는 형태를 닮았다 하여 이름 붙여졌습니다.위 그림과 같이 숫자를 카테로리별로 나눠 바구니에 담은 뒤,그 바구니 안을 정렬해주는 방식입니다. 바구니 안을 정렬할 때는 앞에서 배웠던 정렬 방식 중 아무거나 사용하셔도 상관 없습니다. 저는 삽입 정렬을 이용해서 버킷 정렬을 구현해보았습니다.  코드)디버깅, 실행할 때 보기 편하도록 버킷을 출력해주는 함수를 추가해주었습니다.#include #include void Print(std::vector& v) { for (auto& a : v) { std::cout >& v) { for (int i = 0; i & v) { for (int i = 0; i = 0 &&..