[알고리즘 개념] Shorten time technique

누적합

좌표압축

LR Technique

+1-1테크닉

전처리

투포인터

 

누적합

배열이 주어지고, n번 인덱스부터 m번 인덱스까지 더한 값을 구하라는 문제가 있을 때, 브루트포스로 풀면 하나하나 더해야 하므로 시간복잡도가 O(n)이 된다.

 

하지만, (위와 같이 현재 인덱-스의 값 + 이전 인덱스를 모두 더한 값을 저장하는 배열)을 만들면, m번 인덱스에서 n번 인덱스를 빼면 문제에서 원하는 값이 바로 나온다. 이렇게 누적합을 사용하면 시간복잡도가 O(1)이 된다.

 

이차원 배열에서는 조금 더 복잡하다.

 

이러한 배열이 있고, (a,b)에서 (c,d) 만큼 더한 값을 구하라고 하였을 때, 부분합을 이용해서 구하면 빠르다.

 

 

위 배열이 부분합이다. 각각의 인덱스는 (0,0)에서 해당 인덱스까지의 합을 의미한다. 각각의 부분합을 구하는 점화식은 

부분합[i][j] = 부분합[i-1][j] + 부분합[i][j-1] - 부분합 [i-1][j-1] + 배열[i][j] 이다. 

부분합[i-1][j] + 부분합[i][j-1] 을 해서 중복되는 부분인 부분합[i-1][j-1]은 뺀다. 여기서 원하는 곳의 합을 구하는 방법은 

 

부분합이 arr이라고 하고, (x1,y1)에서 (x2,y2)의 합을 구한다고 했을 때

arr[x2][y2] - arr[x1-1][y2] - arr[x2][y1-1] + arr[x1][y2]를 하면 된다.

여기서도 arr[x1-1][y2] - arr[x2][y1-1] 를 하는 과정에서 중복으로 빠진 부분을 + arr[x1][y2]로 채웠다.

 

 

좌표압축

위와 같이 관계가 주어지고, 1과 연관되어있는 노드 수를 출력하는 문제가 나오면 List를 이용해서 해당 값에 해당하는 인덱스에 관계된 값을 넣어 DFS를 진행한다. 

하지만 위와 같이 10^9의 수를 가진 노드가 존재한다면 LIst를 10^9개 만들어야하므로 시간적, 메모리적 낭비가 심하다. 그래서 각 노드에 번호를 붙여서 

이와 같이 만들어두고 푸는 것이 좌표압축이다.

 

좌표압축의 과정은

위와 같이 사용되는 모든 수를 TreeSet에 넣은 후(중복되는 수들은 거르고 , 수들을 정렬해서 저장하는 역할을 한다.)

HashMap에 차례로 수를 묶어서 넣는다.

그 다음 위와 같이 edges 배열을 새로운 노드번호로 수정해준다.

 

 

 

LR Technique

이렇게 배열이 주어지고, 배열n 을 제외하고 위와 같이 앞,뒤의 차이를 모두 더한 값을 출력하라는 문제가 있다고 가정하자.

이 문제를 브루트포스로 풀면 시간복잡도가 O(n)이다. 하지만 LRTechnique를 이용하면 O(1)로 풀 수 있다 

위와 같이 L과 R의 배열을 만들고, L은 해당 인덱스보다 앞의 인덱스와의 차이 + L[인덱스-1]의 값을 의미하고, R은 해당 인덱스보다 뒤의 인덱스와의 차이 + R[인덱스 +1]의 값을 의미한다.

 

 

이렇게 n의 인덱스보다 앞의 값은 L을 이용해서 바로 구할 수 있고, 뒤의 값은 R을 이용해서 구할 수 있다. 여기에다가 n의 바로 앞, 뒤의 인덱스의 차이를 더하면 답이 바로 나온다. 이 원리는 앞서 설명했던 부분합과 유사하다.

 

-1+1테크닉

-1+1테크닉은 위와 같이 특정 위치에 겹치는 줄의 수를 알아내는데 유리한 알고리즘이다.

 

이를 브루트포스로 풀면, O(n)으로 직선마다 저 위치가 겹치는지 확인하는 과정이 필요하다.

하지만

 

이와 같이 직선의 가장 왼쪽 부분에는 +1을 하고 오른쪽 부분에는 -1을 하고, 0부터 k까지 계속 덧셈을 하면 직선 하나가 지나가면 +1과 -1이 더해지므로, 값에 영향을 미치지 않는다.(0이 더해지므로) 

 

 

전처리

위와 같이 특정한 위치보다 뒤에 있는 값 중 최솟값을 구하는 문제가 있다고 하자. 이 때 브루트포스로 푼다면 O(n)의 시간복잡도가 나온다.

하지만 위와 같이 끝에서부터 최솟값을 구해나가면서 왼쪽으로 가는 과정을 거쳐 R이라는 배열을 하나 더 만든다면 특정 위치가 주어졌을 때 Arr의 해당 인덱스 값과 R의 해당 인덱스 값을 곱하면 바로 원하는 값이 출력되어 시간복잡도가 O(1)이 된다.

 

투포인터

투포인터는 두 곳을 가르키는 변수가 있고 이 두 변수를 옮겨가면서 문제를 푸는 방식입니다.

이러한 문제가 있을 때, 브루트포스로 풀면 시간복잡도가 O(n^3)이 됩니다. 하지만, 이를 투포인터를 이용해서 O(n)으로 풀 수 있습니다.

위와 같이 i와 j를 투포인터로 만들고, for문을 이용해서 i값을 차례로 오른쪽으로 옮깁니다. 이 때 한번 for문이 돌 때마다 가능한 최대한으로 길게 j를 오른쪽으로 밀고, i와 j의 차이가 답보다 크다면 갱신합니다(현재 가장 긴 배열의 길이니까) 끝까지 다 돌게 되면 답이 나오는 것을 알 수 있습니다.

 

 

출처 : 코드트리

https://www.codetree.ai/missions/8/problems/sum-of-n-integers-2/introduction

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석