솔

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

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

버킷 정렬이란?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 &&..

https://sol248.tistory.com/51 QuickSort (퀵정렬)이번에는 퀵정렬에 대해 알아보겠습니다. 퀵정렬은 배열을 두 부분으로 나누고 다시 합치는 과정에서 병합 정렬과 비슷한 면이 있지만,  배열을 절반으로 자르는 병합 정렬과는 달리 퀵정렬sol248.tistory.com퀵정렬은 중복된 값이 많을수록 느리다는 단점이 있기 때문에 앞에서는 중복된 값이 없다는 가정을 하고 진행했습니다. 이것을 극복할 수 있는 방법이 3-way partitioning 입니다. 앞에서는 pivot 값보다 작은것과 큰 것 두 묶음으로 나누었지만, 여기서는key 값보다 작은 값,key 값과 같은 값,key 값보다 큰 값이렇게 3가지로 나눕니다. 구현 자체는 어렵지 않습니다. 코드) void Quick3way(..

이번에는 퀵정렬에 대해 알아보겠습니다. 퀵정렬은 배열을 두 부분으로 나누고 다시 합치는 과정에서 병합 정렬과 비슷한 면이 있지만,  배열을 절반으로 자르는 병합 정렬과는 달리 퀵정렬은 pivot 값을 중심으로 배열을 두 개로 나눕니다. 이떄 pivot 값은 어떤 값이 되어도 상관 없습니다. (pivot 값에 따라 시간 복잡도가 달라집니다) -퀵정렬 코드(난수x)int Partition(int* arr, int low, int high, int n) { int pivot = arr[size_t(floorf((high - low) / 2.0f)) + low]; int i = low; int j = high; while (true) { while (arr[i] pivot) j--; if (..

이번에는 병합 정렬에 대해 알아보겠습니다. 병합 정렬은 이전에 살펴봤던 Karatsuba algorithm 과 비슷하게, 데이터의 크기를 작게 쪼갠 후합치면서 정렬하는 방식입니다. Karatsuba algorithm이 궁금하신 분들은 아래 글 참고 부탁드립니다. https://sol248.tistory.com/46 Karatsuba AlgorithmKaratsuba Algorithm은 큰 문제를 잘게 쪼개서 하나씩 하나씩 결합하는 분할&정복 알고리즘 중에 하나입니다. 먼저, 문제를 어떻게 잘게 쪼개는지 살펴보겠습니다. 1234*5678을 예시로 살펴보죠.이런sol248.tistory.com   다음 사진은 병합 정렬의 작동 방식입니다.  작동 방식 자체는 간단하죠? 그럼 이제 코드를 한번 살펴보겠습니다...

순차 탐색(sequential search) 혹은 선형 탐색(linear search)라고도 하는 탐색에 대해 알아봅시다. 순차 탐색은 말 그대로 앞에서부터 순차적으로 데이터를 찾는 탐색 방법입니다.  코드)#include #include int SequentialSearch(std::vector v, int target) { int N = v.size(); for (int i = 0; i v1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; std::cout  이렇게, 앞에서부터 하나씩 찾아야 하는 값과 비교하며 나아갑니다.찾는 값을 찾은 경우, 바로 그 위치를 반환합니다.   이번에는, 이진 탐색에 대해 알아보겠습니다.이진 탐색이란, 데이터를 두 조각으로 나누어서 탐색하는 것입니..

마스터 정리의 개념 앞에서 정렬이나 탐색 등을 배우며 시간 복잡도에 대해 이야기한 적이 있었죠.  마스터 정리는 big-O 를 손쉽게 구할 수 있는 정리입니다. 마스터 정리란 어떤 것인지 한번 살펴보죠. 여기서a는 나누어지는 문제의 개수를 의미하고 b는 나누어지는 문제의 크기를 의미합니다.f(n)은 나누고 나서 부가적인 과정을 의미합니다.위 식에서 알 수 있는 것은, a*T(n/b)와 f(n)중 차수가 더 큰 것이 시간 복잡도의 결과로 나타난다는 것을 볼 수 있습니다. 차수가 크면 클수록 숫자가 커질 때의 증가폭이 더 크기 때문이겠죠.  위의 식을 좀 더 정리하면 아래의 식으로 간단하게 나타낼 수도 있습니다. 마스터 정리를 이용한다면 점화식을 통하지 않더라도 바로 시간 복잡도를 구할 수 있겠죠. 공식을 ..

점근 표기법이라고 하면 와닿지 않아도 아마 시간 복잡도 혹은 O(n) 이라면 익숙하실 것 같습니다.  점근 표기법에 대해 알아봅시다.  -점근 표기법의 종류𝜪빅오 (Big-Oh)Upper Bound (상한)𝜴빅오메가 (Big-Omega)Lower Bound (하한)𝜭세타 (Theta)Tight Bound (딱 맞는)  -빅오 표기법빅오 표기법은 최악의 경우(상한)을 나타내는 표기법입니다. 이떄 상한이라는 말의 의미는, 아무리 느려도 빅오 표기법으로 표현한 것보다는 빠르다는 것입니다. 보통 어떤 알고리즘의 실행 시간이 주어졌을 때 가장 높은 차수를 사용합니다.  -빅오메가 표기법빅오메가 표기법은 최선의 경우(하한)을 나타내는 표기법입니다. 하한이라는 말의 의미는 아무리 느려도 빅 오메가로 표현한 것보..

Karatsuba Algorithm은 큰 문제를 잘게 쪼개서 하나씩 하나씩 결합하는 분할&정복 알고리즘 중에 하나입니다. 먼저, 문제를 어떻게 잘게 쪼개는지 살펴보겠습니다. 1234*5678을 예시로 살펴보죠.이런 식으로 곱해야 하는 수가 한자리 수가 될 때까지 위와 같은 방법으로 분할시킵니다. 그럼 합칠 때는 어떻게 해야할까요? 위의 과정을 볼 때, 어떤 두 수의 곱셈을 3개의 부분으로 분할시키고 있습니다. 가장 왼쪽에 위치하는 어떤 수들의 앞부분끼리 곱하고 있는 부분. (이를 a라 칭하겠습니다)중간에 위치한 각 수를 분할한 값끼리 더하고 곱셈하는 부분. (이를 b라 칭하겠습니다)가장 오른쪽에 위치한 어떤 수들의 뒷부분들끼리 곱하고 있는 부분. (이를 c라 칭하겠습니다) 원래의 식 1234*5678을 ..