20250108 - C++코테 강의 진행중

코딩테스트

[level 1] 콜라 문제 - 132267

https://school.programmers.co.kr/learn/courses/30/lessons/132267#

[level 1] 콜라 문제 - 132267 풀이코드

#include <string>
#include <vector>

using namespace std;

int solution(int a, int b, int n) {
    int answer = 0;
    
    while (true) {
        if (n < a) {
            break;
        }
        
        answer += (n / a) * b;
        n = ((n / a) * b) + (n % a);
    }
    
    return answer;
}

[level 1] 명예의 전당 (1) - 138477

https://school.programmers.co.kr/learn/courses/30/lessons/138477

[level 1] 명예의 전당 (1) - 138477 풀이코드

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


vector<int> solution(int k, vector<int> score) {
    vector<int> answer;
    vector<int> stage;
    
    for (int i = 0; i < score.size(); i++) {
        stage.push_back(score[i]);
        sort(stage.begin(), stage.end(), greater<int>());
 
        if (stage.size() <= k) {
            answer.push_back(stage[stage.size() - 1]);
        } 
        else {
            answer.push_back(stage[k - 1]);
        }
    }
    
    
    return answer;
}

[level 1] 2016년 - 12901

https://school.programmers.co.kr/learn/courses/30/lessons/12901#

[level 1] 2016년 - 12901 풀이코드

#include <string>
#include <vector>
#include <map>
using namespace std;

vector<int> m = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
vector<string> answer = {"THU", "FRI", "SAT", "SUN", "MON", "TUE", "WED"};
string solution(int a, int b) {
    int sum = 0;
    for (int i = 1; i < a; i++) {
        sum += m[i];
    }
    sum += b;
    int r = sum % 7;
    return answer[r];
}

[level 1] 카드 뭉치 - 159994

https://school.programmers.co.kr/learn/courses/30/lessons/159994

[level 1] 카드 뭉치 - 159994 풀이코드

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

string solution(vector<string> cards1, vector<string> cards2, vector<string> goal) {
    bool isCan = true;
    reverse(cards1.begin(), cards1.end());
    reverse(cards2.begin(), cards2.end());
    
    int i = 0;
    while(i < goal.size()) {
        if (goal[i] == cards1[cards1.size() - 1]) {
            cards1.pop_back();
        }
        else if (goal[i] == cards2[cards2.size() - 1]) {
            cards2.pop_back();
        }
        else {
            isCan = false;
            break;
        }
        i++;
    }    
    
    return isCan ? "Yes" : "No";
}

---

시간복잡도

입력크기에 대해 어떠한 알고리즘이 실행되는 데 걸리는 시간이며 주요 로직의 반복 횟수를 중점으로 측정

시간 → 컴퓨터 사양 등 다양한 환경에 의해서 변경 가능

그래서 시간 복잡도를 설명할 때는 시간이 아니라 어떠한 알고리즘이 주어진 입력크기를 기반으로 어떠한 로직이 몇 번 박복되었는가

→ 로직의 반복횟수를 중점으로 설명

빅오표기법(Big - O notation)

복잡도에 가장 영향을 많이 끼치는 항의 상수인자를 빼고 나머지 항을 없애서 복잡도를 나타내는 표기법

10n^2 + n → 가장 영향을 많이 끼치는 항 → 10n^2 → 상수인자 제거 → n^2;

우선순위로 보는 빅오표기법

n! > 2^n > n^2 > nlogn > n > logn > 1 순서이다.

상수시간 시각복잡도 O(1)

입력크기와 상관없이 일정한 시간복잡도를 가지는 것 → O(1)의 시간복잡도 사용

• 입력과 출력 → cin, cout, scanf, printf
• 곱하기 → a[2] *= 2;,나누기, 나머지연산, 빼기 등
• 간단한 비교 if문
• 배열의 인덱스 참조

재귀함수의 시간복잡도

재귀함수의 Main Logic * 함수 호출

공간복잡도

입력 크기에 대해 어떠한 알고리즘이 실행되는데 필요한 메모리 공간의 양

int 타입 배열 기준, 보통 3000만까지 가능하다.

• 64MB : 1500만
• 128MB : 3000만
• 256MB : 6000만
• 512MB : 1억2천만

보통 128MB까지는 주기 때문에 3000만 정도로 생각하면 된다.

누적합(PrefixSum)

어떠한 배열을 기반으로 앞에서부터 요소들의 누적된 합을 저장해서 새로운 배열을 만들어 사용하는 방법

v [4] = 1, 10, 11, 100;

psum [1] → 1까지 합한 숫자 = 1

psum [2] → 2까지 합한 숫자 = 11

psum [3] → 3까지 합한 숫자 = 21

psum [4] → 4까지 합한 숫자 = 121

다만 누적합을 만들어서 사용할 경우 정적 배열에서만 사용해야 한다.