key idea

• 이진 트리에서 트리를 순회한다는 것은 어떤 루트를 기준으로 왼쪽 서브트리 / 오른쪽 서브 트리 / 그 루트의 순서를 정의한다. 라는 의미이다.
• 따라서 트리의 순회에서 중요한 것은 왼쪽과 오른쪽 서브트리의 기준을 어떻게 잡느냐? 이고, 그에 맞추어서 트리를 정의할 수 있다.
• 예를 들어 pre_order 로 탐색한 트리의 경우 항상 루트가 맨 앞에 오는 R[l...r] 의 형태, post_order의 경우 항상 루트가 맨 뒤에 오는 [l...r]R의 형태가 될 수도 있다.
• 이 후, recursion 을 이용하여 말 그대로 트리를 탐색하면 된다.

관련 코드

# pre_order 은 항상 가장 앞에 있는 원소가 root 인 성질이 있음
# Root[l .... r] 형태의 트리를 postorder로 순회하는 함수
def post_order(tree, l, r):
    # 왼쪽 subtree와 오른쪽 subtree를 나눈다.
    if l > r:
        return ""

    root = tree[l]
    right_subtree_start = next((i for i in range(l + 1, r + 1) if tree[i] > root), r + 1)

    left = post_order(tree, l + 1, right_subtree_start - 1)
    right = post_order(tree, right_subtree_start, r)

    return left + right + f"{root}\n"

집합 연산

• 관련 문제 : https://www.acmicpc.net/problem/1764

• <algorithm> 헤더의 set_intersection 등의 함수를 이용하여 집합 연산을 할 수 있다. (비슷하게 set_union, set_difference, set_symmetric_difference가 존재함)

• 이 함수를 사용하면 결과값 배열의 iterator가 반환된다.

  • 다음과 같은 형태로 사용한다.

    result.resize(s1.size() + s2.size()); // 결과 배열에 먼저 공간을 확보해야 한다.
    auto it = set_intersection(s1.begin(), s1.end(), s2,begin(), s2.end(), result.begin());
    result.erase(it, result.end()); // 남은 공간을 제거한다.

• 이러한 집합 연산의 경우, 컨테이너가 벡터여도 사용이 가능하지만 각 컨테이너들이 정렬되어 있어야 한다.

• https://www.acmicpc.net/problem/2179

split() 내부에는 정규표현식이 들어가기 때문에
. 같은거 쓸떄는 escape 처리를 해줘야 한다.

예시 : String[] v2 = version2.split("\\.");

c++의 경우, int 와 int 의 계산에서 int로 cast되면서 소숫점이 다 버려지면서 부정확하게 계산될 수 있다.
따라서 정확하게 연산을 하기 위해여 나누는 수 중 하나를 double로 static cast 해주어야 한다.

• 예시

// 산술 평균
int getAvg() {
  int sum = 0;

  for (auto number : numbers) {
    sum += number;
  }

  int avg = round(sum / (double)n);

  return avg;
}

sys.setrecursionlimit 을 할 때, 먼저 최악의 경우를 계산해보고 인자를 작성해야 한다! (항상 최악의 경우와 비교해봐야 한다.)

관련 문제
https://www.acmicpc.net/problem/15900

• 전처리를 통하여 O(1)에 부분 배열의 합을 구하는 테크닉
• pSum[x] 를 앞에서부터 x개 원소의 합이라고 정의
• [l ,r]로 구간이 주어진다면 구간합은 pSum[r] - pSum[l - 1]로 정의할 수 있다.
  • 이 때, 작은 구간의 경우 l- 1임을 유의한다. (2차원 배열에서도 똑같음)

관련 문제

https://www.acmicpc.net/workbook/view/11438

https://www.acmicpc.net/board/view/83176

BackTracking 에서 해를 하나만 찾기

스도쿠 문제에서 스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다 는 조건에 의해 백트래킹을 이용하여 스도쿠 판을 채우면서 답을 찾으면 함수를 종료해야 한다.

이는 backtracking 함수에서 반환값을 bool 타입으로 설정하고,
답을 찾은 경우 true, 답을 찾지 못한 경우 false를 리턴하여 구현할 수 있다.

코드

• 참고

// TODO: 첫 번재 답을 찾은 후 백트래킹을 중단해야 한다.
// 답을 찾으면 true를 반환한다.
bool backtracking(int idx) {
  // 종료 조건 : 빈칸이 모두 채워진 경우
  if (idx == blanks.size()) {
    printBoard();
    return true;  // 답을 찾음
  }

  pair<int, int> current = blanks[idx];

  // 빈칸에 1 ~ 9까지의 숫자를 모두 대입한다.
  for (int i = 1; i <= 9; i++) {
    if (!row[current.X][i] && !col[current.Y][i] &&
        !square[(current.X / 3) * 3 + (current.Y / 3)][i]) {
      board[current.X][current.Y] = i;
      row[current.X][i] = true;
      col[current.Y][i] = true;
      square[(current.X / 3) * 3 + (current.Y / 3)][i] = true;

      if (backtracking(idx + 1)) return true;  // 답을 찾으면 백트래킹을 중단한다.

      board[current.X][current.Y] = 0;
      row[current.X][i] = false;
      col[current.Y][i] = false;
      square[(current.X / 3) * 3 + (current.Y / 3)][i] = false;
    }
  }

  // 이 경로에서는 해를 찾지 못함
  return false;
}

cf) exit(0)과 같은 시스템 콜 함수를 이용하여, 답을 찾는 순간 프로그램을 강제로 종료할 수도 있다.

관련 문제

https://www.acmicpc.net/problem/9372