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

안녕하세요

1231인 경우 말씀하신대로 첫번째 1에 대한 카운트를 제거하고 범위를 한 칸 앞으로 전진시키는 구조기 때문에 쉽게 이해가 갔습니다. 1 12 123을 집합A로, 나머지 경우의 수를 집합B로 하여 최종적으로 A+B로 전체 경우의 수를 구하는 구조이지요.

저 또한 강의를 보기 전 문제를 풀면서 이러한 논리로 접근하였으며, 강의에서 설명하신 논리 자체(중복되는 수가 포함되는 경우의 수(집합A)를 제거하고 나머지 경우의 수(집합B)를 더하는 구조)는 이해하였습니다.

이러한 논리를 코드로 작성하는 부분에서 이해가 잘 가지 않습니다.

먼저 강의 3분~5분의 1231의 예시 설명을 저는

• 얘(1)는 못 쓴다 -> 중복되니깐

• 1을 삭제하고 s를 당긴다 -> 중복되는 1을 제거한다

• 이 구간(갈색 구간)이 완성된다 -> e-s를 통해 중복되는 수인 1이 포함되는 경우의 수를 제외 && s를 당겨 "1을" 제외시키고 "2부터 시작되는 구간"을 만든다

라고 이해하였습니다.

이후 중복되는 수 2를 만나 s가 1증가되는 것은 단순히 중복되는 수의 인덱스가 0과 1로 1씩 증가하기 때문이라고 생각했습니다.

따라서 s의 값은 중복되는 수의 인덱스에 맞춰 변화한다고 생각했습니다.

따로 문제를 풀어보면서도

위의 사진처럼 단순히 s를 1 증가시킨다면 우측에서 볼 수 있듯 중복되는 수인 3이 포함되게됩니다. 실질적으로 s를 1만 증가시켜도 되지만 시각적으로는 분명 중복되는 수가 포함된채로 구간을 탐색하고 있는 것이지요.

마지막의 5가 없이 수열이 12343이라고 한다면 마지막 등차수열의 합 계산을 할 때

s가 1일 때는 마치 중복되는 수인 3을 포함하는 등차수열의 합처럼 보입니다.

물론 s를 1씩 증가시키는 강의의 코드(아래의 사진)를 통해 정답이 나오기 때문에 이것이 단순히 도식화시키면서 발생하는 오류일 뿐인 것 같습니다.

정리를 하자면

• 강의에서 설명해주신 문제 해결을 위한 논리구조는 이해가 갑니다.(중복되는 수를 포함하는 경우의 수 따로 빼서 더하다 마지막에 n(n+1)/2하기)

• 수강자가 이해하기 쉽도록 1231의 예시를 들어주신 것이지만(수가 복잡했으면 집합A와 집합B를 더해서 경우의 수 총합을 구하는 것을 설명하시는 것도, 수강자가 이해하기도 어려웠을 것입니다) 강의의 3-5분의 그림 설명을 통해 중복되는 수를 만났을 때 s를 1씩 증가시키는 것만으로 왜 중복되는 수를 포함하는 경우의 수들이 따로 빠지는지, 24~26행의 코드가 도출되는지 이해가 잘 가지 않습니다.

• 단순히 제가 이해력이 부족한 것일 수도 있지만 왜 's가 1만 증가해도 되는지'에 대한 설명이 보충된다면 좋을 것 같습니다.

감사합니다.

위의 사진처럼 단순히 s를 1 증가시킨다면 우측에서 볼 수 있듯 중복되는 수인 3이 포함되게됩니다. 실질적으로 s를 1만 증가시켜도 되지만 시각적으로는 분명 중복되는 수가 포함된채로 구간을 탐색하고 있는 것이지요.

>> 저런 상황은 발생되지 않습니다. 예를 들어 볼까요?

디버깅 코드는 다음과 같습니다.

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<cstdio>
using namespace std;
long long s, e, cnt[100001], n, a[100001];
long long ret;
int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        scanf("%lld", a + i);
    }
    while(e < n){
        if(!cnt[a[e]]){
            cnt[a[e]]++;
            e++;
        }else{
            ret += (e - s);
            cnt[a[s]]--;
            s++;
        }
        cout << s << " : " << e << '\n';
    }
    ret += (long long)(e - s) * (e - s + 1) / 2;
    printf("%lld\n", ret);
    return 0;
}
/*
6 1 2 3 4 3 5
0 : 1
0 : 2
0 : 3
0 : 4
1 : 4
2 : 4
3 : 4
3 : 5
3 : 6
15
*/

자,

1 2 3 4 3 5

에서

1 / 1 2 / 1 2 3 / 1 2 3 4

를 더하고

2 / 2 3 / 2 3 4 /

를 더하고

3 / 3 4

를 더하면서 가고 있죠?

중복된 3은 발생하지는 않습니다.

이러한 예제의 기본은 다음과 같아요.

예를 들어 이 수열

1 2 3 1

에서 첫번째 1을 포함하는 조합

1

1 2

1 2 3

에 대한 경우의 수를 모두 더하고

그리고 해당 포인터를 2로 옮기는 로직이 기본이 되서 움직이는 거에요.

흠.. 해당 강의 업데이트는 저도 검토해볼게요.

감사합니다.

안녕하세요

디버깅을 통한 친절하고 자세한 설명 감사합니다

정성껏 답변을 해주셨지만 무언가 제 궁금증이 해결되지 않아서 죄송한 맘이 드네요 ㅠㅠ 코드가 이해가 가지 않는 것이 아니라 코드로 나아가는 과정이 잘 이해가 가지 않아거 여쭈어본 것이었습니다

말씀해주신대로 코드상으로 s를 1씩 더하며 계산하면 중복되는 3은 발생하지 않습니다.

