1. 문제 설명 📌문제 링크두 배열의 구간합끼리 더해서 목표값인 T가 나오는 횟수를 세는 문제2. 접근 방식 🗃️KEY WORD: Two Pointer, Range sum이번 문제는 각 배열에서 나올 수 있는 구간합을 모두 구해서 List 화 시킨 뒤에, 이 두 List에서 값을 각각 꺼내어 보며, T가 될 수 있는 경우의 수를 세야한다. 한마디로 요약하면 구간합 후보군들 사이에서 Two Pointer로 요약할 수 있다.(1) 왜 그렇게 풀어야 하나요?답: 배열의 원소로 음수가 존재이 문제의 까다로운 점은 배열의 원소로 음수가 존재할 수 있다는 것이다. 누적합을 활용한 구간합을 구하는데 기본이 되는 전제 조건은 "right 포인터를 늘리면 구간합이 커진다. left 포인터를 늘리면 구간합이 줄어든다...

1. 문제 설명 📌https://www.acmicpc.net/problem/1806 문제가 직관적이라 설명 생략!2. 접근 방식 🗃️KEY WORD: TWO POINTER목표값 보다 Two Pointer 구간 내의 합이 작으면 오른쪽 포인터 이동목표값 보다 크거나 같으면 왼쪽 포인터 이동구간 내 합이 목표값 이상이면 Math.min(이전까지의 최소 개수, 현재 개수)로 최소값 갱신3. 코드 소개 🔎import java.io.*;import java.util.*;public class Main { /* * KEY WORD: 투 포인터 * 1. 목표값보다 작으면 오른쪽 포인터 이동 * 2. 목표값보다 크거나 같으면 왼쪽 포인터 이동 * 3. 목표값과 일치하면 그 개수를 뽑아내..

1. 구간합 기술이란?1차원 배열에서 특정 구간 내의 원소들의 합을 구하는 알고리즘이다.2. 왜 써야 하는가?위의 예시에서 A에서 B까지의 구간 합을 구한다면, 어떻게 구할 것인가? 혹자는 2번 index부터 7번 index까지 for 반복문을 활용해 차례대로 더할 것이다. 혹자는 0에서 A번까지의 누적합을 구하고, 0~B번까지의 누적합을 구해, 둘을 빼서 구할 것이다. 만약 단일 계산이라면, 이런 식의 풀이는 n번의 반복일 뿐이니 괜찮을 수 있다. 하지만, 문제에서 여러 개의 구간합을 반환하길 바란다면? 매번 이러한 반복문을 반복하는 것은 비효율적이다. 이는 시간 초과로 이어질 수 있다.시간 복잡도로 계산해 보겠다. 최악을 상정해야하니, N개의 원소를 가진 배열에서 0~ N~1까지의 계산을 K번 반복한..

1. 문제 설명 📌문제 링크문제의 설명만 보면 이해하기가 어려운데, 밑의 시뮬레이터를 보면 문제에서 주어진 조건과 로봇의 작동원리는 이해할 만하다.하지만 헷갈리는 것이 있다면 바로, points와 routes의 의미 및 관계라고 할 수 있겠다.(1) 헷갈리는 것 바로 잡기points: 로봇이 방문해야하는 지점의 좌표를 배열 형태로 저장해놓았다.points[i]일 때, 이 i가 방문할 지점의 번호 이고, point[i]의 value가 각각 i란 지점의 행과 열 즉 좌표이다.routes; 로봇별로 방문해야할 지점을 순서대로 나열한 1차원 배열의 묶음이다.routes[i]의 i는 로봇의 번호이고, routes[i]에는 로봇이 방문해야할 지점의 번호가 순서대로 저장되어 있다.예를 들어, routes[2] = ..

1. 문제 설명문제 설명2. 접근 방식KEY WORD: Sliding Window, 나머지 연산아이디어를 떠올리기가 어려워서 다른 사람의 풀이 블로그에서 아이디어 부분까지만 봤다.나는 a와 b를 일일히 교환하는데만 집중하고 있었는데, 완전히 잘못된 접근 방식이었다. 그러한 방식으로 풀었을 때, 최소값을 어떻게 찾을 수 있을지 감이 안온다. 문제를 푸는 방식은 다음과 같다. 문자열 내의 a의 개수를 세고, 그 개수를 용량으로 하는 Sliding window를 만든다.문자열의 처음부터, 1번에서 센 슬라이딩 윈도우의 용량만큼 a와 b의 개수를 센다. b의 개수 == 교환이 일어나는 횟수 이다. 현재 a의 개수만큼씩 배열을 확인하고 있고, 거기서 b의 개수를 전부 a로 돌린다면, 연속된 a와 연속된 b가 ..

1. 이분 탐색 (binary-search)란 무엇인가요?이분 탐색(binary-search)이란, 정렬된 상태의 일련의 데이터 중 현 기점에서 답 후보가 될 수 없는 절반을 삭제해가며 답을 찾아내는 탐색 알고리즘 이다. 다음과 같이 정렬된 10개의 정수가 배열 형태로 주어져 있다고 하자. 우리는 여기서 23이란 수를 찾고자 한다.(1) 먼저 목표값과 비교할 기준을 구해야 한다. 기준은 항상 값을 구해야 하는 구간의 중앙값이다. (짝수면은 중앙의 두 개의 값 중 앞 쪽 값이다.)(2) 16을 23과 비교해보니, 작다. 이 말은 즉 '16의 앞쪽 원소들도 목표 값보다 작다.' 는 말이 된다. 왜냐하면 이미 오름차순으로 정렬된 상태에서 탐색을 시작했기 때문이다. 따라서 16과 그 앞 쪽의 수들은 전부 날린다..