Do you believe in you?

구간합, 구간에 따른 경우의 수를 구하는 문제에서 많이 쓰이는 알고리즘인 세그먼트 트리에 대해 알아보자. * 세그먼트 트리의 등장 배경 및 필요성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가지 처럼 모든 풀이방법을 생각하..

[문제]https://www.acmicpc.net/problem/2109 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불한다.첫째 줄에 정수 n이 주어진다. 다음 n개의 줄에는 각 대학에서 제시한 p값과 d값이 주어진다.가장 많은 돈을 벌 수 있는 순회강연을 찾고 그 돈을 출력하라.  [풀이]d 일 안에 와서 강연이라는 조건을 d 일에 강연하는 걸로 잘못 이해하여 map 으로 풀다가 틀렸다.게시판을 참고해보니 d 일 안에 와서 라는 조건이 있기에 d 일 안이면 언제든 강연할 수 있다는 것을 생각해야 한다. n개의 대학의 전부를 비교하기에는 시간제한이 되므로 sort, priority queue 를 이용한 Greedy  로 접근해야 한다.기한..

1. 이진수. Boolean 배열/벡터.128 64 32 16 8 4 2 1  1    0   1   1  0 0 0 0(176)0001001000110100010101100111100012345678  2. 비트 연산자&비트단위로 AND 연산|비트단위로 OR 연산^비트단위로 XOR 연산(같으면 0, 다르면 1)~피연산자의 모든 비트 반전피연산자의 비트 열을 왼쪽으로 이동>>피연산자의 비트 열을 오른쪽으로 이동 * 10진수 -> 2진수 변환 사이트 Decimal to Binary ConverterDivide by the base 2 to get the digits from the remainders: Divisionby 2 Quotient Remainder(Digit) Bit #www.rapidtable..