Dec 27, 2024

1014. Best Sightseeing Pair

내 코드

처음에 TLE 나서 아이디어 GPT 참고..!

0ms, 45.56MB

// BruteForce 말고?
class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& values) {
        // 나누기 (gpt)
        // values[i] + i => left
        // values[j] - j => right
        int answer{}, left = values[0];
        for(int s{1}, e{static_cast<int>(values.size())}; s < e;++ s) {
            answer = max(answer, left + values[s] - s);
            left = max(left, values[s] + s);
        }
        return answer;
    }
};

GPT

문제 이해
LeetCode 1014번 Best Sightseeing Pair 문제는, 배열 values가 주어졌을 때,
$\text{score}(i, j) = \text{values}[i] + \text{values}[j] + i - j$
의 값이 최대가 되도록 하는 서로 다른 인덱스 $i, j$ ( $i < j$ )를 찾아 그 때의 $\text{score}(i, j)$ 를 구하는 문제입니다.

문제를 다시 쓰면?

크기 $n$ 인 배열 values가 있을 때, 인덱스 $i$ 와 $j$ ( $0 \leq i < j \leq n-1$ )를 하나씩 고른다.
그때의 점수는 values[i] + i + values[j] - j.
이 점수를 최대로 만들어야 한다.

핵심 아이디어

위 식을 조금 변형해보면 다음과 같이 두 부분으로 나누어 생각할 수 있습니다:

$\text{score}(i, j) = (\text{values}[i] + i) + (\text{values}[j] - j)$

즉,

왼쪽 지점( $i$ )에서의 $\text{values}[i] + i$
오른쪽 지점( $j$ )에서의 $\text{values}[j] - j$

이 두 값을 각각 크게 만들면 전체 점수가 커집니다.
중요한 점은 $i$ 가 고정된 상태에서의 최댓값이 아니라, $j$ 가 증가해가면서 가능한 여러 $i$ 중 $\text{values}[i] + i$ 가 최대인 값을 찾아야 한다는 것입니다.

단계별 접근

최댓값 보관(mx)
반복문을 왼쪽부터 오른쪽까지 진행하면서, 이전까지 봤던 모든 인덱스 $i$ 들에 대해 $\text{values}[i] + i$ 의 최댓값을 저장해둡니다.
- 즉, mx = max(mx, values[i] + i) 과 같은 형태로 업데이트합니다.
현재 인덱스 $j$ 에서의 점수 계산
현재 인덱스 $j$ 에 대해, 이미 구해둔 mx와 $\text{values}[j] - j$ 의 합이 바로 $\max_{i < j} (\text{values}[i] + i) \;+\; (\text{values}[j] - j)$ 이 되므로, 이를 이용해 그 시점에서의 가능한 최대 점수를 갱신합니다.
결과 갱신
- 매 반복에서 구한 점수 후보와, 지금까지의 최대 점수를 비교해 최대값으로 갱신합니다.
- 모든 $j$ 에 대해 이 과정을 반복한 후, 최종적으로 최대 점수를 출력하면 됩니다.

알고리즘 예시 (직관적 예시)

예를 들어, values = [8, 1, 5, 2, 6]라면,

i = 0일 때 values[0] + 0 = 8 + 0 = 8
- mx = 8이 됨.
j = 1로 왔을 때, mx + (values[1] - 1) = 8 + (1 - 1) = 8
- 최대 점수 후보는 8.
- 이어서 mx 갱신: mx = max(8, values[1] + 1) = max(8, 1 + 1) = 8.
j = 2로 왔을 때, mx + (values[2] - 2) = 8 + (5 - 2) = 11
- 최대 점수 후보는 11.
- mx 갱신: mx = max(8, values[2] + 2) = max(8, 5 + 2) = 7 (오타 아님?)
- 5 + 2 = 7인데 현재 mx = 8이므로 그대로 mx = 8.
j = 3일 때, mx + (values[3] - 3) = 8 + (2 - 3) = 7
- 후보는 7.
- mx 갱신: mx = max(8, values[3] + 3) = max(8, 2 + 3) = 8.
j = 4일 때, mx + (values[4] - 4) = 8 + (6 - 4) = 10
- 후보는 10.
- mx 갱신: mx = max(8, values[4] + 4) = max(8, 6 + 4) = 10.

