해 구성하기 (Constructive)

정의

해 구성하기 (Constructive Algorithm) 는 답의 존재를 증명하는 대신, 명시적으로 답을 만드는 문제 유형.

“가능한가?” → YES/NO 가 아니라, “가능하다면 그 예시를 하나 만들어라” 가 출력.

수학의 구성적 증명 (constructive proof) 과 동일. 존재성 정리 (존재한다는 증명) 보다 구체 알고리즘을 요구.

문제 상황과 동기

문제: “조건 C 를 만족하는 수열/배치/그래프를 하나 만들어라. 없으면 -1.”

• naive: 모든 가능한 배치를 브루트포스 (O(N!) 또는 O(2^N)).
• constructive: 조건 분석 → 그리디 / 재귀 / 역산으로 O(N)~O(N log N) 구성.

핵심 통찰: “불가능 조건”을 먼저 제거하고, 가능한 경우 단계적 구성.

자주 등장하는 PS 위치:

• Balanced parentheses 생성
• Matching / Pairing 문제
• Magic square / Latin square 구성
• 그래프 간선 추가로 조건 만족

실무:

• 테스트 케이스 자동 생성 (fuzzer, random testing)
• 스케줄링 (과제 배치, 시프트)

시각화

핵심 아이디어

invariant: 단계마다 조건을 유지하며 확장.

대표 패턴:

1. 그리디 구성: 각 단계마다 지역 최적 선택.
2. 재귀 분할: 작은 부분 문제 해결 후 합치기.
3. 역산: 목표 상태에서 거꾸로 역추적.
4. 대칭/패턴: 규칙적 배치 (예: 대각선, 회전).
5. 불변량 유지: 각 단계에서 조건 검증.

알고리즘

constructive(conditions):
    if impossible(conditions):
        return -1
    result = []
    while not complete(result):
        next_element = choose_next(result, conditions)
        result.append(next_element)
        if violates(result, conditions):
            backtrack or fail
    return result

구현

예제 1: Balanced Parentheses 생성

N쌍의 괄호로 올바른 괄호 문자열 하나 만들기.

관찰: 여는 괄호 N개, 닫는 괄호 N개. 항상 (왼쪽 누적 ≥ 오른쪽 누적).

// N쌍 괄호, 가장 간단한 구성: (((...)))
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n; cin >> n;
  string s(n, '(');
  s += string(n, ')');
  cout << s << "\n";
}

# 가장 단순한 구성, O(N)
n = int(input())
print('(' * n + ')' * n)

// StringBuilder 로 O(N)
import java.util.*;
public class Main {
  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      StringBuilder sb = new StringBuilder();
      for (int i = 0; i < n; i++) sb.append('(');
      for (int i = 0; i < n; i++) sb.append(')');
      System.out.println(sb);
  }
}

3

((()))

5

((((()))))

예제 2: 1~N 순열, 인접 차이 ≥ 2

N개 수 1,2,…,N 을 배치하되, 인접한 두 수의 차이가 2 이상이어야 함.

관찰: N=1,2 는 불가능 (1,2 인접하면 차이=1). N≥3 이면 홀수-짝수 분리 배치 (1,3,5,…,2,4,6,…) 가 해.

// 홀수-짝수 구성, O(N)
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n; cin >> n;
  if (n <= 2) {
      cout << "-1\n";
      return 0;
  }
  vector<int> ans;
  for (int i = 1; i <= n; i += 2) ans.push_back(i);
  for (int i = 2; i <= n; i += 2) ans.push_back(i);
  for (int v : ans) cout << v << " ";
  cout << "\n";
}

# range 로 홀수/짝수, O(N)
n = int(input())
if n ≤ 2:
  print(-1)
else:
  odd = list(range(1, n+1, 2))
  even = list(range(2, n+1, 2))
  print(" ".join(map(str, odd + even)))

2

-1

5

1 3 5 2 4

예제 3: Magic Square 3×3 (합=15)

3×3 격자에 1~9 를 배치, 모든 행/열/대각선 합=15.

관찰: 중앙=5, 나머지 대칭 배치. 2,4,6,8 모서리, 1,3,7,9 코너.

// 3×3 매직 스퀘어 고정 배치, O(1)
#include <bits/stdc++.h>
using namespace std;
int main() {
  int grid[3][3] = {
      {2, 7, 6},
      {9, 5, 1},
      {4, 3, 8}
  };
  for (int i = 0; i < 3; i++) {
      for (int j = 0; j < 3; j++)
          cout << grid[i][j] << " ";
      cout << "\n";
  }
}

# 3×3 매직 스퀘어, O(1)
grid = [
  [2, 7, 6],
  [9, 5, 1],
  [4, 3, 8]
]
for row in grid:
  print(" ".join(map(str, row)))

2 7 6
9 5 1
4 3 8

복잡도

변형

함정

1. 불가능 조건 누락

“항상 가능” 이라 가정했는데 반례 존재. 불가능 케이스 먼저 처리 (if N < threshold: return -1).

2. 부분 조건 위반

각 단계에서 조건 만족했지만, 최종 결과가 전체 조건 위반. 예: 괄호 생성 중 중간에 닫는 괄호가 여는 괄호보다 많음.

3. 중복 제거 미흡

같은 원소를 여러 번 사용 (순열에서 중복). set 또는 used[] 배열로 관리.

4. 오프바이원 (off-by-one)

1-indexed vs 0-indexed, inclusive vs exclusive. 배열 범위 검증 필수.

BOJ 연습 문제

참고

• 애드 혹 (관찰 트릭)
• 그리디 (지역 최적)
• 백트래킹 (조건 위반시 되돌리기)
• 케이스 워크 (경우 분류)