3냥 집사이면서 게임 개발자입니다.

누적합이란 요소들의 누적된 합의 의미로 어떠한 배열을 기반으로 앞에서 부터 요소들의 누적된 합을 저장해 새로이 배열을 만들어서 이를 활용하는 것을 말합니다. 이는 앞에서부터 더하는 prefix sum과 뒤에서부터 더하는 suffix sum이 있지만 코딩테스트는 prefix sum만 나오지 prefix sum 만 공부해도 좋습니다. 누적합의 경우 0번 배열에 넣지 않고 1번 배열부터 담는 것이 구현하는 것이 쉽습니다. 누적합이란 누적해서 더해진 값들의 배열을 의미합니다. 1,2,3,4 라는 배열의 누적합은 1,3,6,10이란 배열이 됩니다. 이렇게 만들어놓으면 구간 쿼리에 대응하기가 쉽습니다. 예를 들어 0 번째 요소에서 3 번째 요소까지 다 더하라고 했을 때 누적합 배열 3 번째 요소를 이용하면 되기 때..

공간복잡도는 "입력크기에 대해 어떠한 알고리즘이 실행되는데 필요한 메모리 공간의 양"을 가리킵니다. 이는 정적 변수로 선언된 것 말고도 동적으로 재귀적인 함수로 인해 공간을 계속해서 필요로 할 경우도 포함하여 배열이든 맵이든 셋이든 요소들을 담을 공간이면 모두 적용됩니다. 다음 코드에서 int형 배열 1000만 개 1개, 1004개 1개를 선언했습니다. 둘 다 포함해서 공간복잡도를 계산합니다. int a[10000000]; void f() { int b[1004]; } int main() { return 0; } 예를 들어 입력이 N이 들어오고 거기에 따라 N개 int형 요소를 담아야 할 공간이 필요하다면 4N바이트의 공간이 필요합니다. 이를 빅오표기법으로 나타내면 O(N)이 됩니다. 상수는 버립니다. ..

Q4. 다음 코드의 시간복잡도는? tip. 로그(log)는 지수 함수의 역함수이다. 어떤 수를 나타내기 위해 고정된 밑을 몇 번 곱하여야 하는지를 나타낸다고 볼 수있다. #include using namespace std; int N; void solve(int N) { int a = 0, i = N; while(i > 0) { a += i; i /= 2; } cout N; solve(N); return 0; } // 디버깅 작업했을 때 // 입력 32 // 횟수 6 // 입력 8 // 횟수 4 위 코드를 보면 solve 함수 내에 while 문을 사용한 알고리즘이 몇 번 반복하는지가 시간복잡도를 결정하는 핵심 알고리즘이라는 걸 알 수 있습니다. cnt 를 선언하고 디버깅했을 때 (logn)+1 임을 알..

복잡도는 시간복잡도와 공간복잡도로 나뉘어지는데 먼저 시간 복잡도에 대해 알아봅시다. 시간복잡도란 입력크기에 대해 어떠한 알고리즘이 실행되는데 걸리는 시간이며 주요 로직의 반복 횟수를 중점으로 측정됩니다. 시간? 시간이라는 것은 컴퓨터 사양 등 여러가지 요소에 영향을 받곤 합니다. 그래서 시간복잡도를 설명할 때는 시간이 아니라 어떤 알고맂므이 주어진 입력 크기를 기반으로 어떤 로직이 몇번 반복했는가를 중점으로 설명합니다. 예를 들어 다음 코드는 어떤 시간복잡도를 가질까요? for(int i = 0; i nlog..