이 중 가장 큰 후보가 11이므로, 최종 정답은 11이 됩니다.

시간 복잡도

한 번의 순회로, 각 단계에서 현재 인덱스 $j$ 에 대해 mx + (values[j] - j)를 계산하고 mx를 갱신하기만 하면 됩니다.
따라서 전체 알고리즘 시간 복잡도는 $O(n)$ 입니다.

파이썬 예시 코드

def maxScoreSightseeingPair(values):
    res = float('-inf')
    mx = float('-inf')
    
    for j in range(len(values)):
        # 현재 j에 대한 후보 점수
        candidate = mx + (values[j] - j)  
        if candidate > res:
            res = candidate
        
        # mx 갱신
        current = values[j] + j
        if current > mx:
            mx = current
    
    return res

# 테스트
print(maxScoreSightseeingPair([8,1,5,2,6]))  # 예시: 11

정리

점수 식을 $(\text{values}[i] + i) + (\text{values}[j] - j)$ 로 분리
$(\text{values}[i] + i)$ 의 최댓값을 순회하면서 갱신
매 시점에 $\text{values}[j] - j$ 와 더해 최대 점수를 갱신
한 번의 순회(O(n))로 쉽게 구할 수 있음

이 방법대로 구현하면 효율적(시간 복잡도 $O(n)$ ) 으로 문제를 해결할 수 있습니다.

어떻게 나눌 생각을 하지?.. 난 개똥벌레야.

수식 분해 아이디어 자체는 “values[i] + i와 values[j] - j로 따로 떼놓고 보자”는 관찰에서 시작하는데요, 처음엔 다들 쉽게 떠올리기 어려울 수 있어요.

어떻게 분해 아이디어를 떠올릴까?

1. 수식 재구성 습관 들이기

(values[i] + i) + (values[j] - j) 형태가 자연스럽게 나오려면, 문제에서 주어진 식 values[i] + values[j] + i - j를 보고, “indices(i와 j)의 영향과 values배열의 영향을 분리해볼 수 없을까?” 라는 질문을 먼저 던져봅니다.
즉, 원래 식에서 i와 -j를 굳이 붙여서 보면 (i - j)지만, 이를 (+i) + (-j)처럼 떼어내고 나머지인 values[i] + values[j]도 분리해서 함께 묶어보는 거죠.

2. 과거 비슷한 문제(패턴) 경험

사실 이런 문제 패턴은 [i ± j] 형태가 나올 때, 종종 **“배열 값 + 인덱스”**나 **“배열 값 - 인덱스”**를 따로 저장하는 방식을 취합니다.
예를 들어, “점수 식이 arr[i] + arr[j] + f(i,j)”와 같은 문제에서, f(i,j)가 i-j나 j-i 꼴이면, 자주 이런 분해 방법을 사용합니다.

3. 동적 계획법 / 누적값에서 착안

만약 i < j이면서 어떤 식을 최대로 하는 문제들은, 이전에 구해 둔 최적값(여기서는 $\max(\text{values}[i] + i)$ )을 “적절한 포맷”으로 캐싱해 두고, 현재 j에서 빠르게 써먹는 형태로 자주 접근합니다.

“처음 보면 어렵다”는 게 당연!

대부분 코딩테스트나 알고리즘 경험이 쌓이다 보면 “어, 인덱스 차이나 합이 있는 문제는 일단 분리해서 생각해볼까?” 하는 식으로 습관이 자리잡히는데, 처음에는 이 과정을 바로 떠올리기 쉽지 않아요.
문제를 많이 풀고, 유사 유형을 몇 번 경험하면서 “아, 이런 식으로 분리하는 테크닉도 있구나”라는 걸 체화하게 됩니다.

요약하자면

