SK_MOUSE 개발일기

투포인터 https://www.youtube.com/watch?v=rI8NRQsAS_s 투포인터,구간합 알고리즘 강의 나동빈 처음에는 투포인터 문제인지 모르고 풀었다. 그 풀이는 아래와 같다. 풀이 한 코드가 너무 아까워서 남겨둔 것이니, 투포인터 풀이를 보려면 더 아래로 내려가서 확인하면 된다. import java.util.*; import java.io.*; public class Main { static int n; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // StringTokenizer st = n..

문제를 통해 배울점은 두가지였다. 1. 구간합 : 투 포인터 알고리즘(Deque와 같음) 2. 누적합의 최적화 1. 구간합 : 투 포인터 알고리즘(Deque와 같음) 먼저 일정한 길이의 구간을 계속해서 더해야 될때의 투포인터 알고리즘을 설명해보겠다. 아래와 같이 구간의 길이가 3이락 할때, 구간의 합이 최대인 구간을 구하려고 한다. => 전에 구한 구간합에서 가장 첫 원소를 빼고 다음 원소 하나를 더해주면 다음 구간합과 같다. 위 알고리즘을 적용한코드는 아래와 같다. //Deque처럼 이전값의 맨앞값 빼고 새로운값 더하기 for(int i=advTime; imax){//최대값 비교 max=sum; maxStartTime=i-advTime+1; } before=sum; } 2. 누적합의 최적화 누적합의 최..