🥇 Problem Solving/Backtracking

[Python] BOJ / 1038번 / 감소하는 수

1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 📝 풀이 백트리킹 알고리즘 사용 재귀로 구현할 경우 메모리 초과가 발생하므로 while문을 통해 구현 알고리즘 현재 값이 감소하는 수라면 현재 값에 +1을 수행 현재 값이 감소하는 수가 아니라면 현재 값과 가장 가까운 감소하는 수가 되도록 수정 위 과정을 반복하며 N번째 감소하는 수가 되었을 때의 값을 출력 N번째 감소하는 수가 없는 경우에는 -1을 출력해야하며 ,이는 최대 감소하는 수인 '9876543210'보다 현재 값이 클 경우임 💻 소스코드..

[Python] BOJ / 1062번 / 가르침

1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 📝 풀이 백트래킹 사용 남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 기본적으로 알아야하는 글자가 5개(a, c, i, n, t)이다. k(가르칠 글자의 수)가 5보다 작을 경우 읽을 수 있는 단어가 없다. k(가르칠 글자의 수)가 26(a, b, c, ..., z)일 경우 모든 단어를 읽을 수 있다. 배운 단어와 배우지 않은 단어를 구분하기 위해 배열을 사용하며 인덱스는 아스키코드(ord())를 통해 접근한다. set을 활용하여..

[Python] BOJ / 12100번 / 2048 (Easy)

12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 문제 2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다. 이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만,..

[Python] BOJ / 1987번 / 알파벳

1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 ..