전체 글

[골5] 2294 - 동전2

#include #include #pragma region 입출력 속도향상 #define FAST_IO() \ {\ ios::sync_with_stdio(false);\ cin.tie(NULL); \ cout.tie(NULL); \ }\ #pragma endregion using namespace std; int main() { FAST_IO(); int n, k; cin >> n >> k; vector v(n), dp(k + 1); for (int i = 0; i > v[i]; for (int i = 1; i

최장 증가 부분 수열 (LIS)

개념 어떤 임의의 수열이 주어졌을 때, 수열에서 앞에서부터 차례대로 몇 개의 숫자들을 뽑아서 부분수열을 만들 수 있다. 이렇게 만들 수 있는 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열(LIS, Longest Increasing Subsequence)라고 한다. 예를 들어 [5, 2, 1, 4, 3, 5] 라는 수열이 있다고 가정해보자. 해당 수열에서 최장 증가 부분 수열에 해당하는 수열은 무엇일까? 세번째에 있는 숫자 1을 꺼낸다. 다섯번째에 있는 숫자 3을 꺼낸다. 여섯번째에 있는 숫자 5를 꺼낸다. 이렇게 만들어진 수열 [1, 3, 5]가 위 수열에서 만들 수 있는 최장 증가 부분 수열에 해당하고 길이는 3이 된다. 구할 수 있는 방법에는 크게 2가지가 있고 시간 복잡도에서..

[C++] STL container 시간 복잡도 및 특징 비교

※용어 설명※ amortized : 분할 상환하다는 뜻을 가지고 있는 이 단어는, 쉽게 설명하자면 최악의 경우는 더 높은 값의 시간 복잡도를 가질 수 있지만, 대체적으로는~ 으로 생각하면 될 것 같다. 점근적 분석(Asymptotic analysis)으로 보면 O(n)이 나오는 경우에, 분할상환분석(Amortized Analysis)으로 보면 O(1)이 나오는 경우도 있기 때문이다. ​ red-black tree: 레드블랙트리. Balanced Binary-Search Tree로 이루어진 구조. [출처] C++ STL container 시간 복잡도 및 특징 비교.|작성자 Chan

[C++] 순열 / 조합 구하기 (next_permutation/prev_permutation 함수)

순열 next_permutation C++의 algorithm 헤더에는 n개의 원소의 순열을 구할 수 있는 next_permutation이라는 함수가 있다. 기본은 오름차순이다, 즉 내림차순인 prev_permutation을 사용하기 위해서는 내림차순으로 정렬 되어있어야 한다. 중복이 있는 원소들은 제외하고 순열을 만들어준다. // default bool next_permutation (BidirectionalIterator first, BidirectionalIterator last); // custom bool next_permutation (BidirectionalIterator first, BidirectionalIterator last, Compare comp); next_permutation ..

[알고리즘] 순열과 조합의 차이

순열과 조합의 가장 큰 차이는 순서가 있고 없고 이다. 예를 들어 자전거의 번호가 있는 자물쇠를 연다고 가정해보자. 자물쇠 번호가 1234라고 한다면 순서에 대한 고려 없이 4321을 입력하면 자물쇠는 열리지 않는다. 이를 순열이라고 한다. (순서가 있음) 또 다른 예시로 닭가슴살 샐러드를 가정해보자. 닭가슴살 샐러드의 재료는 닭가슴살, 양상추, 소스, 토마토라고 한다면 우리는 샐러드를 담을 때 닭가슴살을 처음으로 넣고 두 번째는 양상추... 이런 식으로 넣지 않고 그냥 재료에 맞게 넣는다. 이를 조합이라고 한다. (순서가 없음) 이제 수학적으로 다가가 보자 1 2 3 4 배열이 있고 2가지 경우를 뽑는다고 가정해보자 순열의 경우에는 순서가 중요하기에 하기와 같이 다 뽑아 버린다. 1 2 1 3 1 4 ..

[수학] 순열, 조합 공식 총 정리