문제 식에 i와 -j 형태가 섞여 있으면 떼어서 생각하는 습관.
이전 인덱스(i)에서 최적값을 어떻게 “간단한 형태”로 캐싱할지 고민(여기서는 values[i] + i).
여러 문제에서 “배열 값 + 인덱스” / “배열 값 - 인덱스”로 분리하는 아이디어가 자주 쓰인다는 점 익히기.

결론적으로, 이런 문제는 익숙해지면 자연스럽게 수식을 분리해 보는 습관이 생깁니다. 처음엔 막막해도, 비슷한 유형을 계속 풀어보면 “아, 또 ‘values + 인덱스’로 나눌 수 있는 문제구나!” 하고 반사적으로 떠오르게 될 거예요.

그러니 지금처럼 “어떻게 생각해내지?” 라고 생각하는 건 너무나 정상적인 거고, 자책할 필요 전혀 없습니다. 조금씩 패턴을 접하고 경험을 쌓다 보면, 이런 아이디어가 더 빨리 스쳐 지나가게 될 겁니다. 화이팅입니다!

[!TIP] 다들 처음에는 비슷하게 막막하고 실수도 자주 해요. 그러다 보면 어느 순간, 아차 싶을 때가 오고 문제 풀이 아이디어가 눈에 들어오기도 해요.
너무 자책하기보다는 “아, 이번엔 이렇게 문제를 풀 수 있구나!” 하고 받아들인 뒤 넘어가면 됩니다.
분명 다음번엔 훨씬 더 빠르게 실마리를 잡을 수 있을 거예요. 화이팅입니다!

Solution

Approach 1: Dynamic Programming

0ms, 47.35MB
Complexity
- Let $n$ be the length of the array.
- Time Complexity: $O(n)$
- Space Complexity: $O(n)$

class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& values) {
        int n = values.size();
        // Initialize an array to store the maximum left scores up to each
        // index.
        vector<int> maxLeftScore(n);
        // The left score at the first index is just the value of the first
        // element.
        maxLeftScore[0] = values[0];

        int maxScore = 0;

        for (int i = 1; i < n; i++) {
            int currentRightScore = values[i] - i;
            // Update the maximum score by combining the best left score so far
            // with the current right score.
            maxScore = max(maxScore, maxLeftScore[i - 1] + currentRightScore);

            int currentLeftScore = values[i] + i;
            // Update the maximum left score up to the current index.
            maxLeftScore[i] = max(maxLeftScore[i - 1], currentLeftScore);
        }

        return maxScore;
    }
};

GPT

이 코드는 배열 values에서 두 위치의 점수를 계산하여 최적의 Sightseeing Pair를 찾는 문제를 해결합니다. 점수는 다음과 같이 계산됩니다:

$\text{Score}(i, j) = \text{values}[i] + \text{values}[j] + i - j$

여기서 $i < j$ 입니다.

문제 분석

주어진 문제에서 점수는 두 요소의 값과 그들 간의 거리(인덱스 차이)를 기반으로 계산됩니다.
이를 다음과 같이 변환할 수 있습니다:

$\text{Score}(i, j) = (\text{values}[i] + i) + (\text{values}[j] - j)$

이렇게 변환하면:

$(\text{values}[i] + i)$ 는 $i$ 의 왼쪽 점수(left score) 입니다.
$(\text{values}[j] - j)$ 는 $j$ 의 오른쪽 점수(right score) 입니다.

목표는 왼쪽 점수 + 오른쪽 점수의 최대값을 찾는 것입니다.

코드 설명

1. 배열 초기화

vector<int> maxLeftScore(n);
maxLeftScore[0] = values[0];

maxLeftScore[i]: 인덱스 $i$ 까지의 최대 왼쪽 점수를 저장합니다.
초기화:
- 첫 번째 위치의 왼쪽 점수는 $\text{values}[0] + 0 = \text{values}[0]$ .

2. 변수 초기화

int maxScore = 0;

maxScore: 현재까지의 최대 점수를 저장합니다.

3. 순회하여 최적 점수 계산

for (int i = 1; i < n; i++) {
    int currentRightScore = values[i] - i;
    maxScore = max(maxScore, maxLeftScore[i - 1] + currentRightScore);
    int currentLeftScore = values[i] + i;
    maxLeftScore[i] = max(maxLeftScore[i - 1], currentLeftScore);
}

