Do you believe in you?

벡터, 배열을 0이 아닌 특정 값으로 초기화 하고 싶을 때, fill 함수를 사용한다. *헤더:  1) 1차원 배열#include #include #include int main(){ int arr[5] = {0, 1, 2, 3, 4}; fill(arr[0], arr[0] + 5, -1); return 0;} 2) 2차원 배열#include #include int main(){ int arr[5][2] = {{0,0}, {0,1}, (0,2}, {0,3}, {0,4}}; fill(arr[0][0], arr[0][0] + (5*2), -1); return 0;} 3) 벡터#include #include #include int main(){ vector v{0, 1, 2..

C++ 에서 제공하는 copy 문은 copy, copy_if 가 있고 copy_if 를 쓰면 조건문을 추가할 수 있다. 헤더#include  함수copy(시작 지점, 끝 지점, 복사될 변수 시작지점);copy_if( 시작 지점, 끝 지점, 복사될 변수 시작지점, 조건); 예시1) 1차원 배열 복사#include #include int main(){ int arr[4] = {1, 2, 3, 4}; int copiedArr[4] = {0, }; copy(arr, arr+4, copiedArr); return 0;} 2) 2차원 배열 복사#include #include int main(){ int arr[2][4] = {{0,-1}, {0,1}, {-1,0}, {1,0..

구간합, 구간에 따른 경우의 수를 구하는 문제에서 많이 쓰이는 알고리즘인 세그먼트 트리에 대해 알아보자. * 세그먼트 트리의 등장 배경 및 필요성S[0] = A[0];for (int i=1; i 구간합을 단순 for 문을 이용해서 구하는 코드이다.0~n 까지의 합을 구할 때 O(n) 의 시간복잡도가 발생한다.0~n 뿐 아니라 2~5, 100~200 등 m 개의 구간합을 구한다면 O(nm) 의 시간복잡도가 발생한다. 여기서 만약 A[x] 의 값을 변경해야 하면 어떻게 될까.A[x] 값이 포함된 모든 S 배열 값을 변경해서 다시 구간합을 구해주어야 한다.0번 값이라고 하면 또 O(nm) 의 시간복잡도가 발생한다. 큰 수의 n, m 이 주어지면 시간초과로 풀 수 없다. 다른 방법을 찾아야 한다.* 세그먼트 트..

[문제]https://www.acmicpc.net/problem/1463정수 x 가 주어졌을 때, x 를 1로 만드는 최소 연산의 수를 찾는 문제이다. x 를 1로 만드는 연산은 3가지가 있다. 1) x 가 3 으로 나누어 떨어지면 x 를 3 으로 나눈다.2) x 가 2 로 나누어 떨어지면 x 를 2 로 나눈다.3) 1)2) 가 아니면 x 에서 1을 뺀다. 정수 x 값의 범위는 1 ≤ x ≤ 10^6 이다.제한시간은 0.15초 이다. [풀이]정수 x 의 최대값이 10^6 이기 때문에 O(n^2) 만 되어도 문제의 제한시간을 넘긴다. 즉, 완전탐색으로 풀면 안된다. 점화식을 찾아야 한다.'D[x] = x를 1로 만드는 최소 연산의 수' 라고 두고 D[1] 부터 구해보자. D[1] = 1D[2] = D[2/..

* DP(Dynamic Programming)란 ?: 큰 문제를 작은문제로 나누고 작은문제로 큰문제를 푸는 방법. 작은문제가 중복된다.(vs 분할정복: 분할정복과 비슷한데 분할정복은 작은문제가 중복되지 않는다.)  * DP 의 특징1) Overlapping Subproblem: 부분문제(작은문제)가 겹친다.2) Optimal Substructure: 최적 부분 구조. 문제의 정답을 작은 문제의 정답에서 구할 수 있다. 정답의 작은 문제의 정답은 항상 같다.  * DP 알고리즘으로 풀 수 있는 대표적인 예: 피보나치 수 !0 1 1 2 3 5 8 13 21 34 55 89 ...F0 = 0F1 = 1...Fn = Fn-1 + Fn-2(n ≥ 2)Fn 이라는 큰문제 값을 Fn-1 과 Fn-2 의 작은 합으로..

