명이나물 라이브러리

투포인터 알고리즘1. 투포인터란?투포인터는 배열이나 리스트에서 두 개의 인덱스, 즉 포인터를 사용해 원하는 조건을 만족하는 값을 효율적으로 찾는 알고리즘 기법이다.보통 left, right 또는 start, end라는 이름의 변수를 사용한다.예를 들어 배열이 다음과 같이 있을 때,int[] arr = {1, 2, 3, 4, 5};두 개의 포인터를 사용해 특정 구간을 살펴보거나, 두 수의 합을 비교할 수 있다.[1, 2, 3, 4, 5] L R여기서 L은 왼쪽 포인터, R은 오른쪽 포인터다.2. 투포인터를 사용하는 이유배열에서 두 수를 고르거나, 연속된 구간의 합을 구하는 문제를 단순하게 풀면 보통 이중 반복문을 사용하게 된다.for (int i = 0; i 이 방식의 시간복잡도는 O(N..

연속된 부분 수열의 합 Java 풀이 — 투포인터로 시간초과 해결하기1. 문제 소개이번에 풀어본 문제는 프로그래머스 Lv.2 문제인 연속된 부분 수열의 합이다.문제에서는 비내림차순으로 정렬된 정수 배열 sequence와 정수 k가 주어진다.이때 합이 k가 되는 연속된 부분 수열을 찾아, 해당 구간의 시작 인덱스와 마지막 인덱스를 배열로 반환해야 한다.조건은 다음과 같다.부분 수열의 합은 k여야 한다.합이 k인 부분 수열이 여러 개라면 길이가 가장 짧은 수열을 선택한다.길이도 같다면 시작 인덱스가 더 작은 수열을 선택한다.처음에는 단순히 모든 구간의 합을 구하면 되지 않을까 생각했다.하지만 제한사항을 보고 완전탐색으로는 풀기 어렵다는 것을 알 수 있었다.2. 제한사항 확인문제의 제한사항은 다음과 같다.5 ..