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 이 주어지면 시간초과로 풀 수 없다. 다른 방법을 찾아야 한다.* 세그먼트 트..

* 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 의 작은 합으로..

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..