bruteforce

Algorithm/Baekjoon Online Judge
[java] 백준 2580 (스도쿠) Gold 4
문제 원문 링크 : https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net Approach 이 문제 또한 대표적인 BruteForce, Backtracking 문제이다. N-Queens 문제와 접근법은 동일하다. 놓을 수 있는지 없는지 검사 후, 다음 단계로 넘어가며, 놓을 수 없다면 다시 뒤로 돌아가 똑같이 다음 수를 검사하는 것이다. 나는 1차원 배열을 사용하였으며, 배열에서 i번째 요소는 N x N 행렬에서 (i / N)행 (i % N)열이다. ..
→2020.12.22
Algorithm/Baekjoon Online Judge
[java] 백준 9663 (N-Queen) Gold 5
문제 원문 링크 : https://www.acmicpc.net/problem/9663 Approach 대표적인 BruteForce, Backtracking 알고리즘 문제이다. 첫번째 열부터 숫자를 하나씩 놓으면서 그 다음 열에 놓을 수 없는지를 검사하여 놓을 수 있는 총 개수를 구하는 문제다. 퀸을 놓으려면 가로, 세로, 대각선에 퀸을 놓아서는 안된다. arr[] 배열은 몇 번째 열, 몇번째 행에 퀸을 놓은지를 기록한 것이다. 예를 들어, arr[i] = j 라 할 때, i번째 열에 j번째 행에 퀸이 놓아져 있다는 뜻이다. for(int i = 0; i < n; i++){ arr[lv] = i; if (isPossible(lv)){ backtracking(lv + 1); } } 루프를 이렇게 처리함으로써..
→2020.12.22

• 이전
• 1
• 2
• 3
• 다음