ezhoon

📖 문제 첫 번째 줄에 수열의 길이인 자연수 N 과 k입력 두 번째 줄에는 N길이의 0과 1로 구성된 수열 입력 최대 k번 0을 1로 변경할 수 있다. 1로만 구성된 최대 길이의 연속부분수열의 길이를 출력 ⚠️ 주의사항 Two Pointer사용 0부터 ~ N-1 까지 이므로 길이 구할 때 조심해야함 ✍️ 이해 * 1. 길이가 N인 수열, k 번의 변경 횟수 * 2. 길이가 N인 윈도우 생성 * 3. 0을 만날때마다 1로 바꿔줬다고 가정하고 cnt++ * 3-1. rt가 N까지 반복 * 3-1-1. rt == 0 -> cnt ++ * 3-2. cnt > k 인 경우 반복 * 3-2-1. lt == 0 -> cnt --, lt++ * 3-3 answer = Math.max(answer, rt -lt + 1)..

📖 문제 첫 번째 줄에 양의 정수 N가 주어진다. 2개 이상의 연속된 자연수의 합으로 정수 N을 표현하는 방법의 가짓수를 출력 N이 15이면 7 + 8 = 15 / 4 + 5 +6 = 15 / 1 + 2 + 3 + 4 + 5 = 15 총 3가지의 경우가 존재한다. ⚠️ 주의사항 two pointer 사용 예제 - [인프런] 03_04 연속 부분 수열 (Two pointers) ✍️ 이해 * 1. 정수 N 만큼의 배열 생성 15면 1 ~ 14까지의 배열 arr 생성 * 2. pointer) left, right = 0 * 3. right 값이 N - 2 될 때 까지 반복 * 3-1. sum sum += arr[++right] * 3-2. sum > N -> sum -= arr[left++] *..

📖 문제 첫째 줄 N, 특정 숫자 M이 주어진다. 둘째 줄에는 N개의 수로 이루어진 수열이 주어진다. 수열의 합이 특정숫자 M이 되는 경우가 몇 번 있는지 구하시오 N = 8, M = 6인 경우 아래와 같은 배열을 가지면 3가지 입니다. {2, 1, 3}, {1, 3, 1, 1}, {3, 1, 1, 1} ⚠️ 주의사항 Two pointers 알고리즘 풀 때 한 개의 배열일 때는 어떻게 해야 할지 수열의 마지막을 벗어나지 않게 조심하기 2022.01.21 - [인프런_자바_알고리즘_기초/Two pointers, Sliding window] - 투 포인터란? ✍️ 이해 * 1. N개의 배열 M이 되는 경우 * 2. 투 포인터 방식으로 left, right 변수 선언 * 2-1. sum = left ~ rig..

투 포인터와 슬라이딩 윈도우 두 알골리즘은 1차원 배열을 2회 이상 반복적으로 탐색해야 할 경우 O(N^2) 이상 걸릴 시간 복잡도를 부분 배열을 활용하여 O(N)으로 줄일 수 있다는 공통점이 있습니다. 이 두 알고리즘의 차이는 사용자가 찾고자 하는 부분 배열의 길이의 변화 여부 입니다. 투 포인터 (가변적 길이) 슬라이딩 윈도우 (고정적 길이) 투 포인터 길이가 가변적인 부분 배열들을 활용하여 특정 조건을 일치시키는 알고리즘 입니다. 예시로 두 배열이 주어지고 그 배열의 공통 원소를 구한다고 할 때, 배열을 정렬 후 각 배열의 포인터를 하나씩 만들어 준 다음 같은 값이 나오면 두 포인터 다 + 1 만약 같은 값이 안나왔을 경우 더 작은 값의 포인터는 그대로 둔 뒤 더 작은 값의 배열의 포인터를 +1 해..

📖 문제 첫 줄에 N과 K가 주어진다. 두 번째 줄에 N개의 숫자열이 주어진다. N일 동안의 매출기록을 주고 연속된 K일 동안의 최대 매출액이 얼마인지 구하시오. ⚠️ 주의사항 for문을 다 돌려서 할 수도 있지만 슬라이딩 윈도우 방식으로 해결 해보겠습니다. ✍️ 이해 슬라이딩 윈도우 방식이란 배열의 처음부터 순차적으로 탐색하고 부분 배열을 꺼내 보는 것입니다. 이때 부분 배열의 길이는 고정적(일정)합니다. 참고 블로그 아래와 같은 배열이 주어지고 10일 동안의 매출 중에 3일 동안의 최대 매출액은 얼마인지 구할려고 해보겠습니다. 0 1 2 3 4 5 6 7 8 9 12 15 11 20 25 10 20 19 13 15 * 슬라이딩 윈도우 방식으로 해결 * 1. N개 만큼의 숫자열 입력, K입력 * 2. ..

📖 문제 A(N개)와 B(M개) 두 개의 집합이 주어지면 두 집합의 공통 원소를 추출 후 오름차순으로 출력하시오 ⚠️ 주의사항 집합 A와 B는 정렬 돼 있지 않다. pointer로 비교하기 위해서는 A와 B를 먼저 정렬 후 해결해야 한다. ✍️ 이해 * 1. N 개의 집합 A, M 개의 잡합 B 입력 * 2. Arrays.sort(A), Arrays.sort(B) * 3. pi -> A의 pointer, pj -> B의 pointer * 3-1. A[0]B[0] A[1]B[1] ~ A[N-1]B[N-1] 비교해서 같은게 있으면 answer배열에 추가 * 3-2. 중복되면 안되므로 answer에 add * 4. return answer ✏️ 풀이 import java.io.BufferedReader; im..

📖 문제 첫 번째 줄에 배열의 크기인 N 입력 두 번째 줄에 N개의 배열 원소가 오름차순으로 주어진다. 세 번째 줄에 배열의 크기인 M 입력 네 번째 줄에 M개의 배열 원소가 오름차순으로 주어진다 두 배열을 오름차순으로 합쳐 출력하는 프로그램을 작성하시오. ⚠️ 주의사항 N개의 배열 원소, M개의 배열 원소 오름차순이다. 두 배열을 합친 배열도 오름차순이다. ✍️ 이해 내가 풀 때 적었던 풀이 방법 * 1. 1차원 배열 입력 2개 받기 N개와 M개 * 2. 한개로 합쳐서 내림차순 해야 하므로 answer[N+M] 에 각각 누적시킨다 * 2-1. N은 i = 0 ~ N -> answer[i] * 2-2. M은 i = N ~ N+M -> answer[i] * 2-2-1. M의 값을 answer[i]에 넣을 ..