8-I vector 범위 질문

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

8-I

작성

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.

안녕하세요. 선생님.
vector의 크기를 max_n으로 할당하셨는데, max_n + 1으로 해야하지 않나요?
그래야 tree[max_n]까지 계산할 수 있잖아요.
이상하다고 생각해서 비주얼 스튜디오로 실행했을 때는 바로 오류가 나는데, 백준은 그냥 통과하더라고요?
왜 그렇죠? Update()함수를 실행할땐 범위가 max_n을 초과할 수 있으니까 그렇다 해도, right 값을 구할때 사용하는 Sum은 max_n부터 계산하니까 무조건 오류가 날 거라고 생각했는데 말이죠.

c++코딩-테스트

답변 2

큰돌

지식공유자

안녕하세요 원진님 ㅎㅎ

음... 해설을 보시면 max_n은 이미 넉넉히 1025를 주고 있습니다. ㅎㅎ

#include<cstdio>
#define max_n 1025

이원진

질문자

#include <bits/stdc++.h>
using namespace std; 
#define max_n 200004
#define ll long long
const ll mod = 1e9 + 7; 
int n, value;  
ll ret = 1, _prev; 
vector<ll> tree_cnt(max_n, 0), tree_sum(max_n, 0); 
// 이렇게 하면 tree[0] ~ tree[max_n - 1]까지 접근 가능하지만
ll _sum(vector<ll> &tree, int value){ 
    ll _ret = 0; 
    int i = value; // value == max_n이라면 tree[max_n]부터 계산하기 때문에, tree[max_n]에 무조건 접근하게 됩니다.
    while(i){
        _ret += tree[i];
        i -= (i & -i); 
    }
    return _ret;  
}
ll sum(vector<ll> &tree, int s, int e){
    if(s > e) return 0; 
    return (_sum(tree, e) - _sum(tree, s - 1)); //e = max_n
}

void update(vector<ll> &tree, int x, ll value){
    int i = x; 
    while(i <= max_n){ //이 부분에서 tree[max_n]까지 접근할 수 있습니다. tree의 크기는 max_n이고 tree[max_n-1]까지 접근가능하니까요. 
//따라서 vector<ll> tree(max_n + 1, 0)으로 해야하지 않냐는 겁니다.
        tree[i] += value; 
        i += (i & -i);  
    } 
    return;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);  
    cin >> n;  
    for(int i = 1; i <= n; i++){
        cin >> value; value++;   
        if(i != 1){
            ll left = value * sum(tree_cnt, 1, value - 1) - sum(tree_sum, 1, value - 1);
            ll right = sum(tree_sum, value + 1, max_n) - value * sum(tree_cnt, value + 1, max_n); 
            ret *= (left + right) % mod; 
            ret %= mod; 
        }   
        update(tree_cnt, value, 1);
        update(tree_sum, value, value);
    } 
    cout << ret << "\n";
}

max_n이 충분히 큰 건 알고 있습니다. 좌표 값의 범위가 0 ~ 200000이니까요.

그런데 제가 말씀 드린건 vector<ll> tree(max_n); 부분입니다.

이렇게 하면 tree[0] 부터 tree[max_n - 1]까지 접근 가능하지만, Update()에서 tree[max_n]까지 접근할 수 있고 ll right의 sum(tree_sum, value + 1, max_n)에서 무조건 tree[max_n]까지 접근하지 않나요? sum()은 start부터 end까지의 합이고 _sum()은 end부터 계산하니까 tree[max_n]은 무조건적으로 접근하게 되는거죠.
제 생각은 이래서 이상하다고 느꼇고 실제로 비쥬얼 스튜디오는 해당 부분에서 오류가 나왔습니다. 그런데 백준에서는 통과를 하더라고요? 왜 그런지 해당 부분이 궁금합니다.

큰돌

지식공유자

아 제가 문제를 잘못봤네요..

네 원진님 맞습니다.

void update(vector<ll> &tree, int x, ll value){
    int i = x; 
    while(i < max_n){

이렇게 수정되어야 합니다.

해당 부분은 오늘내로 강의 내 반영하도록 하겠습니다.

제 생각은 이래서 이상하다고 느꼇고 실제로 비쥬얼 스튜디오는 해당 부분에서 오류가 나왔습니다. 그런데 백준에서는 통과를 하더라고요? 왜 그런지 해당 부분이 궁금합니다.

-> 백준 문제 내 private TC가 부족해서 -> max_n까지 갔을 때 ub가 발생해야 하는데 그부분이 발생하지 않아 생기는 부분인 것 같습니다.

제 틀린 부분을 찾아주셔서 감사합니다.

인프런 AI 인턴

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

이원진님께서 질문하신 vector의 크기와 관련해서 유사한 상황을 다룬 기존의 질문과 답변을 제공해 드립니다. 이와 관련된 일반적인 내용은 배열이나 벡터의 크기를 설정할 때, 종종 크기보다 하나 더 크게 설정하는 습관이 있습니다. 이는 인덱스 범위 초과 문제를 사전에 방지하기 위한 방법입니다. Visual Studio와 백준에서의 차이는 컴파일러나 환경의 차이로 설명될 수 있습니다. Visual Studio에서는 보다 엄격하게 인덱스 검사를 할 수 있어서 오류가 발생할 수 있습니다.

관련하여 참고할 만한 질문과 답변은 다음과 같습니다:

8-H 문제 질문
- 이 질문에서는 배열의 인덱스 범위에 대한 문제를 다루고 있습니다. 강사님이 설명하신 바에 따르면, 배열의 인덱스 범위를 설정할 때 원시적인 C/C++ 배열 구조의 특성상 경계 확인이 이루어지지 않기 때문에 에러가 발생하지 않을 수 있음을 설명하고 있습니다.
8-H maxN 설정
- 여기도 유사한 범위 설정에 대한 설명이 나옵니다. 특히 max_n과 같은 상수를 설정할 때 문제가 되는 경우와 그렇지 않은 경우를 상세히 설명하고 있습니다.

이렇게 유사한 질문들을 통해 이해를 돕고자 합니다. 컴파일러 및 환경에 따라 결과가 달라질 수 있음을 항상 염두에 두시고, 배열의 크기를 설정할 때는 보수적으로 설정하는 것이 좋습니다.

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

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

8-I vector 범위 질문