백트래킹
-
[백준] 6443 애너그램 with PythonPS 2022. 3. 2. 23:42
📌 BOJ 6443 애너그램 💡 조건 첫째 줄에 단어의 개수 N 이, 둘째 줄부터 N개의 영단어가 들어온다. 영단어는 소문자로 이루어져 있다. 단어의 길이는 20보다 작거나 같고, 애너그램의 수가 100,000개 이하인 단어만 입력으로 주어진다. 애너그램 프로그램이란, 입력받은 영단어의 철자들로 만들 수 있는 모든 단어를 출력하는 것이다. 입력받은 단어내에 몇몇 철자가 중복될 수 있다. 이 경우 같은 단어가 여러 번 만들어 질 수 있는데, 한 번만 출력해야 한다. 또한 출력할 때에 알파벳 순서로 출력해야 한다. 백트래킹 유형의 문제 🖥 소스 코드 from sys import stdin def solve(l, s): if l == 0: visited.add(s) return for i in range(26..
-
[백준] 1759 암호 만들기 with PythonPS 2022. 2. 13. 23:18
📌 BOJ 1759 암호 만들기 💡 조건 암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성. 각 줄에 하나씩, 사전식으로 가능성 있는 암호를 모두 출력 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 문자들은 알파벳 소문자이며, 중복되는 것은 없다. 브루트포스, 백트래킹 유형의 문제 🖥 소스 코드 from sys import stdin from itertools import com..
-
[백준] 15658 연산자 끼워넣기 (2) with PythonPS 2022. 2. 2. 17:56
📌 BOJ 15658 연산자 끼워넣기 (2) 💡 조건 N개의 수로 이루어진 수열 A1, A2, ..., AN N(2 ≤ N ≤ 11), (1 ≤ Ai ≤ 100) 입력 값중 셋째 줄에 4N보다 작거나 같은 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다. 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다. 식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 나눗셈은 정수 나눗셈으로 몫만 취한다. 또한 음수를 나눌 때에는 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾸어야 한다. 백트래킹, DFS 알고리즘 유형의 문제 🖥 소스 코드 from sys impo..
-
[백준] 10819 차이를 최대로 with PythonPS 2022. 1. 11. 17:53
📌 BOJ 10819 차이를 최대로 💡 조건 N개의 정수로 이루어진 배열 A N (3 ≤ N ≤ 8) 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. 다음 식의 최댓값을 구하는 프로그램을 작성. |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]| 5. **브루트포스 알고리즘 유형**의 문제 ## 🖥 소스 코드 from sys import stdin from itertools import permutations n = int(stdin.readline()) arr = list(map(int, stdin.readline().split())) res = -int(1e9) for arr2 in permutations(arr, n): v ..
-
[백준] 1799 비숍 with PythonPS 2021. 10. 11. 21:44
📌 BOJ 1799 비숍 💡 조건 및 풀이 체스판의 크기는 10 이하의 자연수 비숍을 놓을 수 있는 곳에는 1, 비숍을 놓을 수 없는 곳에는 0 대각선 방향으로 움직이는 비숍이 이동할 수 있는 경로에 비숍을 놓을 수 없다. 백트래킹 유형의 문제 🖥 소스 코드 from sys import stdin n = int(stdin.readline()) chess_map = [] black = [] white = [] color = [[0] * n for _ in range(n)] for i in range(n): for j in range(n): color[i][j] = (i % 2 == 0 and j % 2 == 0) or (i % 2 != 0 and j % 2 != 0) for i in range(n): ch..
-
[백준] 6987 월드컵 with PythonPS 2021. 9. 22. 23:14
📌 BOJ 6987 월드컵 💡 조건 및 풀이 6개의 국가가 있고, 총 18번의 경기를 한다. 승, 무, 패의 결과가 있으며, 승, 무, 패의 수는 6보다 작거나 같은 자연수 또는 0 백트래킹 유형의 문제 입력은 네 줄로 들어오며, 각 줄에 대해 가능한 결과 1, 불가능한 결과 0 을출력하는 문제이다 🖥 소스 코드 from sys import stdin from itertools import combinations as cb def solution(round): global ans if round == 15: ans = 1 for sub in res: if sub.count(0) != 3: ans = 0 break return t1, t2 = game[round] for x, y in ((0, 2), (1..