18th Koala 1주차

Koala 1주차를 시작했다 \\٩(•́⌄•́๑)و//// (빠밤)

 

항상 코드트리에서 문제를 풀다가 백준에서 문제를 풀려고 하니 어색한 점이 한두 가지가 아니었다.

 

특히, 백준 사이트 내에서 문제를 보면서 동시에 코드를 작성할 수 없다는 점이 조금 아쉬웠다.

 

하지만 한 가지 아주 큰 장점이 있었다...!!! 바로 코드트리에서는 시간이나 메모리 제한 없이 문제를 풀었는데, 백준에서는 그런 제한이 있어서 좀 더 효율적인 코드를 짜야 한다는 점이 엄청 좋다고 느꼈다!!!

 

들어보니 기업에서 코딩 테스트를 볼 때 시간이나 메모리 제한을 두는 곳도 있다고 하던데, 만약 Koala를 시작하지 않았다면 백준도 하지 않았을 거고, 그런 부분에 대해 제대로 공부하지 못했을 거라는 생각이 들어 더 하길 잘했다는 생각이 들었다!!

 

그래서 이번 1주차는 문제 풀이뿐만 아니라, 내가 문제를 풀면서 새롭게 알게된 C++에서 시간 제한이 있을 때 사용하면 좋은 코드들도 작성해보려 한다!

 

스따뚜~ ♡(˶╹̆ ▿╹̆˵)و✧♡

 

C++에서 시간 제한이 있을 때 활용하면 좋은 코드들

 

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

 

백준에서 기본으로 제공하는 입출력 방식은 느린 편이라서 이 코드로 바꿔주면 속도가 확실히 빨라진다!

 

• ios::sync_with_stdio(false); → C의 stdio랑 C++의 iostream을 동기화하지 않게 해서 속도를 올려준다.
• cin.tie(NULL); → cin과 cout의 묶임을 풀어서 입출력 시간을 줄여준다.
• 💡 주의: scanf, printf 랑 같이 쓰지 않기!

cout << "Hello World!" << endl;  // 느림 (버퍼를 매번 비워서 출력함)
cout << "Hello World!" << "\n";      // 빠름 (버퍼에 넣었다가 한 번에 출력함)

 

endl 사용 자제하기! ( endl 대신 '\n' 사용하기 )

• endl은 버퍼를 비우는 작업을 포함하기 때문에 시간이 많이 걸릴 수 있다.
• 따라서, 출력이 많을 때는 '\n'으로 대체하는 것이 좋다!

 

백준 2869번 : 달팽이는 올라가고 싶다

 

달팽이가 높이가 v미터인 나무 막대를 올라가는데, 낮에는 a미터 올라가고, 밤에는 b미터 미끄러진다. 정상에 올라간 후에는 미끄러지지 않고 달팽이가 나무 막대를 모두 올라가는데 며칠이 걸리는지 구하는 문제이다. 

 

처음에는 무한루프 반복문을 사용하여 이렇게 문제를 풀었다. 

#include<iostream>
using namespace std;

int main(){
    
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int a, b, v;
    cin >> a >> b >> v;
    int height = 0, day = 0;
    
    while(true)
    {
        height += a;
        day++;
        
        if(height >= v)
        {
            cout << day;
            break;
        }
        
        height -= b;
    }
    
}

 

그런데 시간초과가 떴다 ㅠㅠ

 

그래서 시간 초과 원인을 분석해보았다...!!

 

1. 반복문의 사용방식

무한루프를 사용했고 이 방식은 높이를 1일씩 계속 증가시키면서 체크하는 방법이다. 예를 들어, 높이가 1억정도라면, 매일 A-B만큼의 이동을 계산해서 반복을 돌리기 때문에 시간이 엄청 오래 걸리게 된다.

 

2. 높이를 매일 1일씩 직접 계산

매일 낮에는 a만큼 올라가고, 밤에는 b만큼 미끄러져서 실제로는 a-b만큼만 전진하는 셈이다. 근데 이걸 하나하나 다 계산하고 있으니 느리게 처리된다.

 

이러한 이유로, 반복문을 통해 매일 조금씩 계산하지 않고, 수학적인 계산으로 다시 풀어 보았다.

 

도착하기 전까지 필요한 높이 = V-A

하루에 실질적으로 올라가는 높이 = A-B

따라서, 필요한 날 수 = ( V-A ) / ( A-B ) + 1 이다.

또한, 나머지가 생긴다면, 하루 더 필요하게 된다!

 

따라서 최종 코드는 이렇게 수정되었다!

 

#include<iostream>
using namespace std;

int main(){
    
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int A, B, V;
    cin >> A >> B >> V;
    
    // 정상에 도달하기 전까지 필요한 일수 계산
    int days = (V - B - 1) / (A - B) + 1;
    
    // 결과 출력
    cout << days;

    return 0;
}

 

 

 

이 문제를 풀면서 반복문으로 접근하면 시간 초과가 발생할 수 있다는 걸 확실히 느꼈다. 또한, 수학적으로 접근해서 문제를 해결하는 것도 유리한 경우가 있으니 중요하다는 생각이 들었다. 코알라 1주차 공부를 하면서 내가 너무 몰랐던 것들이 많다는 걸 새삼 깨달았다. 앞으로 비슷한 문제를 만나도 주어진 제한 사항을 잘 고려하면서 코드를 작성할 수 있도록 더 많이 고민하고 공부해야 겠다는 다짐을 했다. 문제를 푸는 것도 중요하지만, 그 과정에서 효율적인 방법을 찾기 위해 고민하고 학습하는 게 진짜 중요한 것 같다!!! 다음주에는 더 열심히 해야징~!

 

 

-1주차 끗 (●ˇ∀ˇ●)-