동학 개발 운동

문제 출처 : www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 문제 해석 : 폭발 문자열과 일치하는 문자열을 제거하고 나머지를 이어 붙인다. 이때 다시 폭발 문자열이 생성될 수 있으며 이 또한 같은 방식으로 제거를 반복한다. 마지막까지 수행했을 때 길이가 0이라면 FRULA를 출력하고 아니라면 그 문자열을 출력하는 문제이다. 문제 풀이 : 파이썬에서 제공하는 replace를 사용하면 시간초과가 나온다. 따라서 인덱스와 스택을 활용하여 직접 제거..

문제 출처 : www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 해석 : 1~N 까지의 수 중에서 중복을 허용하면서 M개의 수를 고를 수 있는 모든 경우를 출력하는 문제이다. 단 비내림차순 이여야 한다. 문제 풀이 : 재귀적으로 모든 경우를 체크하면서 배열을 만들고 M개가 되었을 때 출력한다. 풀이 코드 def make_answer(count, arr): if count > M: for element in arr: print(element, end=" ..

문제 출처 : www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 해석 : 1~N의 수 중 중복없이 오름차순으로 M개의 수를 선택하는 경우를 모두 보이는 문제이다. 문제 풀이 : Python itertools - combinations에서 제공하는 것과 동일한 기능이기에 이를 활용한다. 가능한 다른 풀이 : 원리를 이용해서 직접 구현 할 수 있다. 이때는 for문을 통해서 오름차순인지 확인하고 중복된지를 확인하면서 만들면 된다. 풀이 코드 from ite..

문제 출처 : www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 해석 : NxN 보드에서 N개의 퀀이 서로 공격하지 못하게 배치하는 방법의 수를 출력하는 문제이다. 문제 풀이 : 백트래킹 방법을 이용해서 가능할 수 있는 경우에만 연산을 진행한다. 풀이 코드 def is_possible(end): for i in range(1, end): if answer[end] == answer[i] or abs(answer[end]-answer[i]) == abs(end - i): ..

문제 출처 : www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 문제 해석 : 스티커를 뜯으면 상하좌우로 모두 뜯긴다. 이때 최대 점수를 구할 수 있게 뜯는 문제이다. 문제 풀이 : DP로 풀 수 있는 문제이다. 갈 수 있는 방법은 자신과 다른 열의 바로전, 또는 2개전이며 이 중에서 최대 값을 구하면 되는 문제이다. 풀이 코드 T = int(input()) for test_case in range(T): N = int(input()) arr = [..

문제 출처 : www.acmicpc.net/problem/5639 문제 해석 : 이진 트리의 트리를 순회하여 출력하는 문제이다. 문제 풀이 : 주어진 순회를 입력 받아 이를 이진 트리임에 유의하여 더 커지는 순간이 자신의 루트라는 것을 생각하여 재 구성하여 출력하면 된다. 풀이 코드 def solution(start, end): if start > end: return div = end + 1 for i in range(start + 1, end + 1): # 루트 보다 큰 지점 --> 오른쪽 서브 트리 if tree[start] < tree[i]: div = i break solution(start + 1, div - 1) solution(div, end) print(tree[start]) import..

문제 출처 : www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표 www.acmicpc.net 문제 해석 : 외부 공기에 노출된 치즈는 1시간이 지나면 모두 녹아 없어진다. 이때 모든 치즈가 녹을때 까지 얼마의 시간이 걸리는 지 구하는 문제이다. ( 4변 중 2변이상이 외부 공기에 노출 되었을 때 외부 공기에 노출된 것으로 본다.) 문제 풀이 : DFS를 통해서 외부 공기를 각 시간 마다 확산 시키고 이와 2변 이상 마주치는 치즈를 제거하면 문제를 풀 수 있다. 풀이 코드 impo..

문제 출처 : www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 문제 해석 : In-order, post-order가 주어지면 pre-order를 찾아 출력하는 문제이다. 문제 풀이 : 트리를 순회하기 위해서 일단 in-order를 통해서 idx를 만들어 주고 반복적으로 자신의 왼쪽 자식, 오른쪽 자식을 찾아서 만들어 주면 된다. 풀이 코드 import sys sys.setrecursionlimit(10 ** 6) def find_solution(l_in, r_in, l_post, r_post..

문제 출처 : www.acmicpc.net/problem/2448 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net 문제 해석 : 예시로 제시된 그림을 보고 규칙을 찾아 별 모양을 찍는 문제이다. 문제 풀이 : 간격에 유의하면서 재귀적으로 만들어가면 된다. 풀이 코드 import math answer = [" * ", " * * ", "***** "] def stars(space): length = len(answer) for i in range(length): answer.append(answer[i] + answer[i]) answer[i] = (" " * s..

문제 출처 : www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 문제 해석 : 조합 결과를 출력하는 문제이다. 문제 풀이 : 공식과 동일하게 풀이하면 된다. 풀이 코드 import math N, M = map(int, input().split()) X = math.factorial(N) Y = (math.factorial(N-M)) * (math.factorial(M)) answer = X//Y print(answer) author : donghak park contact : donghark03@naver.com ## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문..