Tips

Comparator

STL로 정렬할 때, 표준 라이브러리는 비교 함수가 < 연산자 (less) 와 같이 동작한다고 가정한다. less 의 정의는 다음과 같다.

  1. Irreflexivity(비반사성): a < a 는 항상 거짓.
  2. Asymmetry(비대칭성): a < b 이면 not (b < a).
  3. Transitivity(추이성): not (a < b) 이고 not (b < a) 이면 a = b 이다. a = b 이고 b = c 이면 a = c 이다 (transitivity of equivalence).

예를 들어 정수 집합을 정렬하기 위한 다음과 같은 less가 있다고 하자.

bool operator < (const IntSet& a, const IntSet& b) {
  if (isProperSubset(a, b))
    // a가 b의 진부분집합
    return true;
  if (isProperSubset(b, a))
    // 반대로 b가 a의 진부분집합
    return false;
  return false;
}

이 less가 동작하지 않는 이유는 위의 정의에 부합하지 않기 때문이다. 예를 들어 {1}, {2}, {2, 3}이 있을 때, 위의 함수는 {2} < {2, 3}만 참이고 나머지는 모두 거짓으로 계산하는데, 추이성에 따라서 {1} = {2}, {1} = {2, 3} 의 관계가 되어버린다. 그러면 결과적으로 {1} = {2} = {2, 3} 이라는 요상한게 튀어나온다.

따라서 위의 정의에 부합하게 주의해서 작성해야 한다.

bool operator < (const IntSet& a, const InstSet& b) {
  if (a.size() != b.size())
    // a와 b의 크기가 다르면 더 작은 쪽이 앞에 와야 한다
    return a.size() < b.size();
  // 크기가 같은 경우는 사전순으로 비교한다.
  return lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
}

크기가 작은 순으로 앞에 오도록 하고 크기가 같은 경우에만 사전 순으로 비교하면 모든 것이 해결된다. 또 크기가 작은 순으로 앞에 오게끔 하기 때문에 굳이 진부분집합 여부를 확인하지 않아도 된다.

Type Promotion

타입의 크기가 다른 두 변수를 계산할 때 컴파일러가 임의적으로 한 쪽의 타입을 바꿔서 (주로 큰 쪽에 맞추기 때문에 프로모션) 같은 타입으로 만든 후에 계산을 한다. 주로 다음 규칙이 적용된다.

  1. 정수랑 실수일 경우 실수로 맞춘다.
  2. 양쪽 다 정수 또는 실수일 경우 더 큰 쪽으로 맞춘다.
  3. 양쪽 다 int 보다 작은 정수이면 둘다 int 로 맞춘다.
  4. 부호 없는 정수형과 부호 있는 정수형이 섞인 경우: 부호 없는 정수형으로 맞춘다.

다음 예시를 보자.

unsigned char a = 17;
short b = -18;
int c = 2;
unsigned int d = 0;

cout << (a + b) * c + d << endl;

결과는 (17 + (-18)) * 2 + 0 = -2 가 될 것 같지만 실행하면 엄청난 값이 나온다.

  1. unsigned char 와 short 는 둘 다 int 보다 작은 정수형이므로 int 로 프로모션
  2. int 곱하기 int 는 그대로 int
  3. int 와 unsigned int 타입을 계산하므로 부호가 없는 쪽을 따라 unsigned int 가 최종 타입

따라서 되도록이면 unsigned 를 쓰지 말고, 타입을 한 쪽으로 몰아서 생각하는 것이 좋다.

입출력 최적화

입력과 출력을 직접 처리해야 하는 경우에 할 수 있는 최적화다. C 스타일 입출력과 C++ 스타일의 스트림 입출력의 동기화를 끊어서 속도를 빠르게 한다. 대신, 입출력을 할 때 두 가지 스타일 중 하나만 사용해야 한다.

