Algorithms63 백준 9663. N-Queen https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 일전에 42서울 피신 중에 접한 적 있는 문제. 이 때 백트래킹이라는 알고리즘의 존재를 처음 알았다 . . . 유명한 문제기도 하고, 파훼법도 생각보다 간단하다. 백트래킹 문제의 핵심은 아무래도 적합성 검사 알고리즘이니깐 그 부분만 잘 구현하면 된다. 우선 기본적인 아이디어는 다음과 같다. 1. 얼핏 보면 2x2 List가 필요할 것 같지만, 일차원 리스트로 충분하다. - 어차피 한 row에 퀸이 두 개 이상 들.. 2022. 6. 20. 백준 15651. N과 M(3) https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 수열을 구하는 문제인데, 중복되는 수가 와도 상관없다. 역시 백트래킹으로 해결했다. 다만 이 경우에 모든 자리에 모든 수가 와도 되므로 검사하는 알고리즘을 삭제하고 모든 try를 하면 된다. n, m = map(int, input().split()) arr = [] def dfs(): if len(arr) == m: print(' '.join(map(str, arr))) return for i .. 2022. 6. 17. 백준 15649. N과 M (1) https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 수열을 도출하는 방법 중 하나는 백트래킹을 이용하는 방법이다. 백트래킹이란 모든 경우의 수를 살피면서 조건이 맞으면 탐색을 계속하고, 조건에 맞지 않으면 노드 하나를 되돌아가는 양상을 띈다. n, m = map(int, input().split()) arr = [] def backtrack(): if len(arr) == m: print(' '.join(map(str, arr))) return .. 2022. 6. 16. 백준 15650. N과 M(2) https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net NPM 중에서도 오름차순으로 정렬되어 있는 수열만 출력하는 문제. 수열을 만드는 문제들에서 주로 쓰이는 DFS(Depth First Search, 깊이우선탐색)를 사용했다. 기본적인 개념은 다음과 같다. [1]에서 시작해서 두번째 숫자에 우선 1을 넣는다. [1,1] -> 끝자리에 1~9를 모두 넣어본다. 한칸 후퇴해서 [1,2] 로 리스트를 바꾼다. ->다시 끝자리에 1~9를 모두 넣어본다. .. 2022. 6. 16. 이전 1 ··· 3 4 5 6 7 8 9 ··· 16 다음
