🔗문제 보러가기 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 🧑🏻‍💻풀이 과정 🔗1992번 문제와 비슷한데, 4개의 분할에서 9개로 늘었다는 점만 다른 것을 빼면 풀이는 똑같습니다. 정말로 똑같아서, 따로 적을 말이 없네요... ✏️소스 코드 및 결과 #include #include #include #define FAST_IO ios::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL); using namespace std; const int ALL_..

🔗문제 보러가기 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 🧑🏻‍💻풀이 과정 🔗2630번 문제와 유사하게 풀 수 있습니다. 전체 2차원 배열을 image라고 하고, 현재 탐색 중인 사각형 영역의 제일 왼쪽 위 시작점을 (rowBegin, colBegin)이라고 하겠습니다. \(N \times N \) 크기부터 시작하여 Top-down으로 내려 간다. N == 1이라면, 정답 문자열에 현재 색깔(image[rowBegin][colBegin])을 추가하고 종료한다. N != 1이라면, 현재 사각..

🔗문제 보러가기 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 🧑🏻‍💻풀이 과정 맨 처음에는 \( N \times N \) 크기의 색종이부터 시작하여 주어진 정사각형 내의 색깔들이 모두 같은 색깔인지를 볼 겁니다. 이 때, 선택지는 두 가지로 나뉘게 됩니다. 주어진 범위 내의 색깔이 모두 같은가? \( \rightarrow \) 해당 색깔 개수 +1하고, 종료 색깔이 같지 않은가? \( \rightarrow \) 주어진 범위의 사각형을 4등분하여 다시 탐색 시작 정사각형 탐색은 맨..

🔗문제 보러가기 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 🧑🏻‍💻풀이 과정 최장 증가 부분 수열(LIS) 알고리즘은 저에겐 처음 접해보는 개념이었습니다. 그래서 해당 개념에 대해 먼저 공부하였고, 기존 \( O(n^2) \)의 시간복잡도를 가지는 알고리즘을 이진 탐색(Binary Search)을 활용하여 \( O(nlogn) \)으로 줄이는 방법에 대해서도 알게 되었습니다. (🔗참고 블로그) 방법은 다음과 같았습니다. 최장 증..

🔗문제 보러가기 25682번: 체스판 다시 칠하기 2 첫째 줄에 정수 N, M, K가 주어진다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 🧑🏻‍💻풀이 과정 각각 N행 M열 크기의 흰색으로 시작하는 보드판과 검은색으로 시작하는 보드판 두 개의 2차원 배열을 준비합니다. 다음 과정을 통해, 교체해야 하는 횟수를 누적하여 저장해 나갑니다. 다음은 올바른 체스판의 배열일 경우를 나타냅니다. (행 + 열)이 짝수일 경우, 시작 색깔(1, 1)과 같아야 한다. (행 + 열)이 홀수일 경우, 시작 색깔(1, 1)과 달라야 한다. 위 두 가지 중 하나에 해당하지 않을 경우, 색깔을 교체해야 한다. 행과 열을 각각 K부터 시작하여, 각각 ..

🔗문제 보러가기 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 🧑‍💻풀이 과정 초기값으로, 1행과 1열 각각의 배열 원소에 누적합을 저장합니다. 2행 2열 ~ N행 N열까지 다음 과정을 반복합니다. \( N \times N \) 배열을 arr이라고 한다면, arr[row][col] += arr[row - 1][col] + arr[row][col - 1] - arr[row - 1][col - 1] arr[row - 1][col]에는 (row - 1 ) * col 사각형..