1. 문제 설명 📌문제 링크문제 설명이 어려워서 부연 설명을 하겠다.N개의 울타리와 너비가 X인 룰러가 있다. 울타리의 경우 너비는 1로 고정이고, 높이만 1차원 배열 형식으로 주어진다. 당신은 룰러를 활용하여 페인트를 칠할 것인데, 너비가 X임으로, X 너비 내의 울타리는 한 번에 칠하게 될 것이다. 여기서 중요한 조건은 다음과 같다.(1) 룰러의 부분이 허공에 닿으면 안된다.왼쪽과 같이 일련의 울타리가 주어진다면, 오른쪽 그림의 테두리 안 쪽만 롤러를 돌려 칠할 수 있다는 말이다. 즉 롤러 너비 X 내에 제일 작은 울타리가 색칠의 기준이 된다.(2) 칠한데는 또 칠할 수 있다.다음과 같이 롤러의 너비가 3일 때, 처음 맞딱뜨리는 구간에서는 최대로 칠할 수 있는 높이가 1일 것이다.롤러를 한 칸 옮기..

1. 문제 설명 📌문제 링크용액마다 특수값이 존재두 용액을 골라서 둘의 특수 값을 합했을 때, 그 합이 0에 가장 가까운 조합을 구하여라2. 접근 방식 🗃️KEY WORD: Two way Two pointer용액의 특수값을 1차원 배열에 입력받고, 해당 배열을 오름차순으로 정렬한다.index = 0에 L 포인터, index = N-1에 R 포인터를 둔다L+R > 0 일 경우, R 포인터를 한 칸 후진 시켜서 합을 하향조정한다.L-R 일 경우, L 포인터를 한 칸 전진 시켜서 합을 상향조정한다.0에 가까운 값을 구해야함으로, 둘 사이의 합의 절대값이 최소인 경우를 찾으면 된다.(왜냐하면, 두 포인터 사이의 합의 절대값이 커질수록 0에서 멀어지기 때문이다.)(1) 단뱡항 투 포인터로 답을 구할 수 없는 ..

1. 문제 설명 📌문제 링크2. 접근 방식 🗃️KEY WORD: one-way Two pointer단방향 투 포인터를 사용하는 전형적인 문제이다. 왼쪽 포인터(L)과 오른쪽 포인터(R)을 둔다. 해당 구간 내 수들의 합을 sum이라 하겠다.sum : R 포인터를 전진시킨다.sum >= M: L 포인터를 전진시킨다. (만약 sum == M이면 답이 되는 경우의 수를 +1 올린다.)구간 내의 합은 구간 내의 값이 원소 하나인 경우도 포함한다. 따라서 arr[0] == M 인 경우도 예외 없이 계산에 포함되도록 해줘야 한다.나는 3번의 규칙을 지키기 위해 배열을 N+1로 만들어 값들을 1부터 채우고, 포인터들은 0부터 시작하도록 하였다.3. 코드 소개 🔎import java.io.*;import java..

0. 글이 흘러가는 방향먼저 개념 설명을 하고, 투 포인터를 활용하는 대표적인 문제 2개를 직접 풀어보며, 개념에 대한 보충을 하겠다.1. 개념1차원 배열에 두 개의 포인터를 두고, 두 포인터에 의미를 부여하여 문제를 푸는 기술배열 안에서 특정 조건의 값을 구하는 문제에서, 일반적으로 시간 복잡도가 O((N^{2}))가 든다면, 투 포인터 기법을 활용하면 시간 복잡도를 O(N)으로 줄일 수 있다. (이유는 활용을 살펴보며 설명하겠다.)(1) 유형투 포인터를 운용하는 유형에는 크게 2가지가 있다.a.단방향 운용L 포인터와 R 포인터가 한쪽 방향으로만 움직이는 것이다. 슬라이딩 윈도우의 양끝을 의미한다고 보면 된다. 슬라이딩 윈도우와 다른 점은 포인터에 따라 구간의 길이가 가변적이라는 것이다.b. 양방향 운..

