구간합 & 투 포인터 & 슬라이딩 윈도우
구간 합
구간 합은 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘입니다.
배열 A가 있을 때 합 배열 S는 다음과 같이 정의합니다.
합 배열 S
S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i]
합 배열은 기존의 배열을 전처리한 배열이라고 생각하면 됩니다. 이렇게 합 배열을 미리 구해놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(n)에서 O(1)로 감소합니다.
책 p 42 인덱스 / 배열 / 합배열 그림 참고
합 배열 S를 만드는 공식
S[i] = S[i-1] + A[i]
구간 합을 구하는 공식
S[j] - S[i-1] : i에서 j까지의 구간 합
풀어볼 문제
문제 003 - 구간 합 구하기 (11659)
BufferedReader + StringTokenizer VS Scanner class
입력 데이터를 처리하기 위해 Java로 작업할 때 입력을 읽고 구문 분석할 수 있는 몇 가지 옵션이 있습니다. 두 가지 일반적인 방법은 Scanner.nextInt를 사용하는 것과 StringTokenizer와 결합된 BufferedReader를 사용하는 것입니다. 두 방법 모두 동일한 목적을 수행하지만 성능 및 구현 측면에서 약간의 차이가 있습니다.
- '스캐너':
- 스캐너는 InputStream, File 등과 같은 다양한 소스에서 입력을 읽을 수 있는 메서드를 제공하는 Java의 유틸리티 클래스입니다. 정규식을 사용하여 기본 유형 및 문자열을 구문 분석할 수 있습니다.
Scanner.nextInt사용 시 입력을 직접 정수로 읽어옵니다. 구문 분석 및 유형 변환을 자동으로 처리하기 때문에 간단한 경우에 더 편리할 수 있습니다.- 그러나 Scanner는 일반적으로 BufferedReader보다 느립니다. 특히 많은 양의 데이터를 처리할 때 구문 분석에 정규식을 사용하기 때문에 계산 비용이 많이 들 수 있습니다.
BufferedReader와StringTokenizer:
- BufferedReader는 문자, 배열 및 행을 효율적으로 읽을 수 있도록 문자를 버퍼링하여 문자 입력 스트림에서 텍스트를 읽는 데 사용되는 Java의 클래스입니다.
- StringTokenizer는 지정된 구분 기호에 따라 문자열을 토큰(하위 문자열)으로 나누는 Java의 유틸리티 클래스입니다.
- StringTokenizer와 함께 BufferedReader를 사용하려면 입력을 문자열로 읽은 다음 지정된 구분 기호(예: 공백)를 기준으로 문자열을 토큰화하고 Integer.parseInt() 또는 유사한 메서드를 사용하여 토큰을 정수(또는 다른 유형)로 변환해야 합니다. 이 접근 방식을 사용하면 입력 구문 분석 프로세스를 더 잘 제어할 수 있습니다.
- 이 조합은 특히 많은 양의 데이터로 작업할 때 스캐너를 사용하는 것보다 빠릅니다. 정규 표현식의 오버헤드를 피하고 효율적인 버퍼 읽기가 가능하기 때문입니다.
요약하면 StringTokenizer와 함께 Scanner.nextInt 및 BufferedReader를 사용하는 것의 주요 차이점은 성능과 입력 구문 분석에 대해 제공하는 제어 수준에 있습니다. 스캐너는 단순한 경우에 더 편리하고 사용하기 쉽지만 속도가 느릴 수 있는 반면 StringTokenizer가 포함된 BufferedReader는 특히 큰 입력 데이터를 처리할 때 구문 분석에 대해 더 나은 성능과 더 많은 제어를 제공합니다.
풀어볼 문제
문제 004 - 구간 합 구하기2 (11660)
문제 005 - 나머지 합 구하기(10986)
투 포인터
투 포인터는 2개의 포인터로 알고리즘의 시간 복잡도를 최적화한다.
풀어볼 문제
문제 006 - 연속된 자연수의 합 구하기(2018)
문제 007 - 주몽의 명령(1940)
문제 008 - 좋은 수 구하기(1253)
슬라이딩 윈도우
슬라이딩 윈도우 알고리즘은 2개의 포인터로 범위를 지정한 다음 범위(window)를 유지한 채로 이동(sliding)하며 문제를 해결합니다. 투 포인트 알고리즘과 매우 비슷하고, 원리도 간단합니다.
풀어볼 문제