구간합
•
합 배열 S)
◦
정의)
◦
합 배열 만드는 방법) ,
◦
장점) 합 배열을 미리 구해놓음으로써 기존 배열의 일정 범위 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소함
◦
단점) A 배열의 값이 자주 바뀐다면, 합 배열 사용하기 어려움 (→ 세그먼트 트리, 인덱스 트리 사용하면 됨)
•
구간합)
◦
정의) 합 배열 이용해 시간 복잡도 줄이는 목적 가진 알고리즘
◦
1차원에서 구간 합 구하는 방법) i~j
▪
▪
합 배열 이용 → (i≥1) ,
◦
2차원에서 구간 합 구하는 방법) (x1,y1)~(x2,y2)
▪
▪
합 배열 이용 → (i>=1, j>=1),
◦
꿀팁) 입력값을 쉽게 변형 가능한 상황이라면 A[0], A[0][j], A[i][0] 은 전부 0으로 두고 실제 값은 A[1], A[1][j], A[i][1] 부터 시작하도록 하기
투 포인터
•
정의) 배열에서 이중 for문으로 으로 처리되는 작업을 2개 포인터(커서)의 움직임으로 에 해결하는 알고리즘
•
장점) 이중 for 문에선 i=0일 때, j가 0부터 n-1까지 돌고, i=1일 때, j가 0부터 n-1까지 도는 식으로 진행되고, i=0일 때 계산하면서 얻은 정보가 i=1일 때 전혀 쓰이지 않음. 반면, 투포인터는 i=0일 때 계산하면서 얻은 정보를 i=1일 때 활용함
•
특징)
◦
이분 탐색으로 투 포인터 문제 풀 수 있는 경우 많고, 투 포인터 문제를 이분 탐색으로 풀 수 있는 경우 많음
◦
1차원 배열에서의 “연속 부분 수열” 혹은 “순서를 지키며 차례대로”, “곱의 최소” 같은 키워드가 등장하면 투 포인터 접근 시도해볼 가치 있음
•
문제)
◦
백준 2230)
▪
설명) N개의 정수로 이루어진 수열({2,3,9,13,22})에서 두 수를 골랐을 때 그 차이가 M(6) 이상이면서 제일 작은 경우 구하기
▪
풀이)
•
이중 for문으로 푸는 경우, i=22에 대해 j={3,9,13,22}를 살펴보고, i=3에 대해 j={9,13,22}를 살펴보고 하는 식으로 두 수의 차이가 M 이상이면서 가장 작은 경우를 찾아나갈 수 있음
•
이때, 재밌는 점은 i=2에 대해 두 수의 차이가 M인 최초의 지점이 j=13이었다면, i=3에 대해 두 수의 차이가 M인 최초의 지점은 무조건 j가 13 이상이라는 점임. 즉 i가 증가할 때 j도 무조건 증가한다는 규칙이 존재함
•
이런 식으로 i=3에 대해 경우의 수를 찾을 때 j가 9인 경우는 볼 필요가 없다는 점에 착안해 나온 게 투 포인터임. 이전(i=2)에 계산하면서 얻은 정보를 다음(i=3)에 활용하는 거임
•
좀 더 직관적으로 명칭을 정하기 위해 i를 start, j를 end라 일컬어 보자
•
start=2일 때 end가 {3,9,13,22} 범위를 순회하게 한다. 이때 13이 되면 멈춤
•
start=3일 때 end는 {9,13,22} 범위를 순회하는 게 아니라 이전 값인 13에서 더 커져야 하기 때문에 {13,22} 범위만 순회함
•
단순 순회 범위의 차이처럼만 보일 수 있지만, 종료 시점을 보면 start가 끝에 도달하거나 end가 끝에 도달하면 종료하기 때문에 시간 복잡도가 O(N+M)임. 이중 for문으로 풀었던 O(N^2)보다 효율적임.
슬라이딩 윈도우
•
정의) 창문을 한쪽으로 밀면서 문제를 푸는 것과 유사해 이름 붙여진 알고리즘
•
특징)
◦
투 포인터처럼 구간을 훑으면서 지나간단 공통점 있으나, 어느 순간에도 그 구간의 넓이가 동일하다는 차이점이 있음
참고