인프런 커뮤니티 질문&답변
작성한 질문수
8주차 개념강의 영화수집 질문드립니다
작성
·
107
·
수정됨
0
안녕하세요
큰돌님 8주차 개념강의 영화수집 문제에 궁금한 점이 있어 질문드립니다!
큰돌님의 코드와 동일한 로직으로 코드를 작성했는데 자꾸만 오답으로 떠서 원인을 찾던중에 아래와 같은 원인을 발견했습니다.
제 코드
int t,n,m,temp;
int tree[200004];
map<int,int> mp;큰돌님 코드
int t, n, m, tree[200004], temp;
map<int, int> mp; 단지 전역변수(tree 배열) 선언 순서만 다른데, 오답으로 채점되었습니다. (큰돌님 코드에서 전역변수 순서만 바꿔도 오답으로 채점됩니다.)
전역변수 선언 순서는 로직에 영향을 받지 않는다고 알고있었는데, 영향이 가는걸까요?
제가 평소에도 전역변수를 선언할때, 배열은 배열끼리 분리해서 선언하는 습관이 있어서 이렇게 선언하였는데 이유가 궁금합니다!
+ 추가적으로 왜 update_idx가 100001 이어야하는지 잘 이해가 가지 않습니다..😥
update_idx가 100001이면 idx 100002부터 저장되는데,
i가 1부터 10만까지이니까 그 다음번 인덱스인 100001부터 저장하면 안되는건가요?
답변 1
0
안녕하세요 희수님 ㅎㅎ
오랜만입니다.
제가 평소에도 전역변수를 선언할때, 배열은 배열끼리 분리해서 선언하는 습관이 있어서 이렇게 선언하였는데 이유가 궁금합니다!
>> 이거는 좀 이상한것 같아요. 전역변수 탓은 아닌 것같고.. 그냥 제 코드가 좀 이상해서 UB가 뜨는 것 같습니다.
제가 해설 코드를 좀 변경했는데 이렇게 하면 희수님 코드도 정답으로 뜹니다.
이렇게 바꿔보시겠어요?
#include<bits/stdc++.h>
using namespace std;
int t, n, m, temp;
int tree[200004];
map<int, int> mp;
void update(int idx, int value){
while(idx < 200004){
tree[idx] += value;
idx += (idx & -idx);
}
}
...
아래 내용은 같음.해당 부분은 해설코드 또한 수정해서 올리도록 하겠습니다. <= 가 아니라 <이 맞는 코드입니다.
i가 1부터 10만까지이니까 그 다음번 인덱스인 100001부터 저장하면 안되는건가요?
>> 펜윅트리는 1부터 저장하게 됩니다. 1 ~ 10만이라면 -> 10만의 공간이 아니라 10만 + 1의 공간이 필요합니다. (0번째를 못쓰기 때문) 이 때문에 그 다음 번째인 10만 + 2의 공간부터 시작해야 하기 때문에 10만 + 2부터 저장해야 합니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
안녕하세요 ㅎㅎ 와 그림까지.. 대단하십니다.
0번 인덱스를 비우고 1번부터 10만까지의 인덱스에 채워넣으면 10만 +1 의 공간이 필요하다는것은 이해가 됐습니다!
>> 문제에서 주어지는게 10만 + 1의 공간이기 때문에 우리는 그 다음의 공간에서 차곡차곡 쌓아나가야 하기 때문에 10만 + 2의 공간부터시작하는게 맞습니다.
음..
1부터 2까지 표현한다면.. (1부터 시작해서)
0, 1, 2 이렇게 3개의 공간이 필요하죠?
그렇듯.
1부터 10만까지 표현한다면..
0, 1, ... 10만 + 1까지의 공간이 필요합니다.
그다음!! 공간인 10만 + 2부터 쌓아나가야 하는 셈입니다.
이해가 안되시면 또 질문주세요 ㅎㅎ
답변 감사드립니다!
0번 인덱스를 비우고 1번부터 10만까지의 인덱스에 채워넣으면 10만 +1 의 공간이 필요하다는것은 이해가 됐습니다!
제가 생각했던 구조인데, 0번 index를 비운 후, 1번 index~ 10만 index 까지 10만개를 로직을 위한 여유공간으로 할당한 후, 10만+1 index 부터 값을 할당해 나가면 될것 같은데, 왜 10만+2 인덱스부터 채워나가야 하는지 이해가 잘 되지 않습니다 ㅠㅠㅠ 제가 어떤 부분을 놓친걸까요?