5-V 누적합 질문

Question

안녕하세요!!
누적합 공부하면서 좀 헷갈리는 부분과 예시코드랑 다른 부분이 있어서 이 두개에 대해서 질문하려고합니다.
http://boj.kr/88f78b9449fb462e99bbed15e9875b5f
이게 제가 작성한 코드인데요,

피자가원형이고, 예를 들어 7,2,2,2,1 이 있다고 치면 확장해서 7,2,2,2,1,7,2,2,2,1 이렇게 만드는 과정이 2*m 즉 2배 확장하는걸로 이해했는데요, (2*m)-1 만 확장해도 상관은 없는거죠? 선택할 수 잇는 시작점의 마지막 위치가 1이고 그 뒤로 넘어가 7을 선택하게되면 결국 맨 처음 선택했던 시작점과 동일해지기 때문에 이런것같은데, Chatgpt를 통해서 의견을 묻는데 반드시 2*M 의 구간확장이 필요하다해서 의미가 있나 싶어 질문드립니다.

또한 map에다가 누적합들을 더하는 과정이 예시 코드에서는
interval개를 선택할거고, start지점을 interval과 같게 설정하는 부분이 잘 이해가 안됩니다. 저는 i~j까지의 합을 size만큼 펼쳐가면서 더햇는데요, 예시 코드에서 start를 꼭 interval로하는 이유가 있나요? 물론 코드가 정상적으로 동작해서 같은 결과를 내는건 알겠는데, start = 1; start<= n 으로 하지 않는 이유가 궁금합니다.

큰돌 · Answer

안녕하세요 정현님 ㅎㅎ

7,2,2,2,1,7,2,2,2,1

->

네 맞습니다.

예시를 들어 보면은... 여기서 보면 저희가 해야할 부분이

7,2,2,2,1,7,2,2,2,1

이렇게 가다가...

7,2,2,2,1,7,2,2,2,1

여기까지의 범위를 확인하는 것이라

2m - 1까지만 확인하는게 맞습니다.

실제로 이부분은 제 코드내에도 다음처럼 break를 걸어 2m 부분의 확인을 막습니다.

            if(interval == n) break;

2번질문::

    for(int interval = 1; interval <= n; interval++){
        for(int start = interval; start <= n + interval - 1; start++){

이 코드와

    for(int i = 1; i<=size; i++){
        for(int j = i; j<=i + size -2; j++){

이 코드가 다른 부분을 말씀하시는거 맞을까요?

근데 저거 변수명 말고는 다른 부분은 -2까지인지 -1까지인지 말고는 없습니다.

        for(int start = interval; start <= n + interval - 1; start++){

이부분이 정현님은

        for(int start = interval; start <= n; start++)

이렇게 되어야 한다고 생각하시는것이죠?

자 전체코드를 잠깐 볼게요.

    for(int interval = 1; interval <= n; interval++){
        for(int start = interval; start <= n + interval - 1; start++){
            int sum = psum[start] - psum[start - interval];

여기서 중요한 부분은 바로 psum[start] - psum[start - interval]; 이부분이죠?

우리는 뭘 확인하고 싶은 걸까요?

바로 길이가 1부터 n까지인 모든 연속 구간의 합을 계산하는 것입니다. 여기서 interval은 구간의 길이입니다. 1 ~ n이어야 합니다.

그리고 그 다음 루프는 해당 길이에 맞춰서 -> 구간의 모든 경우의 수를 구해야 합니다.

예를 들어 구간의 길이가 3이라고 했을 때

1, 2, 3, 4, 5, 6

1, 2, 3, 4, 5, 6

1, 2, 3, 4, 5, 6

1, 2, 3, 4, 5, 6

이런 경우의 수를 뽑아야 하기 때문에 start는 interval(3)부터 시작합니다. 그리고 나서

...

결국 여기까지 뽑아야 하기 때문에 n 까지가 아니라 n + interval - 1까지 뽑아야 합니다.

1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 6

만약 n까지 뽑게 되면 그 이전의 경우의 수 까지밖에 못뽑게 되서 -> 모든 경우의 수를 생각하지 못하게 됩니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

인프런 AI 인턴 · Answer

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

이정현님께서 주신 질문은 누적합과 피자원형 문제에서의 구간 확장 방식에 관한 내용입니다. 질문의 핵심은 피자 원형 배열을 확장하는 과정과 예시 코드에서 사용된 start 변수의 설정 방식입니다.

원형 배열 확장:
- 원형 배열 확장은 연속된 요소를 선택하기 위해서 전체 배열을 다시 한번 이어붙이는 방식으로 진행됩니다. 예를 들어 7, 2, 2, 2, 1을 7, 2, 2, 2, 1, 7, 2, 2, 2, 1로 확장합니다.
- 이때 2배라고 하는 이유는, 구간이 도는 특성상 끝까지 가야만 시작점이 되는 경우를 포함하기 위함입니다. (2*m)-1로도 구현이 가능하지만, 안전하게 2*m으로 사용하여 구간 처리를 명료하게 하는 경우가 많습니다.
- ChatGPT의 의견은 프로그래머들이 안전하게 코드를 구성하도록 돕기 위한 일반적인 지침으로 이해하시면 됩니다.
Start 변수의 설정:
- 예시 코드에서 start를 interval로 설정한 이유는, 특정 길이만큼 확장한 배열을 다루기 위해 초기 위치를 조절한 것입니다.
- 배열의 구간을 설정할 때, 확장된 배열을 기준으로 부분합을 정하는 것이 보통 효율적 이므로 interval로 잡습니다. 이 방식은 중복 계산을 피하고, 알고리즘의 복잡도를 줄이려는 의도가 포함되어 있습니다.
- start = 1; start <= n 으로 설정하는 것도 가능하겠지만, 이렇게 하면 처리하는 방식에 차이가 생길 수 있습니다. 예시에서는 효율적인 계산을 위해 이와 같이 구성한 걸로 보입니다.

추가적으로 관련된 게시물들을 참조하셔서 더 풍부한 정보를 얻으시면 좋겠습니다. 도움이 될 만한 링크를 리스트로 드리겠습니다:

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

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

5-V 누적합 질문