제가 s를 1씩 증가시켜도 실질적으로 중복되는 3이 발생하지 않지만 시각적으로는 중복되는 3이 발생하는 것처럼 보인다 여쭈었던 이유는 다음과 같습니다.

문제를 보면서 아무 것도 없이 답을 맞춰야 하는 입장에서는 아이디어 > 아이디어를 논리적으로 구체화 > 구체화된 논리를 코드로 구현 > 맞았나? 확인하는 과정을 거치게 됩니다

중복되는 수를 마주했을 때 s를 1만 증가시키면 된다는 것을 도출하기 위해서 문제를 푸는 입장에서 논리적 깨달음? 타당성을 확인해야 합니다 큰돌님께서도 그렇기 때문에 왜 s가 1만 증가해도 되는가에 대해 강의에서 긴 시간을 할애해주셨습니다

1231나 12312 같은 예시의 경우 도식화하여 논리를 검증하는 과정에서 s를 1만 증가시켜도 시각적으로(강의에서 s와 e를 증가시키며 선을 그어가며 도식화시켜주시던 부분) 중복되는 1이나 중복되는 2가 발생하지 않으니 s를 1만 증가시키도록 코드를 구현해도 되는 것 같습니다

하지만 앞서 말씀드린대로 문제를 처음 받고 내 논리가 맞나 이것저것 검증해보는 입장에서는 12343을 케이스로 도식화해서 그리는 경우 3이 s를 1만 증가시켜도 연산상으로는 아니지만 시각적으로 ‘중복되는 것처럼’보이니 ’이게 맞나?, s를 1만 증가시키는 것이 맞나?’ 싶어집니다

실질적 경우의 수들을 계산해보는 것이 아니라 도식화된 모습으로 볼 때는 앞선 3이 포함되는 경우 4개를 제외하려면 이 문제가 연속되는 수를 보는 문제기 때문에 경우의 수를 계산하는 범위에서 앞선 3 이전의 수들도 빠져야하는 것처럼 보이기 때문입니다

결과적으로 제 입장에서 도식을 보고 코드를 보고 다시 도식을 보면 이해가 가지만 강의 상 도식화를 통한 논리 검증에서 중복되는 수를 만난다면 s를 1 증가시키면 된다고 확인 후 코드를 짜는 과정이 이해가 가지 않으면서 s를 1증가시킨다는 결과에 맞춰 검증하는 것 같았습니다

감사합니다

안녕하세요

마음에 걸리는 부분을 계속 고민해보다 추가 질문 남깁니다

도식화는 결국 그림을 통해 자연스럽게 규칙을 발견하기 위해 쓰는 것입니다 이를 통해 논리>코드로 자연스럽게 전환이 이루어진다고 생각했습니다 그동안 이러한 방식으로 자연스럽게 문제가 풀렸기 때문입니다 안 풀리면 제가 구현을 제대로 못하여 막히던 것이었습니다

하지만 제가 이해가 안 간다고 하는 부분을 곰곰히 생각해본 결과 12343같은 케이스에서는 도식을 통해 중복되는 수를 만나면 s를 1추가하면 되겠다는 것이 즉각적이고 자연스럽게 도출되지 않습니다 경우의 수 제외를 위해 s를 1추가하면 된다는 규칙은 별도의 사고를 통해 고민해봐야하는 것이지요

원래도 문제를 풀 때 도식화하면서 논리를 검토할 때 한 번 더 생각해봐야하는 케이스들이 있었는데 제가 그동안 사용해왔던 케이스들이 한정적이라 위의 사례처럼 문제에 마주치는 것이 없던 것인지, 아니면 이 문제가 그동안 단순히 풀어오던 유형과 다르며 앞으로는 이런 식으로 단순히 도식화만으로 코드가 바로 도출되지 않는 문제가 있을 수도 있으며 이에 익숙해져야 하는 것인지 궁금합니다

후자라면 더 고민할 것이 아니라 제가 익숙해져야하는 문제이기 때문입니다

감사합니다

좋은 고민을 하셨군요. namk님 ㅎㅎ

투포인터는 뭘까요?

투포인터란 2개의 포인터를 기반으로 주어진 배열을 탐색하는 알고리즘입니다.

이 문제는 s, e를 기반으로 어떠한 집합이 "중복되지 않게 만들고" 해당 경우의 수를 찾는 문제였습니다.

그렇기 때문에 아 이문제는 투포인터를 활용할 수 있지 않을까? 라고 생각하는게 1번째입니다.

자, 그러면 어떻게 투포인터를 활용해야 할까? 여러가지 예제를 기반으로 생각해봅니다. 먼저 1 2 3 4 5 와 같은 아주 간단한 예제는 등차수열의 합으로 풀립니다.

근데 1 2 3 1 2 이런 예제는 어떻게 해야할까? s, e를 정할 때 중복되지 않은 집합으로 만들고 중복되는 점이 나오면 해당 부분을 빼야 하는데.. 어케 빼는게 좋을까? 아 s부분을 ++하면서 하는게 좋지 않을까? 아님 e를 --하는게 좋을까? 이런식으로 고민하다가 나오는 것이 저의 코드가 되는 셈입니다.

도식화를 통해 한번에 풀리면 좋죠. 그러나 한번에 풀리지 않은 문제들도 정말 많습니다. 항상 몇가지의 예제를 생각하고 이를 문제의 입출력을 기반으로 이런 예제가 나왔을 때 어떠한 값이 나와야 하는지를 기반으로 어떤 코드를 작성해야 하는지를 수정하고 수정하면서 답을 찾아가면 됩니다.

감사합니다.

안녕하세요

초보자의 입장에서 자세히 설명해주셔서 정말 감사합니다!

큰 도움이 되었습니다 :)

감사합니다