시간복잡도와 공간복잡도

컴퓨터는 1초에 대략 3-5억개 정도의 연산을 처리할 수 있다. 연산이 단순 연산인지, 나눗셈, 곱셈, 함수 호출 같은 복잡한 연산인지에 따라 약간의 차이는 있을 수 있다.

int func1(int arr[], int n){
    int cnt =0;
    for(int i=0;i<n;i++){
        if(arr[i]%5==0) cnt++;
    }

    return cnt;
}

위와 같은 코드가 있다. 여기서의 연산 횟수를 확인해보자

int func1(int arr[], int n){
    int cnt =0; //1번 
    for(int i=0;i<n;i++){ // 초기값 0 설정으로 1번
        if(arr[i]%5==0) cnt++; // 5의 나머지 구하기로 1번, 0이랑 맞는지 1번, cnt 증가 1번 
        //i 증가 1번, i가 n보다 작은지 확인 1번 
    }

    return cnt; //1번 
}

1+1+5n+1= 5n+3

문제

최선의 경우 1초 (바로 정답) 최악의 경우 n초 (가장 나중이 정답) 평균은 중간에 있을 때 n/2

문제

최선의 경우 1초

최악의 경우는.. n명이 있는데 가운데에 질의해서 왼쪽, 오른쪽으로 방향을 나누고 또 가운데에 질의해서.. 숫자를 대입해보면 더 쉬움 16명일 때면 8명으로 나누고 4명으로 나누고 2명으로 나누면 1명이 걸러질 것 -> 총 4명 log₂N

빅오표기법은 대표항만 남겨두는 방법이다.

내 풀이가 빅오로 몇이고
제한시간 내에 통과할 수 있는지

n이 500인데 O(2ⁿ) 풀이를 했다면 시간 내에 불가하다.

#include <bits/stdc++.h>

using namespace std;

int N;
cin>>N;
int sum=0;

for(int i=1;i<=N;i++){
    if(i%3==0 || i%5==0)
        sum+=i;
}

위 코드는 O(n)이다. 이걸 O(1)로 줄일 수 있다고 한다. 흠.. 3,5,6,9,10.. N=3, sum=3 N=4, sum=3 N=5, sum=8 N=6, sum=14 N=7, sum=14 N=8, sum=14 N=9, sum=23 N=10, sum=33

#include <bits/stdc++.h>
using namespace std;

int N; 
cin>>N;

//3 
int n= (N-(N%3))/3;
int p=n/2(2*3+(n-1)*3)

//5
int m,q=0;
if (N>=5){
    m=(N-(N%5))/5;
    q=m/2(2*5+(m-1)*5);
}

//15
int x,o=0;
if (N>=15){
    x=(N-(N%15))/15;
    o=x/2(2*15+(x-1)*15);
}

int sum=p+q-o;
return sum;

제출한 답

#include <iostream>

using namespace std;

// 1부터 n까지 k의 배수의 합을 구하는 함수
long long sumMultiples(int n, int k) {
    int count = n / k; // 배수의 개수 (ex: 10까지 3의 배수 개수 = 3개)
    
    // 공식: k * (1 + 2 + ... + count) = k * count * (count + 1) / 2
    // long long 형변환을 통해 큰 수 계산 시 오버플로우 방지
    return (long long)k * count * (count + 1) / 2;
}

int main() {
    int N;
    if (!(cin >> N)) return 0;

    // 포함-배제의 원리 적용
    long long ans = sumMultiples(N, 3) + sumMultiples(N, 5) - sumMultiples(N, 15);

    cout << ans << endl;
    return 0;
}

코드 리뷰

integer division 조심 : 알고리즘에서 곱셈을 먼저하고 나중에 나눗셈 진행하기
오버플로우 방지를 위해 long long 선언
포함-배제의 원리 적용

∣A∪B∣=∣A∣+∣B∣−∣A∩B∣ 집합 문제처럼 풀기
코드 사용성 높이기

long long ans = sumMultiples(N, 3) + sumMultiples(N, 5) - sumMultiples(N, 15);

#include <bits/stdc++.h>

using namespace std;

int func2(int arr[],int N){

}

int input;
int arr[1001]={0,};
cin >> input;

for(int i=0;i<input;i++){
    cin>>arr[i];
}

return func2(arr,input);

공간 복잡도

코테에서는 거의 시간복잡도가 까다롭기 때문에 중요한 내용은 아니라고 생각하지만 일단 보자.

512MB는 약간 1.2억개의 int 선언이 가능하다.

coding