🔗문제 보러가기 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 사각형..

🔗문제 보러가기 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 🧑‍💻풀이 과정 네트워크에서 TCP 프로토콜을 공부할 때 봤었던 슬라이딩 윈도우(Sliding window) 개념을 적용하여 풀 수 있습니다. 입력으로 주어지는 각 숫자들을 배열(arr)에 저장하되, [0, K - 1]까지의 합계를 별도의 변수(sum)에 저장해둡니다. int start = 0, last = K로 인덱스 변수를 둡니다. 정답 변수(maxSum)을 1번에서 구한 sum 변수 값으로 초기화합니다. last < K가 만족할..

🔗문제 보러가기 16139번: 인간-컴퓨터 상호작용 첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째 www.acmicpc.net 🧑‍💻풀이 과정 나의 멍청한 실수 이전 문제에서 누적 합을 잘 구해놓고, 여기에서는 왜 적용을 못했나 싶습니다.. 처음에는 DP[26][S.length()] 배열을 선언하여, 각 알파벳마다 등장한 횟수를 누적하여 저장하는 방식으로 접근하였습니다. const int ALPHABET_COUNT = 26; const int LOWER_A_ASCII = 97; string S; vector DP(ALPHA..

🔗문제 보러가기 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 🧑‍💻풀이 과정 백준 사이트에서 단계별 풀어보기를 차례대로 정복 중인데, 그 중 누적 합이라는 유형에 대한 첫 문제였습니다. 문제를 보자마자 딱 생각난 것은, 통계학에서 쓰이는 누적분포함수(CDF, Cumulative Distribution Function)였습니다. 물론 개념적으로 완전히 동일한 것은 아니지만, 제 풀이의 기반 아이디어가 되어 주었습니다. 해당 아이디어를 토대로, 다음과 같이 문제를 순차적으로 풀 수 있습니..