본문 바로가기

backtracking3

[Python] 백준 9663 N-Queen 🧑‍💻 [Python] 백준 9663 N-Queen Gold 4 - Backtracking Queen은 위, 아래, 오른쪽, 왼쪽, 대각선, 8 방면 모두 공격을 할 수 있다 N이 주어지고, 체스판 사이즈는 N x N 이고, N 개의 Queen을 넣었을 때 서로 공격할 수 없는 때의 경우의 수를 찾는 것 1차적으로 자세히 보면, 각 행과 열마다, Queen은 하나씩 배치할 수 있다 이 뜻은 굳이 체스판 자체를 안 만들어도 된다 board = [0, 3, 1, 4, 2] 아래 사진을 표현한 리스트 (board의 인덱스가 열/row, board의 값이 행/column) board 안에 있는 값들은 모두 달라야 한다 row (board의 인덱스) column (board의 값) 0 0 1 3 2 1 3 4 4.. 2023. 4. 5.
[Python] 백준 15650 N과 M 2 🧑‍💻 [Python] 백준 15650 N과 M 2 Silver 3 - Backtracking 쉽게 itertools의 combinations를 사용해서 풀 수 있는 문제다 하지만 Backtracking을 공부하고 싶어서 풀었던 문제다 기본적으로 if len(nums) == M: 을 통해서 재귀 함수의 base case를 만든다 안 만들면 무한 루프 리스트 안에 for문을 돌며, 나오는 숫자가 없을 때, 리스트 안에 해당 숫자를 넣고 backtracking(start)를 다시 돈다 여기서 중요한 것은, 수열이 오름차순이어야 한다는 것이다 그래서 재귀함수를 돌릴때마다 backtracking(start + 1)를 해야 한다 그렇게 하면, for문에서 전에서 backtracking() 했던 것보다, 큰 수부터.. 2023. 4. 2.
[Python] 백준 15649 N과 M 🧑‍💻 [Python] 백준 15649 N과 M Silver 3 - Backtracking 쉽게 itertools의 permutations를 사용해서 풀 수 있는 문제다 하지만 Backtracking을 공부하고 싶어서 풀었던 문제다 기본적으로 if len(l) == M: 을 통해서 재귀 함수의 base case를 만든다 안 만들면 무한 루프 리스트 안에 for문을 돌며, 나오는 숫자가 없을 때, 리스트 안에 해당 숫자를 넣고 dfs()를 다시 돈다 그리고 l.pop()을 해야, 리스트에 숫자가 사라지고, 다른 경우의 수를 넣을 수 있다 코드 백트래킹 사용 N, M = map(int, input().split()) l = [] def dfs(): if len(l) == M: print(" ".join(ma.. 2023. 4. 2.

티스토리툴바