재귀
-
[백준] 1992 쿼드트리 with PythonPS 2023. 3. 31. 17:57
📌 BOJ 1992 쿼드트리 💡 조건 주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못한다. 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 된다. 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. N ×N 크기의 영상이 주어질 때, 이 영상을 압축한 결과를 출력하는 프로그램을 작성하는 문제. 분할정복, 재귀 유형의 문제. 🔖 예제 및 실행결과 예제 1 8 11110000 11110000 00011100 00011100 11110000 111..
-
[백준] 20166 문자열 지옥에 빠진 호석 with PythonPS 2022. 6. 4. 01:36
📌 BOJ 20166 문자열 지옥에 빠진 호석 💡 조건 정신을 차려보니 바닥에는 격자 모양의 타일이 가득한 세상이었고, 각 타일마다 알파벳 소문자가 하나씩 써있다더라. 두려움에 가득해 미친듯이 앞만 보고 달려 끝을 찾아 헤맸지만 이 세상은 끝이 없었고, 달리다 지쳐 바닥에 드러누우니 하늘에 이런 문구가 핏빛 구름으로 떠다니고 있었다. 이 세상은 N행 M열의 격자로 생겼으며, 각 칸에 알파벳이 써있고 환형으로 이어진다. 왼쪽 위를 (1, 1), 오른쪽 아래를 (N, M)이라고 하자. 너는 아무 곳에서나 시작해서 상하좌우나 대각선 방향의 칸으로 한 칸씩 이동할 수 있다. 이 때, 이미 지나 왔던 칸들을 다시 방문하는 것은 허용한다. 시작하는 격자의 알파벳을 시작으로, 이동할 때마다 각 칸에 써진 알파벳을 이..
-
[백준] 6603 로또 with PythonPS 2022. 2. 10. 00:10
📌 BOJ 6603 로또 💡 조건 집합 S에서 K개의 숫자를 골라 뽑아 낼 수 있는 경우의 수를 모두 출력하는 문제 입력이 여러개 들어오며, 0이 들어왔을 때 종료 백트래킹, 재귀, 조합유형의 문제 🖥 소스 코드 from sys import stdin from itertools import combinations while 1: data = list(map(int, stdin.readline().split())) if len(data) == 1 and data[0] == 0: break else: a, arr = data[0], data[1:] res = [] for x in list(set(combinations(arr, 6))): if len(set(x)) == 6: temp = sorted(list..
-
[백준] 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..