문제 풀이를 위한 프로그래밍 기법 - 1. 언어적 특성

알고리즘 문제 풀이를 위한 프로그래밍 기법에 대해 간단히 정리해보고자 한다.

단순 입/출력에서도 어떤 함수를 써야 실행 시간이 조금이라도 짧아질 수 있는지 알아보자.

#include <bits/stdc++.h>

using namespace std;

int main() {
    // 이 부분에 원하는 코드
}

#include <bits/stdc++.h>는 표준 라이브러리 전체를 포함시키는 g++ 컴파일러의 기능이다.

iosttream, vector, algorithm 등의 라이브러리를 개별적으로 포함시키지 않아도 자동으로 사용할 수 있게 된다.

 

작성된 소스 코드의 컴파일은 터미널에서 아래와 같은 명령어로 컴파일한다.

g++ -std=c++11 -02 -Wall test.cpp -o test

컴파일러는 c++11 표준을 따르고(-std=c++11) 코드를 최적화 하며(-02), 발생할 수 있는 오류에 대해서 경고를 띄워주는 (-Wall)명령어이다.

 

입력과 출력

C++ 표준 스트림에서 입력은 cin이고 출력은 cout이다. 물론 scanf, printf도 사용할 수 있다.

공백 문자와 개행 문자로 구분된 문자열 및 수를 입력받으려면 아래처럼 하면된다.

int a, b;
string x;
cin >> a >> b >> x;

1) 공백 문자만 존재

123 456 abc

2) 공백 문자와 개행 문자가 모두 존재

123    456

abc

 

코드 시작 부분에 아래와 같은 코드를 추가하면 입력과 출력을 좀 더 효율적으로 할 수 있게 된다.

ios::sync_with_stdio(0);
cin.tie(0);

하지만 위 두 줄을 사용하면 C언어 입출력 함수를 C++ 입출력 함수와 동시에 사용할 수 없다.

또한 \n이 endl 보다 빠르다는 점에 유의해야 한다. endl을 사용하면 flush 작업이 이루어지기 때문이다.

 

몇몇 시스템에서는 파일을 통해 입력하고 출력하는 경우도 있을 수 있다.

이 때에는 아래 두 줄을 코드의 시작 부분에 추가하면 된다.

freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);

위 코드를 추가하면 input.txt에서 입력을 읽어들이게 되며 output.txt로 출력을 저장할 수 있게 된다.

 

수를 처리하는 방법

정수

알고리즘 문제에서 가장 많이 사용되는 정수 자료형은 int이다. int는 32bit 자료형이고 -2^31 ~ 2^31 -1 사이의 범위를 가지고 있는 자료형이다.

만약 int로 부족하다면 long long을 사용하면 된다. long long은 64Bit 자료형이다.

long long x = 123456789123456789LL;

우리는 보통 사소한 실수로 인해 원하는 값을 얻지 못하는 경우도 많다. 

예를 들어 다음과 같은 경우이다.

int a = 123456789;
long long b = a * a;
cout << b << "\n"; // -1757895751

분명히 long long 형 변수에 값을 넣었는데 왜 오버플로우가 발생할까?? 라고 생각할 것이다.

이유는 간단하다. 바로 a * a가 int * int이기 때문에 int형으로 계산이 되어 오버플로우가 난 것이다.

해결방법은 (long long)a * a 이렇게 바꾸면 된다.

 

나머지 연산

나머지 연산에 있어서 중요한 성질은 다음과 같은 공식이 성립한다는 것이다.

(a + b) mod m = (a mod m + b mod m) mod m
(a - b) mod m = (a mod m - b mod m) mod m
(a * b) mod m = (a mod m * b mod m) mod m

그렇기 때문에 마지막에 연산을 하는것이 아니라 매 번 나머지 연산을 해주면서 값의 크기를 줄여주면 값이 매우 커지는 경우를 방지할 수 있게 된다.

예를 들어, 다음 코드는 n 팩토리얼을 m으로 나눈 나머지는 구하는 코드이다.

long long x = 1;
for (int i = 1; i <= n; i++) {
    x = (x * i) % m;
}
cout << x << "\n";

일반적으로 우리는 나머지 값이 0~m-1 안에 있기를 바라지만 문제를 풀다보면 음수의 나머지를 0이나 음수로 처리하는 경우도 있다. 나머지가 음수가 되지 않도록 하는 간단한 방법은 우선 평소대로 나머지 연산을 한 후에 그 결과가 음수라면 m을 더해주는 것이다.

x = x % m;
if(x > 0) x += m;

부동 소수점 실수

부동 소수점의 소수점 표현은 아래와 같이 한다.

이 정도는 1학년 때 다 배웠을 것이라고 생각한다.

double x = 0.3 * 3 + 0.1;
printf("%.20f\n", x);

부동 소수점 실수를 비교할 때 ==를 쓰는 것은 위험하다. 정밀도 오류로 인해 다르다는 결과가 나올 가능성이 있기 때문이다. 따라서 좀 더 나은 방법은 두 실수의 차이가 10^-9보다 작을 때 서로 일치한다고 판단하는 것이다.

if (abs(a-b) < 1e-9) {
    // a와 b가 일치한다.
}

코드 짧게 만들기

자료형

typedef 명령어를 이용하면 자료형의 이름을 좀 더 짧게 만들 수 있다. 예를 들어 long long은 너무 길기 때문에 다음과 같이 ll로 줄일 수 있다.

typedef long long ll;

복잡한 형태의 자료형에도 typedef 명령어를 사용할 수 있다. 예를 들어 다음 코드는 정수 벡터에 vi라는 이름을, 정수 두 개의 조합(pair)에 pi라는 이름을 붙인다.

typedef vector<int> vi;
typedef pair<int, int> pi;

매크로

매크로는 코드를 컴파일 하기 전에 코드에 포함된 특정 문자열을 다른 문자열로 치환하는 규칙을 의미한다.

C++에서는 #define 지시문을 사용해서 매크로를 지정할 수 있다.

#define F first
#define S second
#define PB push_back
#define MP make_pair

그러면 다음과 같은 코드를

v.push_back(make_pair(y1, x1));
v.push_back(makr_pair(y2, x2));
int d = v[i].first + v[i].second;

다음 처럼 짧게 만들 수 있다.

v.PB(MP(y1, x1));
v.PB(MP(y2, x2));
int d = v[i].F + v[i].S;

매크로에 인자를 줄 수도 있고 이를 이용해 반복문이나 그 밖의 구조문을 짧게 할 수도 있다.

#define REP(i, a, b) for( int i = a; i <= b; i++ )

for ( int i = 1; i <= n; i++ ) {
    search(i);
}

위와 같은 코드를

REP(i, 1, n) {
    search(i);
}

이렇게 짧게 만들 수 있다.