돈많은백수되기프로젝트

누적합? (prefix sum)누적합이란 요소들의 누적된 합의 의미로 어떠한 배열을 기반으로 앞에서부터 요소들의 누적된 합을 저장해 새로이 배열을 만들어서 이를 활용하는 것을 말합니다. 이는 앞에서부터 더하는 prefix sum과 뒤에서부터 더하는 suffix sum이 있지만 코딩테스트에는 prefix sum만 나오니 prefix sum만을 배우면 됩니다.  예시문제승철이는 뇌를 잃어버렸다. 학교에 갔더니 선생님이 자연수로 이루어진 N개의 카드를 주며 M개의 질문을 던진다. 그 질문은 나열한 카드 중 A번째부터 B번째까지의 합을 구하는 것이다. 뇌를 잃어버렸기 때문에 승철이는 이 문제를 풀 수 없다. 문제를 풀 수 있는 프로그램을 작성해 보자.입력수의 개수 N, 합을 구해야 하는 횟수 M, 그 이후 N개..

#1. 시간복잡도복잡도는 시간복잡도와 공간복잡도로 나누어지는데 먼저 시간복잡도에 대해 알아보겠습니다. 시간복잡도란 입력크기에 대해 어떠한 알고리즘이 실행되는데 걸리는 시간이며 주요로직의 반복횟수를 중점으로 측정됩니다. 아니 시간이라고?그렇다면 시간복잡도를 측정하기 위해서 항상 시간을 재야 할까요?만약 어떠한 로직이 있고 그 로직이 걸리는 시간을 재려면 이렇게 재야 합니다. console.time("test")let sum = 0;for (let i = 0; i  하지만 이러한 시간이라는 것은 컴퓨터 사양 등 여러가지 요소에 영향을 받곤 합니다.그래서 시간복잡도를 설명할 때는 시간이 아니라 어떠한 알고리즘이 주어진 입력크기를 기반으로 로직이 몇번 반복되었는가를 중점으로 설명합니다. 예를 들어 다음코드는 어..

순열서로 다른 n개의 원소에서 r (단, 0≤ n)개를 중복없이 순서를 고려하여 선택하거나 나열하거나 하는 것을 순열(permutation)이라고 합니다. 예를 들어 집합 {1, 2, 3}의 원소들의 모든 순열을 구한다면{1, 2, 3}{1, 3, 2}{2, 1, 3}{2, 3, 1}{3, 1, 2}{3, 2, 1}로 총 6가지가 나오게 됩니다.   next_permutation 함수C++의 algorithm 헤더에는 n개의 원소의 순열을 구할 수 있는 next_permutation이라는 함수가 있습니다. 기본적 문법은 다음과 같습니다.  // defaultbool next_permutation (BidirectionalIterator first, BiirectionalIterator last);// c..