[8-J] 3635: 영화 수집 질문

안녕하세요 ㅎㅎ

후... 정말 오래 찾았습니다.

솔직히 모든 로직, 변수명 등 다 좋다고 생각하고 맞다고 생각하는데 이게 왜 틀리지?

하면서 디버깅을 오랫동안 해봤는데요.

#include <bits/stdc++.h>
using namespace std; 
int t, n, m, tree[200004], tmp;
map<int,int> mp; 
void update(int idx, int value)
{
    while(idx <= 200004){
        tree[idx] += value;
        idx += (idx & -idx);
    }
    return;
}
int sum(int idx)
{
    int ans = 0;
    while(idx > 0)
    {
        ans += tree[idx];
        idx -= (idx & -idx);
    }
    return ans;
}
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> t;
    while(t--){
        cin >> n >> m;
        memset(tree, 0, sizeof(tree));
        mp.clear();
        int update_idx = 100001;
        for(int i = 1; i <= n; i++)
		{
            update(i + update_idx, 1);
            mp[i] = i + update_idx;
        }
        for(int i=0; i<m; i++)
        {
            cin >> tmp;
            int idx = mp[tmp];
            cout << sum(idx) - 1 << " ";
            update(idx, -1);
            update(--update_idx, 1);
            mp[tmp] = update_idx;
        }
        cout << "\n";
    } 
}

앞의 코드처럼 하시면 맞습니다.

그러나.

#include <bits/stdc++.h>
using namespace std; 
int t, n, m, tmp, tree[200004];

이렇게 하시면 틀립니다.

즉, tmp를 앞서 선언하면 틀리다고 뜹니다. tmp 순서를 바꾸면 맞습니다.

일단 이거 자체가... 정말 희한하거든요.

C++에서 변수를 선언하는 순서는 해당 변수들이 메모리에서 차지하는 위치에 영향을 미칠 수 있습니다.(전역변수 등) 근데 tmp는 함수 내에서 임시적으로 값을 저장하는 용도로 사용되며, 그것이 선언된 순서는 중요하지 않습니다...

근데 저것만 바꾸면 맞았다고 뜹니다.

해당부분은 일단은 제가 백준에다가 남긴 상태입니다.

https://www.acmicpc.net/board/view/138554

제 지인 중에서도 알고리즘 잘하는 친구들이 있고.. 물어봤는데 다 모른다고 해서...

일단은 최선을 다해 찾아보고 답변이 나오면 다시 답변 드리겠습니다.

원인과 결과가 명확하게 답변을 드리고 싶었는데...

부족한 답변 죄송합니다.

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

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

감사합니다.

강사 큰돌 올림.

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

큰돌님의 ‘10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트’ 강의 중 ‘8-J 팬윅트리’ 강의와 관련하여 질문을 주셨군요.

질문 주신 ‘3635: 영화 수집’ 문제는 팬윅트리(Fenwick Tree)를 이용한 좌표 이동 문제인 것 같습니다. 백준에서 틀렸다는 결과가 나온다면, 보통 다음과 같은 이유일 수 있습니다:

1. 팬윅트리의 구현이 잘못되었을 수 있습니다.
   
2. 좌표 압축 혹은 업데이트 구조에서 오류가 있을 수 있습니다.
   
3. 잘못된 인덱싱으로 인해 벗어난 범위를 참조하는 경우도 있을 수 있습니다.
   

직접적인 코드 리뷰는 인프런 플랫폼의 지원 범위에 포함되지 않으므로, 해당 강의의 Q&A나 다른 학습자들과의 토론을 통해 도움을 얻을 수도 있습니다.

코드의 문제점을 찾지 못하신 경우, 질문하신 걸음마다의 팬윅트리 상태와 연산의 결과를 출력해보시거나, 작은 입력에 대한 사전 계산과 출력 결과를 비교해보는 디버깅 방식을 추천드립니다.

또한, 강의 내용을 한 번 더 복습하시면서 이해하지 못한 부분이 있는지, 예제와 최대한 비슷한 조건으로 테스트했는지 확인해보시기 바랍니다.

감사합니다.