백트레킹6 [Back Tracking] 백준 2580번 : 스도쿠 파이썬 생각하기 0인 칸에 대해서 이 칸에 스도쿠 룰에 맞는 숫자를 넣고 다음 0인 칸에 대해서 룰에 맞는 숫자를 넣는 식으로 생각을 했다. 조건이 안맞으면 바로 이전으로 가서 다시 한번 숫자를 넣어보는 식으로 생각을 했다 prunning 조건 검사 해당 0이 있는 row에 지금 들어갈 같은 수를 가진 아이가 있는지 검사 해당 0이 있는 col에 지금 들어갈 같은 수를 가진 아이가 있는지 검사 0이 속한 아홉개의 섹션 안에 지금 들어갈 같은 수를 가진 아이가 있는지 검사 위의 세가지 조건을 0자리에 들어갈 1 ~ 9까지에 대해서 검사를 하고 맞으면 recursive하게 다음으로, 틀리면 backtracking을 진행한다 9*9를 검사하지 않고 0인 것들만 보기 입력을 받을 때, 0인 칸의 row idx와 col.. 2021. 11. 6. [Back Tracking] 백준 9663번 : NQueen - Python 파이썬 생각하기 각 row에는 하나의 퀸만 있고 각 col에는 하나의 퀸만 있어야 한다 그리고 왼쪽 아래 대각선과 오른쪽 아래 대각선을 모두 고려해야 함 오른쪽 아래 대각선은 row idx - col idx + N -1 이 모두 같은 칸이고 왼쪽 아래 대각선은 col idx - row idx 이 모두 같은 칸이다 이를 고려하여 recursive를 돌리면 된다 처음에는 plus_mem 과 minus_mem을 리스트로 선언하여 append하였지만 이는 시간초과를 가져오는 결과를 보였다 import sys import copy input = sys.stdin.readline N = int(input()) cnt = 0 def search(row, col_mem, plus_mem, minus_mem): global c.. 2021. 11. 2. Sum-of-Subsets 문제 문제 합이 G가 되는 모든 element들의 합의 집합들을 찾아라 입력 5 // data의 개수 21 // 합 G의 값 5 6 10 11 16 // data 값 출력 5, 6, 10, 5, 16, 10, 11, 경우의 수 문제로 최대한 적게 경우의 수를 찾을 수 있는 방법을 생각해야 한다. 합이 G를 넘어버리면 중간에 경우에 대한 계산을 중단하고 다른 경우의 수 즉, 방법으로 넘어가야 한다 처음 생각해낸 방법은 중간에 결과가 G를 넘어버리면 다시 back tracking으로 전으로 돌아가야 한다는 대략적인 밑그림이었다. back tracking 을 사용한다면 State Space Tree (상태 공간 tree)를 생각해야 한다 상태 공간 tree의 각 상태를 어떻게 정의하는가에 대해서 생각해보았다. 각각.. 2021. 5. 12. [Back Tracking] 백준 9663번 - N Queen 완전탐색을 한다면? N = 14일때, 14x14의 요소중에서 14개를 뽑는 것이기 때문에 256^14가 된다 제한 시간은 10초(10^9)이기 때문에 초과한다 -> Back Tracking 으로 풀어야 한다 2차원 배열에서 알아두면 좋은 점 col이 i, row가 j라고 할 때 생각 처음에는 15*15 배열을 만들어 놓고 아래의 규칙에 따라 퀸이 배치된 칸 퀸이 배치된 칸의 모든 아래 칸들 퀸이 배치된 칸의 왼쪽 대각선 아래 칸들 퀸이 배치된 칸의 오른쪽 대각선 아래 칸들을 모두 false 처리 했다 하지만 이렇게 하는 경우 문제가 있다 빨간색이 파란선과 겹치면서 파란색을 원상복귀 시켜놓는다. 이러한 경우를 방지하기 위해서는 각 케이스를 독립적이게 분리할 필요가 있다. 2차원 배열에서의 인덱스들의 특징을.. 2021. 1. 25. 이전 1 2 다음
