우주의WouldYou

시간복잡도

- 알고리즘 수행 시간 기준

- 알고리즘이 실행되는 동안 수행하는 기본적인 연산(최소 크기의 연산)의 수를 입력의 크기에 대한 함수로 표현

-> 입력의 크기가 증가할 때 알고리즘의 수행 시간이 더 빠르게 증가함

== 시간 복잡도가 낮다고 해서 언제나 더 빠르게 동작하는 것은 아니다

== 입력의 크기가 충분히 작을 때는 시간복잡도가 높은 알고리즘이 더 빠르게 동작할 수 있다.

== 시간복잡도가 완전한 속도의 기준이 아님

== 입력의 크기가 매우 작을 경우 시간복잡도는 큰 의미 없음

입력의 크기, 입력의 형태 또한 수행 시간에 영향

#include <string>
#include <vector>

using namespace std;

long long solution(int N) {
    long long answer = 0;
    vector <int> arr;
    
    arr.push_back(1); arr.push_back(1);
    int i = 2;
    while (i  < N+1){
        arr.push_back(arr[i-1] + arr[i-2]);
        i++;
    }
    answer = 2 * (arr[N-1] + (arr[N-1] + arr[N-2]));
    
    return answer;
}

정확성은 100점, 효율성은 0점

모두 저장하고 하니까 당연히 그렇겠지만,, 어떻게 해야하지!?

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

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    string name = "";
    int num = 0;
    int flag = 0;
    sort(participant.begin(), participant.end());
    sort(completion.begin(), completion.end());
    for(int i = 0;i < completion.size(); i++){
        name = participant[i];
        if(participant[i] != completion[i]){
            answer = participant[i];
            flag = 1;
            break;
        }
        
    }
    if (flag ==0)
        answer = participant[participant.size()-1];
    return answer;
}

이거 전에 풀 때는 진짜 큐?인가 그런거 써서 풀려다가 포기했었다. 너무 어렵게 생각하지 말자!

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

int solution(int N, vector<vector<int> > road, int K) {
    int answer = 0;
    int i, j ,k, m, num, num2, city;
    sort(road.begin(), road.end());
    vector <int> uniq;
    uniq.push_back(1);
   int tmp, tmp2;
    for(i=0; i < road.size(); i++){
        tmp = 0;
        for(j = 0; j < 2; j++){
            if(road[i][j] == 1){
                num = abs(j-1);
                city = road[i][num];
                tmp += road[i][2];
                if( tmp > K)
                    break;
                uniq.push_back(city);
                for(k = i + 1; k < road.size(); k++){
                    cout << "k: " << k << " ";
                    for(m =0; m < 2; m++ ){
                        if(road[k][m] == city){
                            tmp += road[k][2];
                            if(tmp > K){
                                tmp -= road[k][2];
                                continue;
                            }
                            num2 = abs(m-1);
                            uniq.push_back(road[k][num2]);
                            tmp -= road[k][2];
                                
                        }
                    }
                }
                
            }
        }
    }
    for(i =0; i < uniq.size(); i++)
        cout << uniq[i] << " ";
    cout << endl;
    sort(uniq.begin(), uniq.end());
    uniq.erase(unique(uniq.begin(), uniq.end()), uniq.end());
    for(i =0 ;i < uniq.size(); i++)
        cout << uniq[i] << " ";
    answer = uniq.size();
    return answer;
}