📖저자님의 책 소개 영상: 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

2. N-퀸

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

def dfs(queen, row, n):
    count = 0
    if n == row:
        return 1
    for col in range(n):
        queen[row] = col
        for i in range(row):
            if queen[i] == queen[row]:
                break
            if abs(queen[i]-queen[row]) == row - i:
                break
        else:
            count += dfs(queen, row + 1, n)
    return count
def solution(n):
    return dfs([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