인프런 커뮤니티 질문&답변

아 그렇군요...

범위도 a.size()로 하면 너무 커져서 큰돌님께서 기저 조건을 p로 잡으신거였군요 이해 한 거 같아요 감사합니다!!

안녕하세요 자르트님 ㅎㅎ

low, high를 처음에 두신 이유가 있으신지 궁금합니다!

->

음.. 모든 경우의 수를 기반으로 다 체크할 수 있을까? 하면서 코드를 짜다보면 두 포인터를 처음에 두게 됩니다.

이 문제는 처음에 {0, 0} 부터시작해 {0, 1} {0, 2} 까지의 연속적인 배열의 합을 기반으로 경우의 수를 찾아야 하죠.

근데 처음에 전체범위부터 시작해서 줄여버리면 모든 경우의 수를 체크를 못하게 됩니다.

예를 들어 {0, 0} 과 {5, 5} 이거 두개는 체크 못하는 코드인 것 같습니다.

ex) 0에서 5까지의 범위라고 하면

그리고

    while (l != r) {
        ll sum = 0;
        for (ll i = l; i < r; i++)
            sum += a[i];

이거 자체가 시간복잡도가 클 것 같습니다.

감사합니다.

안녕하세요, 인프런 AI 인턴입니다.

투 포인터 알고리즘을 사용할 때, 일반적으로 low와 high 포인터를 배열의 시작과 끝에 놓습니다. 이는 보통 특정 조건을 만족하고, 해당 조건을 빠르게 찾기 위해 슬라이딩 윈도우 기법을 사용하는데 최적화된 시작점입니다.

질문하신 코드에서는 low(여기서는 l)와 high(여기서는 r)가 모두 배열의 요소들 사이를 이동하게 되는데, 문제의 접근 방식과 가장 큰 차이점은 각 단계에서 전체 범위를 다시 합산한다는 점입니다. 이는 매번 sum을 계산하는 데 O(n)의 시간이 걸리므로, 시간 초과가 발생할 수 있습니다.

다음과 같이 low와 high를 적절한 초기값으로 설정하고, 슬라이딩 윈도우를 적용하면 시간 복잡도가 개선될 수 있습니다:

1. 초기 위치 설정:

   ll l = 0, r = 0;
   ll sum = 0;
   

2. 목표하는 값보다 합이 작다면 high 포인터를 이동시킵니다. 그 과정에서 현재 위치의 값을 합산합니다.

3. 목표하는 값과 같다면, 결과를 업데이트한 뒤 low 포인터를 이동하여 슬라이딩 윈도우를 진행합니다.

4. 목표보다 크다면 low 포인터를 이동하여 현재의 합을 줄입니다.

아래는 코드 예시입니다:

ll n = /* 목표 값 */;
vector<ll> a = /* 데이터 */;
ll l = 0, r = 0, sum = 0, ret = 0;

while (r < a.size()) {
    if (sum < n) {
        sum += a[r];
        ++r;
    } else if (sum > n) {
        sum -= a[l];
        ++l;
    }
    if (sum == n) {
        ++ret;
        sum -= a[l];
        ++l;
    }
}

이 방법은 각각의 포인터 움직임에 대해 한번의 연산만 추가되고, 결과적으로 O(n)이 되기 때문에 시간 복잡도를 상당히 줄일 수 있습니다.

또한, 다음과 같은 유사한 질문의 링크를 참고하시면 도움이 될 수 있습니다:

• 5-G while(1)문 내부를 이렇게 하면 왜 안될까요?
  
  • 여기에서는 투포인터의 순서에 대한 설명과 코드의 로직에 대한 핵심 사항이 다뤄집니다.
    

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.