[CH03-1] 배열, 리스트, 구간합, 슬라이딩윈도우, 투포인터

배열과 리스트

• 배열 : 연속된 메모리의 공간에 값이 채워져있는 형태의 자료구조
  • 인덱스를 사용해 바로 접근 가능
  • 값을 삽입하거나 삭제하려면 많은 연산시간 필요
  • 배열의 크기는 처음 선언할때 지정. 불변
  • 구조가 단순
• 리스트 : 값과 포인터를 묶은 노드를 포인터로 연결한 자료구조
  - 인덱스가 없기 때문에 값에 접근하는 속도가 느림
  - 포인터로 노드가 연결되어있기 때문에 삭제, 삽입에 빠른 시간
  - 크기를 별도 지정하지 않음 => 크기가 정해지지 않은 데이터 다루기 용이
  - 배열보다 구조가 복잡(노드+포인터)

  구간합

• 배열을 이용해 시간 복잡도를 줄이기 위한 알고리즘
  • 만일, 특정 구간의 합을 구한다면 일반 배열은 O(N)의 시간 복잡도가 요구된다. 그러나 구간합을 이용한다면, A[N]-A[M], 즉 O(1)의 시간 복잡도가 발생한다.

  [백준 11660번] 구간합 구하기 5

• 내 코드

  import java.io.*;
  import java.util.*;
  class Main{
  	public static void main(String[] args) throws IOException {
  		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  		StringTokenizer st = new StringTokenizer(br.readLine());
  		int n = Integer.parseInt(st.nextToken());
  		int m = Integer.parseInt(st.nextToken());
  		// 구간합 맵 만들기
  		int[][] map = new int[n+1][n+1];
  		int[][] prepix = new int[n+1][n+1];
  		for(int i=1; i<n+1; i++) {
  			int[] arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
  			for(int j=1; j<n+1; j++) {
  				map[i][j] = arr[j-1];
  				prepix[i][j] = prepix[i][j-1]+prepix[i-1][j]-prepix[i-1][j-1]+arr[j-1];
  			}
  		}
  		// m만큼 실행
  		for(int i=0; i<m; i++) {
  			st = new StringTokenizer(br.readLine());
  			int x1 = Integer.parseInt(st.nextToken());
  			int y1 = Integer.parseInt(st.nextToken());
  			int x2 = Integer.parseInt(st.nextToken());
  			int y2 = Integer.parseInt(st.nextToken());
  			int result = prepix[x2][y2]-prepix[x2][y1-1]-prepix[x1-1][y2]+prepix[x1-1][y1-1];
  			System.out.println(result);
  		}
  	
  	}
  }

#### [[백준 10986번]](https://www.acmicpc.net/problem/10986) 나머지합 구하기

import java.io.;
import java.util.;
class Main{
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
long cnt = 0;
long[] prefix = new long[n];
long[] arr = new long[m];
st = new StringTokenizer(br.readLine());
prefix[0] = Integer.parseInt(st.nextToken());
for(int i=1; i<n; i++) {
prefix[i] = prefix[i-1]+Integer.parseInt(st.nextToken());
}
for(int i=0; i<n; i++) {
int r = (int) (prefix[i]%m);
if(r==0) cnt++;
arr[r]++;
}
for(int i=0; i<m; i++) {
if(arr[i]>1) cnt+=arr[i]*(arr[i]-1)/2;
}
System.out.println(cnt);

}

}

### 투포인터
- 2개의 포인터를 이용해 시간복잡도를 최적화하는 알고리즘
- start, end index가 둘 다 0인 경우와, 처음과 끝인 경우를 구분하는 점이 어려웠던 알고리즘

#### [[백준 1940번]](https://www.acmicpc.net/problem/1940) 주몽의 명령

import java.io.;
import java.util.;
class Main{
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int m = Integer.parseInt(br.readLine());
int[] arr = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i=0; i<arr.length; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr);
int start = 0;
int end = n-1;
int cnt = 0;
while(start<end) {
int k = arr[start]+arr[end];
if(k == m) {
cnt++;
start++;
end--;
} else if(k<m) {
start++;
} else {
end--;
}
}
System.out.println(cnt);
}
}

### 슬라이딩윈도우
- 두개의 포인터로 범위를 지정한 다음, 그 범위를 유지한 채로 이동하며 문제를 해결하는 알고리즘

#### [[백준 12891번]] (https://www.acmicpc.net/problem/12891) DNA 비밀번호

import java.io.;
import java.util.;
class Main{
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int p = Integer.parseInt(st.nextToken());
String[] arr = br.readLine().split("");
st = new StringTokenizer(br.readLine());
int[] cnt = new int[4];
for(int i=0; i<cnt.length; i++) {
cnt[i] = Integer.parseInt(st.nextToken());
}
int result = 0;
int[] window = new int[4];
for(int i=0; i<p; i++) {
if(arr[i].equals("A")) window[0]++;
else if(arr[i].equals("C")) window[1]++;
else if(arr[i].equals("G")) window[2]++;
else if(arr[i].equals("T")) window[3]++;
}
for(int i=0; i<4; i++) {
if(window[i]<cnt[i]) break;
if(i==3) result++;
}
for(int i=1; i<s-p+1; i++) {

		if(arr[i-1].equals("A")) window[0]--;
		else if(arr[i-1].equals("C")) window[1]--;
		else if(arr[i-1].equals("G")) window[2]--;
		else if(arr[i-1].equals("T")) window[3]--;
		
		if(arr[i+p-1].equals("A")) window[0]++;
		else if(arr[i+p-1].equals("C")) window[1]++;
		else if(arr[i+p-1].equals("G")) window[2]++;
		else if(arr[i+p-1].equals("T")) window[3]++;
		
		
		for(int j=0; j<4; j++) {
			if(window[j]<cnt[j]) {
				break;
			}
			if(j==3) {
				result++;
			}
		}
	}
	System.out.println(result);
}

}