1. 문제
(3, 6, 2, 6, 7, 5, 2)와 같은 숫자가 주어지면, 다음 질문에 답하는 프로그램을 작성하세요.
그러나 각 쿼리에 대해 하나의 번호가 제공됩니다.
첫 번째 숫자를 제외하고 다른 숫자의 경우 인접한 숫자 간의 차이의 합을 찾아야 합니다.
예를 들어 쿼리에 5가 지정된 경우 다섯 번째 숫자인 7을 제외한 모든 숫자를 나열하면, (3, 6, 2, 6, 5, 2)
인접한 숫자 간의 차이의 합은 다음과 같습니다.
|3 – 6| + |6 – 2| + |2 – 6| + |6 – 5| + |5 – 2| = 15.
이때 주어진 숫자는 1보다 크고 N보다 작다고 가정하는 것이 안전합니다.
————————————————– ————————————————————–
함부로 코드를 작성하면 숫자가 주어질 때마다 나머지 숫자 N-1을 순회하면서 O(N) 시간이 걸리고,
Q 쿼리가 있는 경우 시간 복잡도는 O(QN)입니다.
하지만 조금만 생각하면 놀라운 방법으로 개선될 수 있습니다.
예를 들어 4번째 숫자를 제외하면 답을 찾는 과정은…
5번째 숫자를 빼면 답을 찾는 과정은…
자세히 보면 연산이 겹친다.
. 적어도 배열의 (1,3) 부분은 연산이 겹친다.
$L_{i}$가 1에서 i까지 인접한 숫자 사이의 쌍별 차이의 합인 경우
$R_{i}$를 i에서 N까지 인접한 숫자 쌍의 차이의 합이라고 하고 L,R 배열을 얻으면…
그러면 i번째 숫자를 제외하면 인접한 숫자의 합을 더 빨리 찾을 수 있습니다.
이제 예를 들어 4번째 숫자를 제외하면…
이미 L배열을 구했다면 (1,3)까지의 합은 이미 7로 구한 것이다.
그리고 이미 R 배열을 찾았다면 (5,7)까지의 합은 이미 5로 찾았습니다.
따라서… $L_{3}$와 $R_{5}$의 합에 3번과 5번의 차이의 합만 더하면… 쿼리에 답할 수 있습니다.
일반적으로 i번째 숫자를 제외하면… $L_{i-1} + R_{i+1} + \left|A_{i+1} – A_{i-1}\right|$ .
L,R 배열을 미리 구하면 질의당 O(1)에서 문제를 풀 수 있고, O(N)에서 L과 R 배열을 모두 구할 수 있다…
Q 쿼리는 O(N+Q)에서 얻을 수 있습니다.
이와 같이 왼쪽 방향의 L 배열과 오른쪽 방향의 R 배열을 각각 미리 구하여 중복되는 부분을 효과적으로 줄이는 기술을 LR 기술이라고 한다.
2. 구현 예
Java로 구현된 코드는 다음과 같습니다.
public class Main {
public static void main(String() args){
int() arr = new int(){0,3,6,2,6,7,5,2};
int() L = new int(8);
int() R = new int(8);
int n = 7;
//L배열을 채워준다.
L(1) = 0;
for(int i = 2; i <= n; i++){
L(i) = L(i-1) + Math.abs(arr(i) - arr(i-1));
}
//R배열을 미리 채워준다.
R(n) = 0;
for(int i = n-1; i >= 1; i--){
R(i) = R(i+1) + Math.abs(arr(i+1) - arr(i));
}
//4번째 숫자를 제외할때,
System.out.println(L(3)+R(5) + Math.abs(arr(5)-arr(3)));
}
}
Python으로 구현하면 .. 다음과 같습니다.
arr = (0,3,6,2,6,7,5,2)
L = (0)*8
R = (0)*8
n = 7
#L배열을 채워준다.
L(1) = 0
for i in range(2,n+1):
L(i) = L(i-1) + abs(arr(i) - arr(i-1))
#R배열을 채워준다.
R(n) = 0
for i in range(n-1,0,-1):
R(i) = R(i+1) + abs(arr(i+1) - arr(i))
#4번째 숫자를 제외했을 때 답 = 17
print(L(3) + R(5) + abs(arr(5)-arr(3)))
3. 운동
n개의 숫자가 주어졌을 때 서로 인접하지 않은 세 개의 숫자를 선택하여 합이 최대가 되도록 프로그램을 작성하세요.
4. 해결
꽤 어렵다??? 왜 쉬운 문제인가..?
핵심 아이디어는… 가운데로 이동하면서 왼쪽의 최대값 + 중간의 최대값 + 오른쪽의 최대값, 모두의 최대값을 얻습니다.
저장하는 것입니다
구체적으로..
$L_{i}$는 요소 0에서 i까지의 최대값입니다.
$R_{i}$는 요소 i에서 n-1까지의 최대값입니다.
따라서 i = 2,3,4,…,n-3에서 $A_{i}$에 대해 $L_{i-2} + A_{i} + R_{i+2}$의 최대값은당신은 찾을 필요가
특히 O(N)에서 L배열과 R배열을 얻을 수 있어야 한다.
L = (0)*n
R = (0)*n
for i in range(n):
L(i) = max(A(:i+1))
for i in range(n):
R(i) = max(A(i:))
인덱싱은 O(N)이므로 $O(N^{2})$에서 각 배열을 얻습니다.
그런데 조금 더 생각해보면… L배열의 경우…
0에서 i번째 요소까지의 최대값은 i-1번째 요소와 i번째 요소의 최대값 중 큰 값이 됩니다.
동적 프로그래밍에서는 이전 최대값을 사용하여 찾으면 O(N)에서 얻을 수 있습니다.
L = (0)*n
L(0) = A(0)
R = (0)*n
R(n-1) = A(n-1)
for i in range(1,n):
L(i) = max(L(i-1),A(i))
for i in range(n-2,-1,-1):
R(i) = max(R(i+1),A(i))
파이썬으로 구현하면…
from sys import stdin
n = int(stdin.readline())
A = list(map(int,stdin.readline().split()))
L = (0)*n
L(0) = A(0)
R = (0)*n
R(n-1) = A(n-1)
for i in range(1,n):
L(i) = max(L(i-1),A(i))
for i in range(n-2,-1,-1):
R(i) = max(R(i+1),A(i))
answer = 0
for i in range(2,n-2):
x = L(i-2) + A(i) + R(i+2)
if answer < x:
answer = x
print(answer)
자바의 경우…
import java.util.Scanner;
public class Main {
public static void main(String() args) {
// 여기에 코드를 작성해주세요.
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int() arr = new int(n);
for(int i = 0; i < n; i++){
arr(i) = sc.nextInt();
}
int() L = new int(n);
L(0) = arr(0);
int() R = new int(n);
R(n-1) = arr(n-1);
for(int i = 1; i < n; i++){
L(i) = Math.max(L(i-1),arr(i));
}
for(int i = n-2; i >= 0; i--){
R(i) = Math.max(R(i+1),arr(i));
}
int answer = 0;
for(int i = 2; i < n-2; i++){
int x = L(i-2) + arr(i) + R(i+2);
if(answer < x){
answer = x;
}
}
System.out.println(answer);
}
}