알고리즘 문제풀이 전 코드 작성 요령

코딩테스트 코드 작성 팁

• 코딩테스트와 개발은 다르다.
  
  
• 남들이 보기 편한 클린코드가 아닌 가장 빠르게 풀 수 있도록 짜는 것이 훨씬 중요하다.
  
  
• 출력 맨 마지막 공백 or 줄바꿈이 추가로 있어도 상관이 없다.
  
  
• 디버거는 사용하지 않는다. 차라리 중간에 변수를 확인하고 싶다면 printf나 cout으로 확인한다. 
  
  
• endl은 죽어도 쓰지 마라!!!
  endl은 개행문자('\n')을 출력하고 출력 버퍼를 비우라는 명령어이다. 
  온라인 저지 채점은 출력값만 확인하기 때문에 버퍼를 매번 비워줄 필요가 없다. (시간낭비)
  
  
• #include<bits/stdc++.h> 선언
  vscode에서만 쓸 수 있는 구현에 필요한 헤더들을 다 인클루드해 놓은 헤더이다.
  #include<iostream>
  #include<string>
  #include<map>
  #include<set>
  #include<stack>
  #include<vector>
  #include<functional>
  #include<algorithm>
  
  

 

표준 입출력

scanf, printf에서 단 한가지 아쉬운 점이라면, C++ string을 처리할 수 없다는 것이다.

 

printf()로 string 출력 예시

#include<stdio.h>
#include<iostream>
using namespace std;

int main(){
    string s = "baaa";
    printf("s is %s\n", s);
}

//실행 결과 => s is ?

 

scanf, printf를 쓰면서 C++ string을 활용한 예시

  ☞ 일단 char*로 입력을 받고 string으로 형변환해서 원하는 작업을 다 끝낸 후 다시 c_str()을 이용해 출력

#include<stdio.h>

int main(){
    char a[10];
    printf("input : ");
    scanf("%s", a);
    string s(a);  // 혹은 string s = a;
    printf("a is %\n", a);
    printf("s is %s\n", s.c_str());
}

/*
실행 결과
input : test
a is test
s is test
*/

 

 

cin, cout을 쓸 때 주의사항

scanf, printf를 쓸 때는 신경쓰지 않아도 되는데 cin,cout을 쓸 때는 주의해야 할 부분이 있다.
scanf, printf와는 달리 cin, cout은 입출력으로 인한 시간초과를 막기 위해
ios::sync_with_stdio(0), cin.tie(0)이라는 두 명령을 실행시켜야 한다. 
위 두개를 실행해주지 않으면 입출력의 양이 많을 때 시간초과가 날 수 있다.

기본적으로 scanf, printf에 쓰는 C stream과 cin, cout에서 쓰는 C++ stream은 분리되어있다.

하지만 코드의 흐름과 실제 출력이 동일하도록 하기 위해 기본적으로 프로그램은 C와 C++ stream을
동기화하고 있다. 아래와 같은 코드가 순서대로 잘 출력되는 이유는 이처럼 동기화가 되어 있기 때문이다.

#include<stdio.h>
#include<iostream>
using namespace std;

int main(){
    cout << "11111\n";
    printf("22222\n");
    cout << "33333\n";
}

 

 

만약 내가 C++ stream만 쓸거라면 굳이 쓸데없는 시간을 잡아먹으면서 두 stream을 동기화 할 필요가 있을까?
=> 그래서 필요한 것이 sync_with_stdio(0)이다.

 

ios::syn_with_stdio(0)

• C stream과 C++ stream의 동기화를 끊는다.
• 이걸 사용하면 동기화를 끊었기 때문에 절대 cout과 printf()를 섞어쓰면 안 된다.
• 동기화 작업이 없으므로 프로그램 수행 시간에서 이득
• 인자를 엄밀히 하자면 bool type이라 false가 맞는데 0이 더 짧으니 0으로 써도 된다

 

스트림 버퍼

 

 

스트림은 키보드로 받은 입력을 바로 콘솔에 넘기지 않고 버퍼에서 어느 정도 모았다가 보낸다.

하지만 입력과 출력이 번갈아 가면서 나오고 그 값들이 화면에 다 보여질 경우 버퍼의 존재로 인해 화면에 출력되는
순서가 꼬일 수 있다. 
=> 그래서 필요한 것이 cin.tie(0)이다.

오른쪽 콘솔 => 출력 순서가 꼬인 경우

 

#include<iostream>
using namespace std;

int main(){
    for(int i = 0; i < 3; i++){
    	int a,b;
        cin >> a >> b;
        cout << a + b << "\n";
    }
}

위 코드를 보면 3번에 걸쳐 두 수를 입력받고 합을 출력한다. 우리는 당연히 순서대로 출력되길 바란다.
하지만 입력 두개를 받은 후 바로 출력되지 않고 버퍼에 들어있다가 다음 숫자 2개를 입력한 후에 출력이 되버리면
순서가 꼬일 것이다. 이런 현상을 막기 위해 프로그램은 기본적으로 cin 명령을 수행하기 전 cout 버퍼를 자동으로
비워준다. 하지만 온라인 저지 사이트의 채점 형태는 입력이랑 출력이 순서가 꼬이게 콘솔에 나타나더라도 출력들만
확인하기 때문에 틀리지 않는다. 그래서 cin 명령을 수행하기 전에 cout버퍼를 비울 필요가 없다. 
이 때 cout버퍼를 비우지 않도록 하는 코드가 cin.tie(0)인 것이다.

 

 

STL을 함수 인자로 넘길 때

#include<iostream>
using namespace std;

void func1(vector<int> v){
	v[10] = 7;
}

int main(){
    vector<int> v(100);
    func1(v);
    cout << v[10];
}

STL을 함수 인자로 그대로 보내면 복사본을 만들어서 보낸다. 그렇기 때문에 원본에 영향이 없다.

 

또 다른 경우를 보자.

bool cmp1(vector<int> v1, vector<int> v2, int idx){
	return v1[idx] > v2[idx];
}

위의 cmp1()의 시간 복잡도는 어떻게 될까? 바로 O(N)이다. 응? 함수 내부에서 연산이 1번 뿐인데 어떻게 O(N)이냐고
할 수 있는데, 그것은 인자를 보낼 때 원본의 복사본을 만드는 비용을 간과한 것이다.
=> 즉, 위에서 v1의 원소는 n개이고 v2의 원소도 n개라고 한다면 총 2n만큼 복사되므로 시간복잡도가 O(N)인 것이다.

 

이런 경우 STL을 참조를 사용해 함수 인자로 전달하면 시간낭비 문제가 해결된다.

bool cmp2(vector<int>& v1, vector<int>& v2, int idx){
	return vi[idx] > v2[idx];
}

 이렇게 참조로 전달하면 시간복잡도가 O(1)이 된다.

 

 

예시) 전달받은 두 수의 값을 바꾸는 함수

 

참고

바킹독 알고리즘 강의