99클럽 코테 스터디 _ 13일차 TIL (백트래킹)

 

< 문제 >

[백준] 2529. 부등호 / 실버1

---

< 풀이 >

코드 변수 정의

• depth : 현재 선택한 숫자의 개수를 의미하며, k+1개가 되면 종료
• num_list : 현재까지 선택한 숫자들을 저장한 리스트
• min_num, max_num : 반환할 숫자
• num_to_str : 리스트를 문자열로 변환한 값
• visited : 숫자 사용 여부 표시

---

Backtracking
시간복잡도 : O(10!)       *최대 탐색 경우

# x, y가 부등호를 만족하는지 확인하는 함수
def is_valid(x, y, sign):
    return (sign == '<' and x < y) or (sign == '>' and x > y)

# 부등호 조건을 만족하는 최댓값과 최솟값을 찾는 함수
def search(k, inequal):

    # 백트래킹을 이용한 숫자 조합 탐색
    def backtrack(depth, num_list): 
        nonlocal min_num, max_num # 전역 변수

        # 숫자 (k+1)개를 모두 선택한 경우 최댓값과 최솟값을 갱신
        if depth == k + 1:
            num_to_str = ''.join(map(str, num_list)) # 리스트를 문자열로 변환
            min_num = min(min_num, num_to_str)
            max_num = max(max_num, num_to_str)
            return

        # 0 ~ 9까지의 숫자를 확인하며 백트래킹 수행
        for i in range(10):
            if not visited[i]:  # 숫자가 사용되지 않았을 경우
                # 첫 번째 숫자가 아니거나, 부등호 조건을 만족하는 경우 진행
                if depth == 0 or is_valid(num_list[-1], i, inequal[depth - 1]):  
                    visited[i] = True # 숫자 사용 표시
                    backtrack(depth + 1, num_list + [i]) # 다음 숫자 선택
                    visited[i] = False  # 백트래킹 (다른 경우의 수 탐색)

    # 최댓값과 최솟값을 저장할 변수
    min_num, max_num = "9999999999", "0000000000" # 문자열 비교를 위해 최대/최소 초기값 설정
    visited = [False] * 10 # 숫자 사용 여부를 저장하는 배열
    backtrack(0, []) # 백트래킹 시작
    return max_num, min_num

def main():
    k = int(input()) # 부등호 개수
    inequal = list(map(str, input().split())) # 부등호 리스트
    max_num, min_num = search(k, inequal)
    print(max_num)
    print(min_num)

if __name__ == "__main__":
    main()

---

 

 

 

풀이 방식

1. 백트래킹 탐색
   •  
   • 백트래킹을 사용하여 부등호 조건을 만족하는 모든 숫자 조합을 탐색하고, 그 중 최댓값과 최솟값을 찾는다.
   • 백트래킹 탐색 과정_
     1. 종료 조건 : 모든 숫자를 선택한 경우
        • k+1개의 숫자를 모두 선택했다면, 문자열로 변환하여 최솟값과 최댓값을 갱신한다.
     2. 백트래킹을 이용한 탐색
        • 0 ~ 9까지의 숫자를 하나씩 선택하여 백트래킹을 수행한다.
        • 선택된 숫자가 이전에 사용되지 않았는지 visited[i]로 확인한다.
        • depth == 0인 경우에는 부등호 검사를 하지 않고 그냥 선택할 수 있다.
        • depth  != 0인 경우에는 직전 숫자와의 부등호 관계를 is_valid 함수로 확인한다.
        • 조건을 만족하면
          • 해당 숫자를 추가한 뒤 다음 숫자를 선택하는 backtrack()을 재귀 호출한다.
        • 탐색이 끝나면 visited[i] = False로 초기화하여 다른 조합을 탐색할 수 있게 한다.
2. 부등호 비교
   
   • 주어진 두 숫자 x, y가 부등호 조건을 만족하는지 확인한다.
     • < 인 경우  :  x < y 면 True
     • > 인 경우  :  x > y 면 True

---

< 회고 >

 

백트래킹(Backtracking)

 

백트래킹

백트래킹은 재귀적 탐색을 활용하여 모든 경우의 수를 조사한다.

  ✔︎   불가능한 경우는 즉시 탐색을 중단하여 불필요한 연산을 줄인다.

  ✔︎   모든 가능한 해를 고려하면서도 가지치기(Pruning)를 수행하여 탐색 속도를 개선할 수 있다.

 

🔸  백트래킹 활용 문제 유형 예시

• 순열(permutation) / 조합(combination) 문제
• 그래프 탐색 (DFS, N-Queen, 미로 탐색 등)
• 제한 조건을 만족하는 최적해 찾기 (부분집합, 수열 구성 등)

---

백트래킹 동작 방식

백트래킹은 재귀(Recursion)와 조건 검사(Pruning)를 조합하여 작동한다.

 

🔸  기본 동작 흐름

1. 현재 상태에서 가능한 후보군을 선택한다.
2. 후보군이 제한 조건을 만족하는지 검사한다.
   • 만약 조건을 만족하지 않으면 즉시 탐색을 중단한다. (Pruning)
   • 조건을 만족하면 재귀 호출을 통해 다음 후보군을 선택한다.
3. 목표 상태(완전한 해답)를 찾으면 정답을 저장하고 탐색을 종료한다.
4. 탐색이 끝나면 직전 상태로 되돌아가서(Backtrack) 다른 경우를 탐색한다.

🔸  백트랙킹 탐색 예제 (순열)

def backtrack(path, visited):
  if len(path) == N:  # 종료 조건 (모든 숫자를 선택했을 때)
    print(path)
    return
  
  for i in range(N):
    if not visited[i]:  # 아직 선택되지 않은 숫자라면
      visited[i] = True
      backtrack(path + [i], visited)  # 다음 숫자 선택 (재귀 호출)
      visited[i] = False  # 탐색 종료 후 원상 복구 (백트래킹)

---

백트래킹 vs. 완전 탐색(Brute Force)

	완전 탐색(Brute Force)	백트래킹(Backtracking)
탐색 방식	모든 경우의 수를 무식하게 탐색	조건을 만족하는 경우에만 탐색
속도	느림(비효율적)	빠름(Pruning으로 최적화)
적용 문제	작은 범위 (N ≤ 10)	비교적 큰 범위 (N ≤ 15 ~ 20)
예제	모든 가능한 조합 찾기	N-Queen 문제, 미로 탐색

---

백트래킹 활용 예제

🔸   N-Queen 문제 (백트래킹)

def is_valid(board, row, col):
  # 위쪽 행동을 확인하며 같은 열이나 대각선에 퀸이 있는지 체크
  for i in range(row):
    if board[i] == col or abs(board[i] - col) == row - i:
      return False
  return True
  
  def n_queen(board, row, N):
    if row == N:  # 모든 퀸을 배치한 경우
      print(board)  # 가능한 배치 출력
      return
    
    for col in range(N):
      if is_valid(board, row, col):  # 배치 가능 여부 확인
        board[row] = col  # 퀸 배치
        n_queen(board, row+1, N)  # 다음 행으로 이동
        board[row] = -1  # 백트래킹 (되돌리기)

N = 4  # 4 X 4 체스판
board = [-1] * N  # 열 정보를 저장할 리스트
n_queen(board, 0, N)