728x90 backtracking 썸네일형 리스트형 [백준알고리즘] 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개의 퀸을 놓는 문제다. 이거에 대한 접근법도 다양하게 있던.. 더보기 [백준알고리즘] 3109번: 빵집 -Python [백준알고리즘] 3109번: 빵집 -Python https://www.acmicpc.net/problem/3109 3109번: 빵집 문제 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 중에, 가스비가 제일 크다는 것을 알게되었다. 따라서 원웅이는 근처 빵집의 가스관에 몰래 파이프를 설치해 훔쳐서 사용하기로 했다. 빵집이 있는 곳은 R*C 격자로 표현할 수 있다. 첫째 열은 근처 빵집의 가스관이고, 마지막 열은 원웅이의 빵집이다. 원웅이는 가스관과 빵 www.acmicpc.net 문제에 대한 접근은 어렵지 않은 것 같다. visit 리스트를 만들고 오른쪽 위부터 우선적으.. 더보기 [백준알고리즘] 2023번: 신기한 소수 -Python [백준알고리즘] 2023번: 신기한 소수 -Python https://www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수이고, 7도 소수이다. 즉, 왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수이다! 수빈이는 이런 숫자를 신기한 소수라고 이름 붙였다. 수빈이는 N자리의 숫자 중에서 어떤 수들이 신기한 소수인지 궁금해졌다. N이 주어졌을 때, 수빈이를 위해 N자리 www.acmicpc.net 처음에는 에라토스테네스의 체를 이용해서 10**8만큼의 리스트를 만들었었다. 만.. 더보기 [백준알고리즘] 1799번: 비숍 -Python [백준알고리즘] 1799번: 비숍 -Python https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 한 줄씩 주어진다. 비숍을 놓을 수 있는 곳에는 1, 비숍을 놓을 수 없는 곳에는 0이 빈칸을 사이에 두고 주어진다. www.acmicpc.net 이 한문제를 푸는데 굉장히 오래 걸렸다. 처음에는 N-Queen 문제랑 비슷하다고 생각하며 너무 쉽게 생각했다. N-Queen 문제와 비슷하기는 하지만 N-Queen은 한 행과 한 열에 하나씩 배치하기 때문에 배치할 공간이 훨씬 줄어들기 때문.. 더보기 [백준알고리즘] 1339번: 단어 수학 -Python [백준알고리즘] 1339번: 단어 수학 -Python https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 10개이고, 수의 최대 길이는 8이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다. www.acmicpc.net 처음에는 DFS처럼 거의 완전탐색처럼 푸는 것 같다. 알고리즘 분류만 봐도 백트래킹으로 나와있다. 하지만 백트래킹으로 풀었을 때, 시간 초과가 발생했으며 시간을 줄이는 방법이 마땅치 않다. 실제로 다른 분들의 코드를 봐도 백트래킹처럼 푼 풀이는 보지 못했.. 더보기 [백준알고리즘] 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일 경우 바로 출력하는 것이 가장 수가 적은 상태가 된다. 그래서 바로 출력해주고 끝내면 되는데, 이 부분을 다 구해보면서 비교해서 시간초과가 나왔었다. 필요 없는 코드들을 다 지워버리니 바로 통과했다. .. 더보기 [백준알고리즘] 1987번: 알파벳 -Python [백준알고리즘] 1987번: 알파벳 -Python https://www.acmicpc.net/problem/1987 1987번: 알파벳 문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 www.acmicpc.net 20200404. 새로 풀었다. 이번에도 PyPy로만 통과가 가능했다. 처음에는 모양이 달.. 더보기 이전 1 2 다음
