동학 개발 운동

문제 출처 : 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 ## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문..

문제 출처 : www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 문제 해석 : 1,1에서 N,M으로 이동하는데 걸리는 최소 거리를 구하는 문제이다. 단 이때 딱 하나의 벽을 부술 수 있으며 도착하지 못하는 경우에는 -1을 출력해야한다. 문제 풀이 : BFS문제에 한가지 상태를 고려하는 문제이다. 이 문제를 직접 벽을 제거한 배열을 파라미터로 넘겨줘 풀 수 있지만 시간초과로 인해서 변수 한개를 더 사용해서 이를 풀이하는게 올바르다. ->..

문제 출처 : www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 문제 해석 : 3칸으로 이루어진 배열에서 각 배열을 자신의 바로 아래 혹은 그와 붙어있는 칸으로 움직일 수 있다. 이때 마지막까지 갔을 때 최소, 최대 값을 구하세요 문제 풀이 : 메모리 제한이 빡빡하기 때문에 슬라이딩 윈도우와 다이나믹 프로그래밍을 이용해서 문제를 풀어야 한다. -> 모든 순간을 저장하는 배열이 아닌 필요한 만큼만 이동하면서 계산을 진행해야 한다. 풀이 코드 import sys input = ..

문제 출처 : www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 www.acmicpc.net 문제 해석 : 트리를 전위, 중위, 후위 순회하는 코드를 작성하는 문제이다. 문제 풀이 : 딕셔너리 자료형을 통해서 트리를 구성하고 순회 알고리즘을 적용하면 풀 수 있다. 풀이 코드 def pre(current): if current == ".": return else: left,right = tree[current] print(current, end="") pre(left) pre(righ..