슬라이딩 윈도우(Sliding Window)란?슬라이딩 원도우는 특정 범위를 의미하는 윈도우(window)를 유지한 상태에서, 이 범위 안의 요소들을 이용해 문제를 효율적으로 해결하는 알고리즘 기법이다. 배열이나 리스트에서 연속된 일정 범위의 값들을 반복적으로 비교하거나 계산할 때 특히 유용하며, 대표적으로 다음과 같은 문제에서 활용된다.구간 합 구하기(부분합)특정 길이의 부분 배열/부분 문자열 분석연속된 값들 중 최솟값/최댓값 찾기평균/합/최대 빈도 등 윈도우 기반 계산슬라이딩 윈도우의 핵심은 윈도우를 한 칸 이동할 때 변경되는 부분만 갱신하여 전체를 다시 계산하지 않는 것이다.이를 통해 O(N²) 시간이 걸릴 수 있는 문제를 O(N) 시간으로 크게 줄일 수 있다. 슬라이딩 윈도우 종류슬라이딩 윈도우는..
문제 설명https://www.acmicpc.net/problem/2447 ▸ 문제재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다.크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다. **** **** N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다. ▸ 입력첫째 줄에 N이 주어진다. N은 3의 거듭제곱이다. 즉 어떤 정수 k에 대해 N=3k이며, 이때 1 ≤ k ▸ 출력첫째 줄부터 N번째 줄까지 별을 출력한다. 📍 문제 정보..
문제 설명https://www.acmicpc.net/problem/1074 ▸ 문제한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.다음 예는 22 × 22 크기의 배열을 방문한 순서이다.N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.다음은 N=3일 때의 예이다. ▸ 입력첫째 줄에 정수 N, r, c가 주어진다. ▸ 출력r행 c열을 몇 번째로 방문했는지 출력한다. 📍 문제 정보🥇 문제 레벨 : 골드 5🔔 문제 유형 : 분할 정복,..
문제 설명https://www.acmicpc.net/problem/2630 ▸ 문제아래 과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다. 전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다.전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 ..
분할정복(Divide and Conquer)이란?분할정복 알고리즘은 큰 문제를 작은 부분 문제로 분할(Divide)하고, 각 부분 문제를 독립적으로 해결(Conquer)한 뒤, 그 결과를 결합(Combine)하여 전체 문제의 해답을 구하는 알고리즘 기법이다.이 기법은 주로 재귀적 방법을 통해 구현되며, 대표적인 예로는 이진 탐색(Binary Search), 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort) 등이 있다. 분할정복과 동적 계획법 차이두 기법 모두 큰 문제를 작은 문제로 나눈다는 점은 동일하지만, 부분 문제의 중복 여부와 결과 처리 방식에 핵심 차이가 있다. 분할정복(Divide and Conquer)부분 문제가 서로 독립적이고 중복되지 않는다.각 부분 문제는 새롭게 계산하며, ..
문제 설명https://www.acmicpc.net/problem/1446 ▸ 문제매일 아침, 세준이는 학교에 가기 위해서 차를 타고 D킬로미터 길이의 고속도로를 지난다. 이 고속도로는 심각하게 커브가 많아서 정말 운전하기도 힘들다. 어느 날, 세준이는 이 고속도로에 지름길이 존재한다는 것을 알게 되었다. 모든 지름길은 일방통행이고, 고속도로를 역주행할 수는 없다.세준이가 운전해야 하는 거리의 최솟값을 출력하시오. ▸ 입력첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주어진다. 모든 위치와 길이는 10,000보다 작거나 같은 음이 아닌 정수이..
