넘치게 채우기

https://www.acmicpc.net/problem/1799BOJ - 비숍문제 유형: 백트래킹, 브루트 포스, MITM(Meet-In-The-Middle)문제 난이도: Platinum V시간 제한: 10초메모리 제한: 128MB 문제서양 장기인 체스에는 대각선 방향으로 움직일 수 있는 비숍(bishop)이 있다. 과 같은 정사각형 체스판 위에 B라고 표시된 곳에 비숍이 있을 때 비숍은 대각선 방향으로 움직여 O로 표시된 칸에 있는 다른 말을 잡을 수 있다.그런데 체스판 위에는 비숍이 놓일 수 없는 곳이 있다. 에서 체스판에 색칠된 부분은 비숍이 놓일 수 없다고 하자. 이와 같은 체스판에 서로가 서로를 잡을 수 없도록 하면서 비숍을 놓는다면 과 같이 최대 7개의 비숍을 놓을 수 있다. 색칠된 부분에는..

https://codeforces.com/contest/2043/problem/AEducational Codeforces Round 173(Div.2) - A. Coin Transformation문제 유형: 재귀, 분할 정복시간 제한: 1초메모리 제한: 256MB 문제Initially, you have a coin with value n">n.You can perform the following operation any number of times (possibly zero):- transform one coin with value x">x, where x">x is greater than 3">3 (x>3">x>3), into two coins with value ⌊x4⌋..

https://www.acmicpc.net/problem/6772BOJ - Choose Your Own Arithmetic문제 유형: 수학, 다이나믹 프로그래밍, dfs, 재귀, 백트래킹문제 난이도: Silver I시간 제한: 2초메모리 제한: 512MB 문제In Waterloo, you probably have seen some geese. How can you see geese with your calculator? Start with 6, add 7, multiply by 6, multiply by 8, add 7, multiply by 8, and multiply by 7, giving 35336. Then if you flip your calculator upside down, it says g..

https://www.acmicpc.net/problem/10830BOJ - 행렬 제곱문제 유형: 행렬, 재귀, 분할 정복문제 난이도: Gold IV시간 제한: 1초메모리 제한: 256MB 문제크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. 입력첫째 줄에 행렬의 크기 N과 B가 주어진다. (2 ≤ N ≤  5, 1 ≤ B ≤ 100,000,000,000)둘째 줄부터 N개의 줄에 행렬의 각 원소가 주어진다. 행렬의 각 원소는 1,000보다 작거나 같은 자연수 또는 0이다. 출력첫째 줄부터 N개의 줄에 걸쳐 행렬 A를 B제곱한 결과를 출력한다. 풀이행렬 A가 있다고 해보자. 행렬 ..

https://www.acmicpc.net/problem/5639BOJ - 이진 검색 트리문제 유형: 트리, 재귀, dfs, 이진탐색트리(BST)문제 난이도: Gold IV시간 제한: 1초메모리 제한: 256MB 문제이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, ..

https://www.acmicpc.net/problem/9251BOJ - LCS문제 유형: 문자열 처리, 재귀, 다이나믹 프로그래밍문제 난이도: Gold V시간 제한: 0.1초메모리 제한: 256MB 문제LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 입력첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. 출력첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다. 풀이dp[i1][i2]는 첫 번째 문자열의 i1인덱스부터의 부분문자..

https://www.acmicpc.net/problem/1991BOJ - 트리 순회문제 유형: DFS, 트리, 재귀문제 난이도: Silver I시간 제한: 2초메모리 제한: 128MB 문제이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.예를 들어 위와 같은 이진 트리가 입력되면,전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트) 입력첫째 줄에는 이진 트리의 노드의 개..

https://leetcode.com/problems/maximum-number-of-moves-in-a-grid/?envType=daily-question&envId=2024-10-29leetcode - Maximum Number of Moves in a Grid문제 유형: 다이나믹 프로그래밍, 재귀, dfs, 행렬문제 난이도: Medium 문제You are given a 0-indexed m x n matrix grid consisting of positive integers.You can start at any cell in the first column of the matrix, and traverse the grid in the following way:From a cell (row, col),..

https://www.acmicpc.net/problem/9663BOJ - N-Queen문제 유형: 완전 탐색, dfs, 백트래킹, 재귀문제 난이도: Gold IV시간 제한: 10초메모리 제한: 128MB 문제N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 N이 주어진다. (1 ≤ N  출력첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. 풀이재귀 함수 solve(row)에는 이제 퀸을 넣어야 할 행의 인덱스 row를 받는다.첫 번째 방법은, 직접 N * N의 보드를 만들어서 직접 퀸이 공격하는 영역에 표시를 해두고, 공격받지 않는 열에 퀸을 두..

https://www.acmicpc.net/problem/2448BOJ - 별 찍기 - 11문제 유형: 재귀, 구현문제 난이도: Gold IV시간 제한: 1초메모리 제한: 256MB 문제예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요. 입력첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) 출력첫째 줄부터 N번째 줄까지 별을 출력한다. 풀이 재귀적인 방법, 반복적인 방법 모두 가능하다. 반복적인 풀이:shape = {"  *  "" * * ""*****"}를 처음에 저장해놓고, shape의 크기가 n이될때까지 계속해서 크기를 증식시킨다.매번 길이가 두 배가 되는데,shape[i + 기존높이] = shape[i] + " "..