팩토리얼 (!) 서로 다른 n개를 나열하는 경우의 수를 의미한다. 기호로는 n! 으로 표기하고 계산은 n부터 1씩 줄여나가면서 1일 될 때까지의 모든 수를 곱한다. 순열 (nPr) 서로 다른 n개 중에 r개를 선택하는 경우의 수를 의미한다. (순서 상관 있음) 조합 (nCr) 서로 다른 n개 중에 r개를 선택하는 경우의 수를 의미한다. (순서 상관 없음) 중복 순열 (n​πr) 중복 가능한 n개 중에서 r개를 선택하는 경우의 수를 의미한다. (순서 상관 있음) 중복 조합 (nHr) 중복 가능한 n개 중에서 r개를 선택하는 경우의 수를 의미한다. (순서 상관 없음) 같은 것이 있는 순열 나열하는 원소의 팩토리얼에 중복된 원소들의 팩토리얼을 나누어주면 된다. 원 순열 원 모양의 테이블에 n개의 원소를 나열하..

SDK, API의 개념과 차이점

API API란 Application Programming Interface의 약자로, 모듈화하여 만들어진, 어떤 기능을 제어/제공하는 인터페이스를 말한다. 우리가 사용하는 대부분의 애플리케이션은 API에 의존하고 있다. 예) - 차량 공유 앱에서 승차 거리와 시간을 계산하는 것 👉 API의 기능 - 차량 공유 앱에서 드라이버가 픽업 위치에 도착했음을 SMS로 알 수 있는 것 👉 API의 기능 SDK SDK란 Software Development Kit의 약자로, 소프트웨어 개발 도구 모음이라고도 한다. SDK는 API, IDE, 문서, 라이브러리, 코드 샘플 및 기타 유틸리티가 포함될 수 있다. SDK는 프로그램 및 응용 프로그램 개발의 복잡성을 줄이는 강력한 기능 집합이다. 예) iOS SDK를 다운..

[실3] 11659 - 구간 합 구하기 4

#include #include using namespace std; #pragma region 입출력 속도향상 #define FAST_IO() \ {\ ios::sync_with_stdio(false);\ cin.tie(NULL); \ cout.tie(NULL); \ }\ #pragma endregion int main() { FAST_IO(); int n, m; cin >> n >> m; vector v(n + 1), t(n + 1); // 입력 for (int i = 1; i > v[i]; // 구간합 구하기 for (int i = 1; i > s >> e; cout

카라츠바의 빠른 곱셈 (Karatsuba algorithm)

카라츠바의 빠른 곱셈 알고리즘은 수백, 수만자리나 되는 큰 두개의 정수를 곱하는 알고리즘이다. 필요성 카라츠바 알고리즘을 소개하기에 앞서, 두자릿수 이상의 두 수를 곱하는 과정은 다음과 같다. 이 알고리즘의 시간복잡도는 두 정수의 길이가 모두 n이라고 할 때 O(n^2)이다. 2중 for문을 이용하고 있으니 이 점을 이해하기는 어렵지 않을 것이다. 카라츠바 알고리즘은 이 시간복잡도를 O(n^log(3)) 까지 낮춰주기 위해 사용된다. log(3) = 1.585...이므로 O(n^2) 보다 훨씬 적은 곱셈을 필요로 한다. 만약 n이 10만이라고 하면 곱셈 횟수는 대략 100배 정도 차이가 난다. 아이디어 자릿수가 n인 두개의 수 a,b를 단순히 곱하기 위해서는 O(n^2)이 소요되지만, 덧셈과 뺄셈을 하는..

[골5] 1106 - 호텔

#include #include #include using namespace std; #pragma region 입출력 속도향상 #define FAST_IO() \ {\ ios::sync_with_stdio(false);\ cin.tie(NULL); \ cout.tie(NULL); \ }\ #pragma endregion #define MAX 100000 int main() { FAST_IO(); int c, n; cin >> c >> n; vector v; for (int i = 0; i > a >> b; v.push_back({ a,b }); } int dp[MAX + 1] = { 0 }; for (int i = 0; i < v.size(); i++) ..