📖저자님의 책 소개 영상: https://www.youtube.com/watch?v=Q13Uj_5bH9M

🗓️TIL (this week I learned)
수 읽기, 정리, 몸풀기 문제1
목 배열, 해시 복습
금 🤔🤔🤔🤔
토 🤔🤔🤔🤔

• 여기는 풀면서 IQ 상승을 노려볼 만한다🤣

12-1 백트래킹과 백트래킹 알고리즘 개념⭐⭐⭐

🔷 백트래킹: 가능성이 없는 곳에서는 되돌아가고 가능성이 있는 곳을 탐색하는 알고리즘

• 핵심: 해가 될 가능성을 판단하는 것
• 유망 함수(promising function):
  - 유망 = 해가 될 가능성이 있다..
• Constraint Satisfaction Problems (제약 충족 문제): 수많은 제약 조건을 충족하는 상태(states)를 찾아내는 수학 문제.
  - ex) 스도쿠, 십자말 풀이, 8퀸 문제, 4색 문제(지도 색칠), 배낭문제, 문자열 파싱, 조합 최적화 등

🔷 N-퀸 문제: $N*N$체스판에 $N$개를 배치했을 때, 퀸을 놓을 수 있는 경우의 수가 몇 개인지를 찾는 게 논점이다.
참고:
https://cs.lmu.edu/~ray/notes/backtracking/
n-queens wiki(en) -> 책 퀸즈 문제 풀이와 코드가 유사함.

• N개 배치를 놓쳐서 며칠 동안 머리를 싸매고 있었다..ㅠㅠㅠㅠㅠ

• 예컨대, 4x4 체스판, 4개의 퀸을 놓을 수 있는 경우의 수는 4x4x4x4=256(완전탐색). 이를 유망함수를 추가해 탐색 대상을 줄여 해를 구할 수 있다. (4-퀸 문제의 해는 2개)
  
  

• n-queens의 해
  

12-2 문제

1. 피로도

https://school.programmers.co.kr/learn/courses/30/lessons/87946

def dfs(cur_k, cnt, dungeons, visited):
    answer_max = cnt
    for i in range(len(dungeons)):
        if cur_k >= dungeons[i][0] and visited[i] == 0:
            visited[i] = 1
            answer_max = max(answer_max, dfs(cur_k - dungeons[i][1], cnt + 1, dungeons, visited))
            visited[i] = 0
    return answer_max
        

def solution(k, dungeons):
    visited = [0]  * len(dungeons)
    answer_max = dfs(k, 0, dungeons, visited)
    return answer_max

순열로도.. (백트래킹은 아님)

import itertools

def solution(k, dungeons):
    max_cnt = 0
    
    for perm in itertools.permutations(dungeons, len(dungeons)):
        cur_k = k
        cnt = 0
        
        for need, cost in perm:
            if cur_k >= need:
                cur_k -= cost
                cnt += 1
            else:
                break
        if cnt > max_cnt:
            max_cnt = cnt
            
        if max_cnt == len(dungeons):
            return max_cnt
    return max_cnt

2. N-퀸

https://school.programmers.co.kr/learn/courses/30/lessons/12952

def backtrack(col_positions, current_row, board_size):
    total_solutions = 0
    if current_row == board_size:
        return 1
    for col in range(board_size):
        col_positions[current_row] = col
        for prev_row in range(current_row):
            same_col = (col_positions[prev_row] == col)
            same_diag = abs(col_positions[prev_row] - col) == current_row - prev_row
            if same_col or same_diag:
                break
        else:
            total_solutions += backtrack(col_positions, current_row + 1, board_size)
    return total_solutions

def solution(n):
    return backtrack([0] * n, 0, n)

3. 양궁대회

https://school.programmers.co.kr/learn/courses/30/lessons/92342

4. 외벽점검(고난이도)

https://school.programmers.co.kr/learn/courses/30/lessons/60062

5. 사라지는 발판(고난이도)

https://school.programmers.co.kr/learn/courses/30/lessons/92345