이 포스트는 바킹독님의 '바킹독의 실전 알고리즘'포스트를 읽고 정리한 것입니다.
https://blog.encrypted.gg/category/%EA%B0%95%EC%A2%8C/%EC%8B%A4%EC%A0%84%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

내가 생각한 풀이 :

#include <iostream>
using namespace std;
int func1(int N){
    int sum=0;
    for (int i=1; i<=N; i++){
        if (i%3==0||i%5==0){
            sum+=i;
        }
    }
    return sum;
}
int main() {
    cout << func1(16) << endl;
    cout << func1(34567) << endl;
    cout << func1(27639) << endl;


}

고민해볼 풀이 : O(1)에 실행

#include <iostream>
using namespace std;
int func1(int N){
    int k[3]={N/3,N/5,N/15};
    int n[3]={3,5,-15};
    int sum=0;
    for (int i=0; i<3;i++) {
        sum+=n[i]*k[i]*(k[i]+1)/2;
    }
   return (sum);
}
int main() {
    cout << func1(16) << endl;
    cout << func1(34567) << endl;
    cout << func1(27639) << endl;

}

하면서 안 사실:
C++의 int형 벡터는 func2({1,52,48},3)와 같이 initializer list를 인자로 받을 수 있다.

#include <iostream>
#include <vector>
using namespace std;

int operator+(const vector<int> & lhs, const vector<int> & rhs);

int func2(vector<int> arr, int N) {
    for (int i=0;i<N; i++) {
        for (int j=i+1;j<N; j++) {
            if (arr[i]+arr[j]==100) {
                return 1;
            }
        }
    }
    return 0;
}
int main() {
    cout << func2({1,52,48},3);
    cout << func2({50,2},2);
    cout << func2({4,13,63,87},4);


}

내가한 풀이 : O(N^2)에 실행

시간 복잡도

입력의 크기에따라 문제를 해결하는데 걸리는 시간 사이 상관관계
ex) O(1) -> 입력의크기가 무엇이든 해결하는데 상수시간이 걸림
O(n) -> cn에 비례하는 시간이 걸림...

대략 O(N)의 풀이는 입력을 1000만아래로 가질 수 있다.
O(N^2)-> 5000 등..

문제를 풀때 고려해야함.

공간 복잡도

입력의 크기에 따라 문제를 해결하는데 드는 메모리 사이 상관관계
eX) 512MB-> 1.2억개의 int

자료형 별 주의할 점

int형

오버플로우 조심

double형

1. 실수 연산은 오차가 있으니 조심 (float : 유효숫자 6자리, double : 유효숫자 15자리)
   웬만하면 float말고 double쓰자
2. double에 longlong 범위 정수 함부로 쓰지말자 (longlong : 최대 19자리, double : 15자리, int:9자리) double ->int는 가능
3. 실수 비교할때 등호사용 x