a. 오른쪽 점수 계산

int currentRightScore = values[i] - i;

현재 인덱스 $i$ 의 오른쪽 점수는 $(\text{values}[i] - i)$ 로 계산됩니다.

b. 최적 점수 갱신

maxScore = max(maxScore, maxLeftScore[i - 1] + currentRightScore);

$i$ 이전까지의 최대 왼쪽 점수와 현재의 오른쪽 점수를 더한 값으로 maxScore를 갱신합니다.

c. 왼쪽 점수 갱신

int currentLeftScore = values[i] + i;
maxLeftScore[i] = max(maxLeftScore[i - 1], currentLeftScore);

현재 위치 $i$ 까지의 최대 왼쪽 점수를 갱신합니다.
이전까지의 최대 왼쪽 점수 maxLeftScore[i - 1]와 현재의 왼쪽 점수를 비교하여 갱신합니다.

4. 결과 반환

return maxScore;

계산된 최대 점수를 반환합니다.

시간 및 공간 복잡도

시간 복잡도

$O(n)$ : 한 번의 반복문으로 배열을 순회합니다.

공간 복잡도

$O(n)$ : maxLeftScore 배열에 $n$ 개의 공간을 사용합니다.

최적화 가능성

maxLeftScore 배열 대신 단일 변수로 현재까지의 최대 왼쪽 점수를 유지하면 공간 복잡도를 $O(1)$ 로 줄일 수 있습니다.

최적화된 코드

class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& values) {
        int maxLeftScore = values[0];  // 최대 왼쪽 점수
        int maxScore = 0;

        for (int i = 1; i < values.size(); i++) {
            // 오른쪽 점수를 계산하고 최대 점수 갱신
            maxScore = max(maxScore, maxLeftScore + values[i] - i);

            // 왼쪽 점수를 갱신
            maxLeftScore = max(maxLeftScore, values[i] + i);
        }

        return maxScore;
    }
};

최적화된 코드 설명

maxLeftScore 변수를 사용하여 이전까지의 최대 왼쪽 점수를 유지합니다.
각 반복에서:
- 현재 오른쪽 점수를 계산하고, 최대 점수를 갱신합니다.
- 새로운 왼쪽 점수를 갱신합니다.
공간 복잡도는 $O(1)$ , 시간 복잡도는 여전히 $O(n)$ 입니다.

예제

입력:

values = [8, 1, 5, 2, 6]

계산 과정:

초기화:
- maxLeftScore = 8, maxScore = 0.
순회:
- $i = 1$ $i = 1$ :
  - currentRightScore = values[1] - 1 = 0.
  - maxScore = max(0, 8 + 0) = 8.
  - maxLeftScore = max(8, 1 + 1) = 8.
- $i = 2$ $i = 2$ :
  - currentRightScore = values[2] - 2 = 3.
  - maxScore = max(8, 8 + 3) = 11.
  - maxLeftScore = max(8, 5 + 2) = 9.
- $i = 3$ $i = 3$ :
  - currentRightScore = values[3] - 3 = -1.
  - maxScore = max(11, 9 - 1) = 11.
  - maxLeftScore = max(9, 2 + 3) = 9.
- $i = 4$ $i = 4$ :
  - currentRightScore = values[4] - 4 = 2.
  - maxScore = max(11, 9 + 2) = 11.
  - maxLeftScore = max(9, 6 + 4) = 10.

출력:

$\text{maxScore} = 11$

Approach 2: Space-Optimized DP

0ms, 45.63MB
Complexity
- Let $n$ be the length of the array.
- Time Complexity: $O(n)$
- Space Complexity: $O(1)$

class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& values) {
        int n = values.size();

        // The left score is initially just the value of the first element.
        int maxLeftScore = values[0];

        int maxScore = 0;

