투포인터를 이용한 알고리즘 문제를 풀어보겠다. 투포인터에 대해 궁금하다면 아래의 글을 보고 오셔도 되궁 구글링해도 되궁  지피티한테 물어봐도 되궁  O(n) 투 포인터O(n) 의 시간 복잡도를 갖는 알고리즘을 사용 해야 할때 자주 사용하는 방식인 투 포인터. start_index와 end_index 두개의 index를 사용하여 이동시키면서 원하는 값을 찾는 문제이다.   [ 투 포인터henniee.tistory.com import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;import java.io.InputStreamReader;import java.io.OutputStreamWriter;import j..

O(n) 의 시간 복잡도를 갖는 알고리즘을 사용 해야 할때 자주 사용하는 방식인 투 포인터. start_index와 end_index 두개의 index를 사용하여 이동시키면서 원하는 값을 찾는 문제이다.   [ 투 포인터 이동 원칙 ]sum > N  : sum = sum - start_index; start_index++; sum sum == N : end_index++; sum = sum + end_index; count ++;  [ 슈도코드 작성해보기 ]int count = 1, sum = 1, start_index = 1, end_index = 1;int N = 어떤 값 ; while (end_index != N) {if (sum == N) { end_index++; sum = sum + end_..

[구간 합]구간 합은 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘이다. [구간 합의 핵심 이론] 구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야 한다. 배열 A 가 있을 때 합 배열 S는 아래와 같이 정의한다. S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i];  이게 무슨 말이냐 하면, 배열의 0번째 인덱스부터 마지막 인덱스까지의 모든 숫자를 하나씩 합쳐 가며 배열을 만드는 것이다.  [합배열을 만드는 공식]S[i] = S[i-1] +A[i]  [구간 합을 구하는 공식] S[j] = S[i -1]; //j에는 마지막 배열의 값 i 는 시작 인덱스 번호 예를 들면 이렇게 구하고자 하는 마지막 인덱스(j) - 시작 인덱스 (i..

배열의 구간합을 구하는 문제로 2번이나 시간초과로 실패 되었다. 이유는 1. Scanner 사용 2. 배열을 모두 순회하는 for 문 사용 이었는데 코드는 아래와 같다. 더보기import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); //n개 5 int m = sc.nextInt(); //m번 3 int number [] = new int[n]; for (int i = 0; i  [개선]그리고 나서 개선 된 것이 구간합이라는 것을 사용하여 배열을 애초에 꾸리는 방법이다. im..