static auto _ = [](){
    // turn off sync
    std::ios::sync_with_stdio(false);
    // untie in/out streams
    std::cin.tie(nullptr);
    return 0;
}();
  • std::ios::sync_with_stdio 는 C 표준 스트림 (stdin, stdout)과 C++ 표준 스트림 (std::cin, std::cout) 사이의 동기화를 끊어서 입출력을 빠르게 한다. 대신 한 쪽 스트림만 써야 안꼬인다.
  • std::cin.tie 는 std::cin 과 std::cout 사이의 동기화를 조절한다. 만약 동기화가 되어 있다면 std::cin 으로 읽기 전에 std::cout 버퍼가 항상 먼저 비워지고 이를 통해 입출력 순서가 유지된다. 동기화를 끄게 되면 이 순서가 보장되지 않기 때문에 입력과 출력의 순서가 맞아야 하는 경우에는 쓰면 안된다.

설명을 보면 알겠지만 문제 풀이 수준에서는 대부분 두 동기화를 모두 꺼도 괜찮다.

람다 인라이닝

여러 번 쓰이는 짧은 불변식 체크 로직은 함수로 빼면 좋다. 그런데 문제에 따라서 이 함수가 클로저면 편한 경우가 많아서 (예를 들어 그래프 탐색에서 맵 정보나 방문 정보를 공유하기 편함), 람다로 몽땅 캡쳐해서 쓰면 좋다. 그런데 람다는 (일반 함수와 마찬가지로) 기본적으로 인라인이 안된다. 최적화 플래그를 킨다면 인라인이 되겠지만 최적화 플래그를 못 키는 경우에는 다음 어트리뷰트 문법을 사용하면 좋다.

auto skip = [&] (int y, int x) __attribute__((always_inline)) {
  return !(0 <= y && y < m) || !(0 <= x && x < n) || visited[y][x] || map[y][x] == '0';
}

__attribute__ 의 위치에 주의하자. 함수 선언이라면 리턴 타입 뒤에 와야 하지만 람다식의 경우 파라미터 뒤에 와야 한다.

원형 큐 마이크로 최적화

원형 큐가 필요한 경우 정말 복잡한 데이터가 아니라면 std::queue<> 를 가져다 쓰기 보다는 그냥 배열과 head, tail 인덱스를 유지하는게 훨씬 편하다. 이때 인덱스가 오버플로우났을 때 다시 0으로 만드는 방법은 세 가지가 있다.

  1. 모듈러 연산 head = (head + 1) % SIZE : 모듈러는 나누기 연산과 비슷한 비용이 들어가서 별로 좋지 않다.
  2. 매번 오버플로우 검사하기 head++; if (head == SIZE) head = 0; : 그나마 이게 모듈러보단 낫지만 그래도 매번 분기문이 들어가기 때문에 최적이라고 할 순 없다.

그리고 마지막 세 번째 방법은 한정된 경우에서만 쓸 수 있는 트릭인데 바로 비트 연산을 이용하는 것이다 (사실 대부분의 마이크로 최적화는 비트 연산을 가지고 요리조리 하다가 나오는 것 같다). 모듈러는 아예 쳐다봐서도 안되고, 분기문도 되도록 피하고 싶으면 고려해보자.

먼저 SIZE 를 적당히 늘려서 2의 배수로 만든다. 그러면 이 값은 항상 0b10000...00 의 비트를 갖게 된다. 우리가 하고 싶은 것은 헤드나 테일 인덱스가 이 값을 넘치는 순간 값을 다시 0으로 초기화 하고 싶은 것이다. 이를 조금 다르게 표현하면, SIZE 에서 1이 있는 곳을 제외한 나머지 오른쪽 부분을 지워버리면 된다. (참조) 따라서 SIZE - 1 과 And 연산을 하면 된다.

const int SIZE = 1 << 20; // 적당히 문제 조건 보다 큰 값으로
const int MASK = (SIZE - 1);
...

int head = 0, tail = 0;

...

while (head != tail) {
  ...
  head++;
  head &= MASK;

  ...
  tail++;
  tail &= MASK;
}
Last Update: 2023-04-07 05:18:27 PM