728x90 백트래킹 썸네일형 리스트형 [백준알고리즘] 2580번: 스도쿠 -C++ [백준알고리즘] 2580번: 스도쿠 -C++ 2580번: 스도쿠 (acmicpc.net) 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 스도쿠 문제 또한 대표적인 백트래킹 문제 중 하나다. 그만큼 유명하고, 비슷한 문제도 많이 있다. 그럼에도 정답 비율이 30%가 안 되는 것은 그만큼 처음 풀기에도 어려운 문제라는 것 같다. 예전에 이 문제를 Python3 (PyPy3)로 풀었다. 두 번 풀었었고, 해당 코드들을 모두 블로그에 쓴 적이 있다. [백준알고리즘] 2580번: 스도쿠 -Python (tistory.. 더보기 [백준알고리즘] 9663번: N-Queen -C++ [백준알고리즘] 9663번: N-Queen -C++ 9663번: N-Queen (acmicpc.net) 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 백트래킹 문제로 유명한 N-Queen 문제다. 유명한 문제인만큼 정답 비율은 53%가 넘음에도 불구하고 골드 5의 난이도를 갖고 있는 문제다. 그만큼 중요한 문제라고 말하는 것 같다. N-Queen 문제는 원래 8 Queen 문제로 유명하다. 문제의 요구조건은 동일하나 \( 8 \times 8 \) 크기의 체스판에 8개의 퀸을 놓는 문제다. 이거에 대한 접근법도 다양하게 있던.. 더보기 [백준알고리즘] 2661번: 좋은수열 -Python [백준알고리즘] 2661번: 좋은수열 -Python https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 한 번에 통과가 안돼서 오히려 당황하는 바람에 시간이 좀 걸리게 되었다. 1, 2, 3을 순서대로 대입해주는 방식으로 문제를 풀면 만들어낸 수열의 길이가 n일 경우 바로 출력하는 것이 가장 수가 적은 상태가 된다. 그래서 바로 출력해주고 끝내면 되는데, 이 부분을 다 구해보면서 비교해서 시간초과가 나왔었다. 필요 없는 코드들을 다 지워버리니 바로 통과했다. .. 더보기 [백준알고리즘] 1697번: 숨바꼭질 -Python [백준알고리즘] 1697번: 숨바꼭질 -Python https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 www.acmicpc.net 처음에 이번 문제를 DFS 방식으로 풀으려 했다. 백트래킹으로 여러 조건들을 추가해서 .. 더보기 [백준알고리즘] 14888번: 연산자 끼워넣기 -Python [백준알고리즘] 14888번: 연산자 끼워넣기 -Python https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다. www.acmicpc.net 백트래킹 문제이다. 왜지? 그냥 DFS 문제이다. 단계별 풀기에는 분명 백트래킹으로 되어있는데 페이지 밑에 알고리즘 분류에는 또 브포로 나와있다.. 주절주절했듯이 그냥 모든 경우를 찾아야한다. 가지치기(pruning)할 경우를 나눈다고 해.. 더보기 [백준알고리즘] 2580번: 스도쿠 -Python [백준알고리즘] 2580번: 스도쿠 -Python https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 몇 몇 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다. 나머지 빈 칸을 채우는 방식은 다음과 같다. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 굵은 선으로 구분되어 있는 3 www.acmicpc.net 2020.03.11 거의 유사하긴 하나, 새로 푼 코드를 아래에 추가했다. 와 이거 푸는.. 더보기 [백준알고리즘] 9663번: N-Queen -Java [백준알고리즘] 9663번: N-Queen -Java https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 드디어! BackTracking 분류에서 대표적인 백트래킹 문제인 N-Queen문제가 나왔다. 체스판에서 퀸은 가로, 세로, 대각선 방향으로 모두 길이 제한 없이 이동이 가능하다. 즉 각자의 가로, 세로, 대각선에 다른 퀸이 놓이지 않게 N X N 행렬 위에 N개의 퀸을 올리면 되는 문제이다. 이 문제를 처음에 주어진 것처럼 NxN행렬로 만들어서 구하다가 메모.. 더보기 이전 1 다음
