문제zip

나무를 자를 때 몇 토막이 나오는지는 또 다른 문제 → 길이가 28, 30 인 애들을 10 단위로 자른다면, 둘 다 두 토막씩 나옴 → 모듈러 활용합시다

⭐⭐⭐ 나무 자르는 비용이 어마어마어마하게 비싸다면 ? ? ? ?
- 안 자르는 게 낫겠는데 ? ? ? ?
- 나무 개수 * 이익 - 비용 구조로는 판단하기 힘들 걸 ? ? ? ?
  - 그럼 어떻게 구현하지 ? ? ? ?
    각각의 나무마다 → 순이익을 계산하는 방식으로 바꾸자. . . .

결국 bruteforce하게 계산하기…

#include <iostream>
#include <vector>

using namespace std;

int M,N;

vector<vector<int>> v;


void dfs(int x, int y){
    // 예외 처리
    if (x < 0 || x >= M || y < 0 || y >= N) {
        return;
    }
    // 이미 방문한 경우도 예외 처리해주어야
    if (v[x][y] == 0) {
        return;
    }

    // 지나간 값 갱신
    v[x][y] = 0;
    // 네 방향 해두면 알아서 탐색함 like virus
    dfs(x - 1, y); // 북
    dfs(x + 1, y); // 남
    dfs(x, y - 1); // 서
    dfs(x, y + 1); // 동

}

int main() {

    int T;
    cin >> T;

    while(T--){

        cin >> M >> N;

        int K;
        cin >> K;

        int X,Y;
        v.assign(M, vector<int>(N,0));

        while(K--){
            cin >> X >> Y;
            v[X][Y] = 1;
        }


        int count = 0;
        //재귀함수로 불러오기
        for(int i=0; i<M; i++){
            for(int k=0; k<N; k++){
                
                if(v[i][k] == 1){
                    count += 1;
                    dfs(i,k);
                }
            }
        }
        cout <<  count << endl;
    }
    
        
    return 0;
}

#1149

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


int main(){

   
    long N; 

    cin >> N;
    
    // 이차원 벡터 선언 : v -> 저장용, dp -> 계산용
    vector<vector<long>> v (N,vector<long>(3));
    vector<vector<long>> dp (N,vector<long>(3));

    // 벡터 입력 받기
    for(int i = 0; i < N; i++){
        for(int k = 0; k<3; k++){
            cin >> v[i][k];
            
        }
    }

    // DP 계산 : i번쨰 값(무슨 색인지)에 따라 최솟값 계산하고 배열에 저장
    // 초기값 설정
    dp[0] = v[0];
    for(int i = 1; i < N; i++){
        dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + v[i][0];
        dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + v[i][1];
        dp[i][2] = min(dp[i-1][1], dp[i-1][0]) + v[i][2];
    }

    long result = *min_element(dp[N-1].begin(),dp[N-1].end());
    
    cout << result << endl;


    return 0;
}

DP 계산법

min / *min_element

// dp[0], dp[1], dp[2]는 각각 R, G, B로 칠했을 때의 누적 최소 비용
int dp[3] = {0, 0, 0};

for (int i = 0; i < N; ++i) {
  int cost_r, cost_g, cost_b;
  cin >> cost_r >> cost_g >> cost_b;

  // 이전 단계의 누적 최소 비용을 임시 변수에 저장
  int prev_dp0 = dp[0];
  int prev_dp1 = dp[1];
  int prev_dp2 = dp[2];

  // 현재 단계의 누적 최소 비용 계산
  // i번째 집을 R로 칠하는 경우 = (i-1번째 집을 G 또는 B로 칠한 최소 비용) + i번째 집을 R로 칠하는 비용
  dp[0] = min(prev_dp1, prev_dp2) + cost_r;
  dp[1] = min(prev_dp0, prev_dp2) + cost_g;
  dp[2] = min(prev_dp0, prev_dp1) + cost_b;
}

굳이 이차원 벡터 두개로 받아오지 않고 dp를 누적시키는 방법만 활용해도 됨 → 공간 복잡도를 낮출 수 있음

#1038

#include <iostream>
#include <vector>

using namespace std;