문제 & 설명https://www.acmicpc.net/problem/1269  풀이A의 원소 하나하나의 값을 B에서 찾을 때 이분탐색을 진행한다.  정답 코드#include #include #include using namespace std;int main() { int aNum, bNum, input, sum = 0; int l, h, mid; // 이분탐색을 위한 변수 vector As, Bs; // Input cin >> aNum >> bNum; for (int i = 0; i > input; As.push_back(input); } for (int i = 0; i > input; Bs.push_back(input); } ..

[문제]https://www.acmicpc.net/problem/2343 N 개의 강의가 주어질 때 강의들을 몇개씩 엮어서 블루레이로 만들어서 판매하려고 한다.강의들을 엮을 때 강의의 순서가 바뀌면안되고, 블루레이의 크기는 모두 같아야 한다.즉, 강의를 쪼갤 수 있는 최소합을 찾자. *문제조건강의의 수  N (1 ≤ N ≤ 100,000)과 M (1 ≤ M ≤ N)각 강의의 길이는 10,000분을 넘지 않는다. [예시]9 31 2 3 4 5 6 7 8 917 강의는 총 9개이고, 블루레이는 총 3개 가지고 있다. 1번 블루레이에 1, 2, 3, 4, 52번 블루레이에 6, 73번 블루레이에 8, 9 을 넣으면 각 블루레이의 크기는 15, 13, 17이 된다. 블루레이의 크기는 모두 같아야 하기 때문에 블..

https://www.acmicpc.net/problem/2792 아이들의 수와 보석 색상의 수, 보석의 개수가 주어진다.모든 보석을 나누어줄 때 최대한 차이가 나지 않게 나누어주는 방법을 구하는 문제이다. 한 아이가 갖는 보석의 수를 질투심이라 표현했다.이 때 한 아이는 같은 보석의 색상만 가져야 한다. 또한, 보석을 못받는 아이는 있어도 남는 보석은 없어야 한다. [입력]첫째 줄에 아이들의 수 N과 색상의 수 M이 주어진다. (1 ≤ N ≤ 109, 1 ≤ M ≤ 300,000, M ≤ N)다음 M개 줄에는 구간 [1, 10^9]에 포함되는 양의 정수가 하나씩 주어진다. K번째 줄에 주어지는 숫자는 K번 색상 보석의 개수이다.[출력]첫째 줄에 질투심의 최솟값을 출력한다.  [풀이]하나의 보석의 수가 ..

폭발, 짝짓기 문제는 stack을 떠올리자. [문제]https://www.acmicpc.net/problem/9935 문자열에 폭발 문자열이 있다.폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보자. 남아있는 문자가 없는 경우 "FRULA"를 출력하자. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.폭발 문자열의 길이는 1보다 크거나 같고, 36보다 작거나 같다.두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, ..., 9로만 이루어져 있다. [풀이]문자열의 길이가 매우 기므로, 완전탐색으로는 풀 수 없다.문자열 비교를 위해 stack 자료구조나 erase 함수를 이용하여 for문 하나..

구간이 나오면 정렬!을 떠올리자. 어느정도의 복잡도를 감소시킬 수 있다. [문제]https://www.acmicpc.net/problem/1931 각 회의에 대해 시작시간과 끝나는 시간이 주어져 있을 때,각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾자. 회의의 수 N(1 ≤ N ≤ 100,000)시작 시간과 끝나는 시간은 2^31-1보다 작거나 같은 자연수 또는 0 [해결방법]회의의 수가 최대 100,000 개 이므로 완전탐색으로는 풀 수 없다. Greedy 로 풀어야 한다.특히, 구간이 주어지면 정렬을 생각하자. 라인스위핑 문제라 부른다. 1) 시작 시간을 기준으로 정렬2) 끝나는 시간을 기준으로 정렬3) 회의 시간을 기준으로 정렬 위 3가지 처럼 모든 풀이방법을 생각하..