        for (int i = 1; i < n; i++) {
            int currentRightScore = values[i] - i;
            // Update the maximum score by combining the best left score so far
            // with the current right score.
            maxScore = max(maxScore, maxLeftScore + currentRightScore);

            int currentLeftScore = values[i] + i;
            // Update the maximum left score up to the current index.
            maxLeftScore = max(maxLeftScore, currentLeftScore);
        }

        return maxScore;
    }
};

GPT

이 코드는 배열 values에서 두 인덱스 $i$ 와 $j$ ( $i < j$ )에 대해 다음 점수 공식을 최대화하는 문제를 해결합니다:

$\text{Score}(i, j) = \text{values}[i] + \text{values}[j] + i - j$

이 문제는 효율적으로 해결되며, 아래에서 단계별로 분석합니다.

문제 분해

공식을 다음과 같이 변환합니다:

$\text{Score}(i, j) = (\text{values}[i] + i) + (\text{values}[j] - j)$

왼쪽 점수: $\text{values}[i] + i$
- $i$ 에 의존하는 점수로, 이전 인덱스들에서 최대값을 추적합니다.
오른쪽 점수: $\text{values}[j] - j$
- $j$ 에 의존하는 점수로, 현재 인덱스에서 계산합니다.

코드 설명

1. 변수 초기화

int maxLeftScore = values[0];
int maxScore = 0;

maxLeftScore: 현재까지의 최대 왼쪽 점수 $(\text{values}[i] + i)$ $(values [i] + i)$ 를 저장합니다.
- 초기값은 $\text{values}[0] + 0 = \text{values}[0]$ .
maxScore: 현재까지 계산된 최대 점수를 저장합니다.

2. 배열 순회

for (int i = 1; i < n; i++) {
    int currentRightScore = values[i] - i;
    maxScore = max(maxScore, maxLeftScore + currentRightScore);

    int currentLeftScore = values[i] + i;
    maxLeftScore = max(maxLeftScore, currentLeftScore);
}

인덱스 $i = 1$ 부터 $n-1$ 까지 순회하며 점수를 계산합니다.

a. 오른쪽 점수 계산

int currentRightScore = values[i] - i;

현재 인덱스 $i$ 의 오른쪽 점수를 계산합니다: $\text{values}[j] - j$ .

b. 최대 점수 갱신

maxScore = max(maxScore, maxLeftScore + currentRightScore);

현재 오른쪽 점수와 이전까지의 최대 왼쪽 점수를 더해 최대 점수를 갱신합니다.

c. 왼쪽 점수 갱신

int currentLeftScore = values[i] + i;
maxLeftScore = max(maxLeftScore, currentLeftScore);

현재 인덱스 $i$ 의 왼쪽 점수를 계산하고, 최대값으로 갱신합니다.

3. 결과 반환

return maxScore;

계산된 최대 점수를 반환합니다.

시간 및 공간 복잡도

시간 복잡도

순회는 한 번만 수행되므로 $O(n)$ .

공간 복잡도

추가로 사용하는 변수는 상수 개수이므로 $O(1)$ .

작동 원리 예제

입력:

values = [8, 1, 5, 2, 6]

순회 과정:

초기화:
- maxLeftScore = 8, maxScore = 0.
$i = 1$ :
- currentRightScore = values[1] - 1 = 0.
- maxScore = max(0, 8 + 0) = 8.
- currentLeftScore = values[1] + 1 = 2.
- maxLeftScore = max(8, 2) = 8.
$i = 2$ :
- currentRightScore = values[2] - 2 = 3.
- maxScore = max(8, 8 + 3) = 11.
- currentLeftScore = values[2] + 2 = 7.
- maxLeftScore = max(8, 7) = 8.
$i = 3$ :
- currentRightScore = values[3] - 3 = -1.
- maxScore = max(11, 8 - 1) = 11.
- currentLeftScore = values[3] + 3 = 5.
- maxLeftScore = max(8, 5) = 8.
$i = 4$ :
- currentRightScore = values[4] - 4 = 2.
- maxScore = max(11, 8 + 2) = 11.
- currentLeftScore = values[4] + 4 = 10.
- maxLeftScore = max(8, 10) = 10.

출력:

maxScore = 11