bool check_valid(long long N){
    // 3214 -> 벡터로 저장
    // 950
    int num;
    vector<int> v;
    int count = 0;
    while(N > 0){
        num = N % 10;
        v.push_back(num);
        N = N/10;
        count++;
    }

    // v = [4][1][2][3]
    // v = [0][5][9]
    int check = 0;
    for(int i = 0; i < count-1; i++){
        if(v[i] < v[i+1]){
            check++;
        }
    }

    if(count==check+1){
        return true;
    }
    else{
        return false;
    }
}

int main(){

    long long N;
    cin >> N;

    // brute-force하게 n번째 감소하는 수를 찾기 ?
    // 정수를 벡터에 저장해서, 벡터 요소끼리 비교하기
    // abcde -> a > b > c > d > e
    
    int count = 0;
    int result;
    if(N>1022){
        result = -1;
    }
    else{
        for(long long i=0; ;i++){
            if(check_valid(i)){
                count++;
            }
            if(count == N){
                result = i;
                break;
            }
        }
    }
    
    cout << result <<endl;
    return 0;
}

BF하게 짠다면 → 시간초과ㅠ → 대신에 감소하는 수 먼저 찾아 넣기

#include <iostream>
#include <vector>
#include <algorithm> 

using namespace std;

vector<long long> decreasing_nums; // 생성된 감소하는 수를 저장할 벡터

// 감소하는 수를 재귀적으로 생성하는 함수
void generate(long long num) {
    // 1. 현재 생성된 수를 리스트에 추가
    decreasing_nums.push_back(num);

    int last_digit = num % 10; // 현재 수의 가장 마지막 자릿수

    // 2. 마지막 자릿수보다 작은 수를 뒤에 붙여서 새로운 수를 만듦
    for (int i = 0; i < last_digit; ++i) {
        generate(num * 10 + i); // 재귀 호출
    }
}

int main() {

    int N;
    cin >> N;

    // --- 감소하는 수 생성 ---
    // 0부터 9로 시작하는 모든 감소하는 수를 생성
    for (int i = 0; i <= 9; ++i) {
        generate(i);
    }

    // --- 정렬 및 출력 ---
    // 생성된 수들을 오름차순으로 정렬
    sort(decreasing_nums.begin(), decreasing_nums.end());

    // N번째 수가 존재하는지 확인 후 출력
    if (N >= decreasing_nums.size()) { // N이 총 개수보다 크거나 같으면 없는 수
        cout << -1 << endl;
    } else {
        cout << decreasing_nums[N] << endl;
    }

    return 0;
}

#1717

#include <iostream>
#include <vector>

using namespace std;

int parent[1000001];

int find(int x) {
    if (parent[x] == x) return x;
    return parent[x] = find(parent[x]);
}

void unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a != b) parent[b] = a;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m;
    cin >> n >> m;
    
    for (int i = 0; i <= n; i++) {
        parent[i] = i;
    }
    
    for (int i = 0; i < m; i++) {
        int op, a, b;
        cin >> op >> a >> b;
        
        if (op == 0) {
            unite(a, b);
        } else {
            if (find(a) == find(b)) {
                cout << "YES\n";
            } else {
                cout << "NO\n";
            }
        }
    }
    
    return 0;
}

정답코드

#include <iostream>
#include <vector>

using namespace std;

long long n,m;
vector<long long> parent;


// 원소 x의 대표원소 찾기 -> recursive하게
long long find(long long x) {
    if (parent[x] == x) { // -1 제거
        return x;
    }
    // 경로 압축 최적화와 함께 -1 제거
    return parent[x] = find(parent[x]);
}

/*
    [0 1 2 3] -> add(2,3) [0 1 2 2] -> add(1,2) [0 1 1 2]
    check(1,3) == NO ? 
    we need to define root
    [0 1 2 3] -> add(2,3) [0 1 2 2] -> add(1,2) [0 1 1 2] root(3) should be equal to root(1)
*/
void add(long long a, long long b) {
    long long rootA = find(a);
    long long rootB = find(b);

    if (rootA != rootB) {
        parent[rootB] = rootA; // -1 제거
    }
}