1. 문제 설명 📌문제 링크일반적인 슬라이딩 윈도우에서 구간 내 최대값을 반환하라는 조건이 추가되었다.2. 접근 방식 🗃️KEY WORD: Sliding Window, Data Structure(Deque)(1) 코드 구현 순서슬라이딩 윈도우를 deque로 구현한다.내림차순 정렬 (최대값 = peek())슬라이딩 윈도우에서 빠져나가는 값은 deque에서도 똑같이 제거rear > 신규값: 신규값을 deque에 추가한다.rear : rear를 poll 한다. (이는 rear > 신규값이 될 때까지 반복)0~2M-1에 해당하는 값들에 대해 먼저 슬라이딩 윈도우를 진행한다.M ~ N-M까지 슬라이딩 윈도우를 진행한다. 진행하며, 당시 최대값을 StringBuilder에 추가한다.(2) 해설해당 문제는 i라는..

1. 문제 설명 📌문제 링크슬라이딩 윈도우에서 더 나아가서, 윈도우 구간안에 최소값을 매번 출력하는 문제이다.2. 접근 방식 🗃️KEY WORD: Sliding Window, Data Structure (Deque)파이썬에서는 추가시간이 주어줘서 우선순위 큐를 이용해도 풀리지만, Java에서는 풀리지 않는다. 왜 우선순위 큐로는 안되는지에 대해 4번 항목에서 설명하겠다.(1) 전체 접근 방식ArrayDeque로 슬라이딩 윈도우를 구현한다.(해당 deque는 현재 구간인 값들만 가지고 있으며, 오름차순으로 값의 순서를 유지한다. (front = 최소값))슬라이딩 윈도우를 오른쪽으로 한 칸씩 움직인다.구간에 신규로 추가될 값을 A라고 쳤을 때, A와 deque의 rear(꼬리)를 비교한다rear > A:..

0. 알아볼 것1. 슬라이딩 윈도우란?길이가 N인 1차원 배열안에 길이가 W인 움직이는 구간을 생성하여, 해당 구간을 한 칸씩 움직이면서 구간 내 정보를 추출하여 문제를 해결하는 기술(N과 W는 상수)W인 구간을 움직이는 것이 마치 창문을 밀고 당기는 것과 같다고 하여, 움직이는 구간을 슬라이딩 윈도우라고 명명함.2. 활용(1) 구간합1차원 배열에서 특정 구간 내의 합을 원하는 문제에서 활용.a. 어떻게 활용?배열의 길이가 N, 슬라이딩 윈도우의 길이가 W이고 해당 창문을 오른쪽으로 한 칸씩 움직인다면, 매 움직임 마다, 이전 위치에서의 W-1의 원소는 변하지 않고 구간 내에 유지된다. 예를 들어 N = 10, W = 3이라 가정하면,그림과 같이 W-1인 2개의 원소는 변하지 않았다.이를 활용해, 맨 처..

1. 문제 설명 📌문제 링크2. 접근 방식 🗃️KEY WORD: 누적 합, 이분 탐색동굴의 높이인 H와 깊이인 N이 각각 \(10^{5}\)이므로, 완전 탐색으로 하나의 행마다 모든 열을 조회한다면 1초에 \(10^{10}\)번 이상의 연산을 해야해서 시간 초과가 날 것이다.해당 문제는 *거꾸로 매달려 있는 종유석을 어떻게 처리할 것인가?* 에 대한 명확한 가이드라인만 계획할 수 있다면 풀 수 있는 문제이다. 종유석 처리방법에 따라 두 가지 방법으로 풀 수 있는데, 하나는 누적 합이고 다른 하나는 이분 탐색이다.(1) 누적합a. 결론 먼저1. "석순과 종유석 입력을 분류하여 Y축 위치에 따른 각 산물의 위치를 저장하는 배열 구현"2. "각 배열의 누적합 구하기 (석순 누적합 배열을 sum_S[i], ..