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

import sys

for _ in range(int(input())):
    n = int(sys.stdin.readline())
    flag = "YES"
    li = []
    for _ in range(n):
        li.append(sys.stdin.readline().rstrip('\n'))

    li.sort()
    for i, j in zip(li, li[1:]):
        if i == j[:len(i)]:
            flag = "NO"

    print(flag)

from collections import deque

def bfs():
    q = deque([n])
    while q:
        x = q.popleft()
        if x == k:
            return array[x]
        for nx in (x-1, x+1, 2*x):
            if 0 <= nx < MAX and not array[nx]:
                if nx == 2*x and x != 0:
                    array[nx] = array[x] 
                    q.appendleft(nx) # 2*X 가 더 높은 우선순위를 가지기 위함
                else:
                    array[nx] = array[x] + 1
                    q.append(nx)
    
MAX = 100001
n, k = map(int, input().split())
array = [0] * MAX
print(bfs())

x= input()
y= input()

dp = [[0] * (len(y)+1) for _ in range(len(x)+1)]

for i in range(1, len(x)+1):
    for j in range(1, len(y)+1):
        if x[i-1]==y[j-1]:
            dp[i][j] = dp[i-1][j-1] +1
        else:
            dp[i][j] = max(dp[i][j-1], dp[i-1][j])

print(dp[len(x)][len(y)])

import sys 
import heapq

max_heap = []
min_heap = []

for _ in range(int(input())):
    num = int(sys.stdin.readline())
    if len(max_heap) == len(min_heap):
        heapq.heappush(max_heap, (-num, num))
    else:
        heapq.heappush(min_heap, (num, num))

    if min_heap and max_heap[0][1] > min_heap[0][1]:
        max_value = heapq.heappop(max_heap)[1]
        min_value = heapq.heappop(min_heap)[1]
        heapq.heappush(min_heap, (max_value, max_value))
        heapq.heappush(max_heap, (-min_value, min_value))

    print(max_heap[0][1])

백 트래킹 (bakctracking)

• 제약 조건 만족 문제에서 해를 찾기 위한 전략
  • 해를 찾기 위해, 후보군에 제약 조건을 점진적으로 체크하다가, 해당 후보군이 제약 조건을 만족할 수 없다고 판단한 즉시 backtrack (다시는 이 후보군을 체크하지 않을 것을 표기)하고, 바로 다음 후보군으로 넘어가, 최적의 해를 찾는 방법
• 실제 구현시, 고려할 수 있는 모든 경우의 수(후보군)을 상태공간트리(State Space Tree)를 통해 표현
  • 각 후보군을 DFS 방식으로 확인
  • 상태 공간 트리를 탐색하면서, 제약 조건에 맞지 않으면 해의 후보가 될만한 곳으로 바로 넘어가서 탐색
    • Promising : 해당 루트가 조건에 맞는지를 검사하는 기법
    • Pruning (가지치기) : 조건에 맞지 않으면 포기하고 다른 루트로 돌아가서, 탐색의 시간을 절약하는 기법

즉, 백트래킹은 트리 구조를 기반으로 DFS로 깊이 탐색을 진행하며, 각 루트에 대해 조건에 부합하는지 체크(Promising)하고, 만약 해당 서브트리에서 조건에 맞지 않는 노드는 더 이상 DFS로 깊이 탐색을 진행하지 않고, 가지를 치는 것(Pruning)

상태 공간 트리(State Space Tree)

문제 해결 과정의 중간 상태를 각각의 노드로 나타낸 트리

N Queen

• 대표적인 백트래킹 문제
• NxN 크기의 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치하는 문제
• 퀸은 수직, 수평, 대각선 이동(공격) 가능, 따라서 다음과 같이 배치해야 한다
  

Pruning for N Queen

• 한 행에는 하나의 퀸만 위치 가능
• 맨 위 행부터 퀸 배치, 그리고 다음 행에 퀸이 위치 가능한 곳 찾아 퀸 배치
• 만약, 앞선 행의 퀸으로 인해, 다음 행에 퀸이 가능한 위치가 없을 경우, 이전 행의 퀸 배치를 바꿈
  • 맨 위 행부터 퀸 배치가 가능한 경우의 수를 상태 공간 트리로 만든 후, 맨 위 행부터 DFS로 접근

Promising for N Queen

• 수직 체크 cur_col-queen_col==0
• 대각선 체크 abs(queen_col-cur_col)==cur_row-queen_row

def is_available(candidate, cur_col):
    cur_row = len(candidate)
    for queen_row in range(cur_row):
        if candidate[queen_row] == cur_col or abs(candidate[queen_row]-cur_col) == cur_row - queen_row:
            return False
    return True

def DFS(N, cur_row, cur_queens, final_result): # cur_queens : 지금까지 배치된 퀸의 정보
    if cur_row == N:
        final_result.append(cur_queens[:]) # [:] == shallow copy
        return 
    for checking_col in range(N):
        if is_available(cur_queens, checking_col):
            cur_queens.append(checking_col)
            DFS(N, cur_row+1, cur_queens, final_result)
            cur_queens.pop()

def solve_n_queens(N):
    final_result = []
    DFS(N, 0, [],final_result)
    return final_result

DFS, BFS with Python

• N X M 의 배열에서 N,M이 대개 10000~100000 사이의 범위

• 여러 개의 정점이 연결되어 있는 형태로 나올 때 활용

• 간선 개수가 작을 때는 DFS로 재귀함수 활용 가능 (or sys.setrecursionlimit() 설정)

• 간선 개수가 많을 떄는 BFS. 그래도 느리다면 백준 알고리즘 같은 경우 Pypy3 로 채점 시도 해볼 것

해당 문제

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

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

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

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

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