void check(long long a, long long b){
    long long rootA,rootB;
    rootA = find(a);
    rootB = find(b);

    if(rootA == rootB){
        cout << "YES" << endl;
    }
    else{
        cout << "NO" << endl;
    }
}


void swap(long long *a, long long *b){
    long long c;
    c = *a;
    *a = *b;
    *b = c;
}

int main(){
    // n,m
    // 0 -> 합집합, 1 -> 집합 확인
    
    cin >> n >> m;
    parent.resize(n+1);

    // 벡터 초기화
    for (int i = 0; i <= n; i++) {
        parent[i] = i;
    }

    // n번 동안, 3개의 입력 받기
    long long index, a, b;
    while(m--){
        cin >> index >> a >> b;
        if(a > n || b > n || a < 0 || b < 0){
            cout << "err type 1" << endl;
            return 0;
        }
        else{
            // 대표값 == 최솟값
            if(a>b){swap(&a,&b);}

            if(index == 0){
                add(a, b);
            }

            else if(index == 1){
                check(a, b);
            }

            else{
                cout << "err type 2" << endl;
                return 0;
            }
        }
    }
}

내 코드 → 시간초과 ㅜㅜ

endl → \n, 불필요한 swap 제거 등 해봐도 여전히 시간초과가 나오는데 이유를 모르게써여 ㅠ

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

이 두 줄 추가하니까 통과 …

이 두 줄은 C++의 cin, cout 입출력 속도를 C의 scanf, printf 수준으로 매우 빠르게 만들어주는 코드입니다. 알고리즘 문제 풀이(경쟁적 프로그래밍)에서는 거의 필수적으로 사용됩니다.

## ios_base::sync_with_stdio(false);

이 코드는 C++의 iostream과 C의 stdio 라이브러리 간의 동기화를 비활성화합니다.

기본 상태 (동기화): C++의 cout과 C의 printf는 같은 출력 버퍼를 공유합니다. 이 때문에 cout과 printf를 섞어 써도 출력 순서가 보장됩니다. 하지만 이 순서를 보장하기 위해 내부적으로 검사하는 과정이 필요해 속도가 느려집니다.

false 설정 시: 이 동기화를 끊어버립니다. C++ 스트림은 자신만의 독립적인 버퍼를 사용하게 되어 C 스트림을 신경 쓰지 않고 매우 빠르게 동작할 수 있습니다.

⚠️ 주의점

이 코드를 사용한 후에는 C 스타일 입출력(scanf, printf, puts 등)과 C++ 스타일 입출력(cin, cout)을 절대로 섞어 쓰면 안 됩니다. 섞어 쓸 경우 출력 순서가 완전히 꼬여버릴 수 있습니다. cin, cout만 사용해야 합니다.

## cin.tie(NULL);

이 코드는 cin과 cout의 "묶음(tie)"을 풀어줍니다.

기본 상태 (묶여있음): 기본적으로 cin은 cout에 묶여 있습니다. 이 때문에 cin으로 입력을 받기 직전에 cout의 버퍼가 자동으로 비워집니다(flush). 예를 들어, cout << "이름 입력: "; cin >> name;과 같은 코드에서 "이름 입력: "이라는 메시지가 화면에 먼저 보이도록 보장하기 위함입니다.

NULL 설정 시: 이 묶음을 풀어버립니다. cin을 사용할 때마다 불필요하게 cout 버퍼를 비우는 동작을 없애줍니다. 알고리즘 문제 풀이에서는 대화형 입출력이 거의 없으므로, 이 과정은 시간 낭비일 뿐입니다.

⚠️ 주의점

특별한 주의점은 없으나, 이 코드는 cin과 cout의 묶음만 푸는 것이므로 endl 사용에는 여전히 유의해야 합니다.

## 요약 및 핵심 팁

sync_with_stdio(false): C 입출력과의 동기화 해제 → 속도 향상

cin.tie(NULL): cin/cout 묶음 해제 → 불필요한 버퍼 비우기 방지 → 속도 향상

가장 중요한 추가 팁: 위 두 줄을 사용했더라도, cout << endl;을 사용하면 매번 출력 버퍼를 비우기(flush) 때문에 cin.tie(NULL)로 얻은 속도 향상 효과가 사라집니다.