Coding Test

coding_test.md

Coding Test

Tips

• 문제를 잘 읽자! 특히 범위나 가능 여부가 주어지는 경우 주의
  • e.g. 필요한 경우, 최대로 가능 깊이는
• 입출력이 많은 경우 printf/scanf 혹은 ios::sync_with_stdio(false);를 사용한다
• 공백이 없는 입력값은 한 줄 전체를 string으로 입력 받는 것을 고려한다
• N ≤ 10^18 이라면 long long을 써야할 가능성이 높다
• long long 사용 시 중간 계산에 사용되는 값도 long long으로 사용해야 한다
  • e.g. unsigned long long x = 1LL << 10
• (x, y) 좌표계를 사용하는 경우 모든 순서(함수 파라미터, 2차원 배열 참조)는 Y -> X 순서를 사용한다

Snippets

완전 탐색

조합 문제

뽑는 순서가 상관 없는 경우

• 뽑는 순서만 다른 경우를 중복 탐색하지 않으려면 사전순으로 탐색한다(e.g. (0, 1)을 탐색했으면 (1, 0)은 탐색하지 않는다).

int search(int pos, int picked) {
    if (picked == X)
        return; // Do something

    int ret = INF;
    for (int next = pos; next < N; ++next) {
        int tmp = search(next + 1, picked + 1);
        if (tmp < ret)
            ret = tmp;
    }

    return ret;
}

int search(int pos, int picked) {
    if (picked == X)
        return; // Do something

    int ret = INF;

    // 뽑는 경우
    int tmp = search(pos + 1, picked + 1);
    if (tmp < ret)
        ret = tmp;

    // 안뽑는 경우
    tmp2 = search(pos + 1, picked);
    if (tmp < ret)
        ret = tmp;

    return ret;
}

중복 뽑기를 허용하는 경우

int search(int picked) {
    if (picked == X)
        return; // Do something

    int ret = INF;
    for (int next = 0; next < N; ++next) {
        int tmp = search(picked + 1);
        if (tmp < ret)
            ret = tmp;
    }

    return ret;
}

순열 문제

뽑는 순서가 상관 있는 경우

• 순서가 다른 경우도 포함하여 탐색한다(e.g. (0, 1)과 (1, 0)을 모두 탐색). 문제의 크기가 큰 경우 DP를 고려한다.
• 뽑았는지 체크하기 위한 요소를 추가한다.

Boolean 배열

bool Vis[N];

int search() {
    for (0:N)
        return; // Do something

    int ret = INF;
    for (int next = 0; next < N; ++next) {
        if (Vis[next])
            continue;
        Vis[next] = true;
        int tmp = search();
        if (tmp < ret)
            ret = tmp;
        Vis[next] = false;
    }

    return ret;
}

비트마스크

int search(int vis) {
    if (vis == ((0x1 << N) - 1))
        return; // Do something
    
    for (int next = 0; next < N; ++next) {
        int bit = 0x1 << (next - 1);
        if (vis & bit)
            continue;
        int tmp = search(vis | bit);
        if (tmp < ret)
            ret = tmp;
    }
    // ...
}

Stack

int stack[N];
int top = -1;
int elem;

// Push
stack[++top] = elem;

// Pop
elem = stack[top--];

// isEmpty
if (top == -1)

CircularQueue

int que[N];
int front = -1;
int back = -1;
int size = 0;
int elem;

// Enqueue
back = (back + 1) % N;
que[back] = elem;
++size;

// Dequeue
front = (front + 1) % N;
elem = que[front];
--size;

// isEmpty
if (size == 0)

BFS

int P[N][N];

void bfs(int start) {
  bool vis[N] = { false };

  vis[start] = true;
  que.enque(start);

  while (!que.isEmpty()) {
    int cur = que.deque();

    // Do Something

    for (int next = 0; nxt < N; ++next) {
      if (!vis[next] && P[cur][next]) {
        vis[next] = true;
        que.enque(next);
      }
    }
  }
}

Union-Find

int P[N];

void makeSet(int v) {
  P[v] = v;
}

int findSet(int v) {
  if (P[v] != v)
    P[v] = findSet(P[v]);
  return P[v];
}

void unionSet(int u, int v) {
  P[findSet(v)] = findSet(u);
}

그래프 최단거리

BFS

가중치가 없는 그래프의 최단거리

int dist[N];

// 인접 정점을 찾으면 dist[next] = dist[cur] + 1

Djikstra

양수 가중치 그래프에서 Start -> Goal 최단거리

int Dist[N];
int Parent[N];

int djikstra() {
  Dist[Start] = 0;

  while (true) {
    // 방문하지 않은 정점 중 최단거리를 갖는 노드 찾기
    int shortDist = INF;
    int shortest;
    for (int i = 0; i < N; ++i) {
      if (!Vis[i] && Dist[i] < shortDist)
        shortDist = Dist[i];
    }

    // 모든 노드를 방문했으면 종료
    if (shortDist == INF)
      break;

    // 방문 체크
    Vis[shortest] = true;

    // 인접 정점들의 거리 갱신
    for (int next = 0; next < N; ++next) {
      if (!Vis[next])
        Dist[next] = Dist[shortest] + P[shortest][next];
        Parent[next] = shortest; // 경로 저장
    }
  }

  return Dist[Goal];
}

Sort

QuickSort

void quickSort(int first, int last) {
  int pivot;
  int i;
  int j;
  long long temp;

  if (first < last) {
    pivot = first;
    i = first;
    j = last;

    while (i < j) {
      while (P[i] <= P[pivot] && i < last) {
        i++;
      }
      while (P[j] > P[pivot]) {
        j--;
      }
      if (i < j) {
        temp = P[i];
        P[i] = P[j];
        P[j] = temp;
      }
    }

    temp = P[pivot];
    P[pivot] = P[j];
    P[j] = temp;

    quickSort(first, j - 1);
    quickSort(j + 1, last);
  }
}