영화수집 문제) 카운팅트리에서 궁금한게 생겼습니다.

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

8주차 개념 #1. 펜윅트리(Fenwick Tree)

작성

183

수정됨

인덱스를 음수로 사용할 수 없으니까 처음의 값들을

m최대값 10만이니 10만1 이상의 값에 값을 할당하셨는데.

그런데 10만2부터 사용하시고 10만1은 사용하시지 않으셨더라구요. 그래서 이해하는 과정에서 중요한건가 싶어서 10만도 해보고 10만1부터도 해보았습니다.

예로

update_idx = 100000

Update(update_idx , 1);

mp[temp] = update_idx--;

이렇게 수정해보았습니다.

범위에 딱 맞으니까 10만개까지 딱 정보가 들어올 수 있게되는데

sum에서 잠시 생각해보니 tree[0] 인덱스에 10만번째 정보가 들어올 것이라고 생각이 들어서요

while(i>=0) 으로 바꾸어보았는데 .. (ㅋㅋ 왜 [1] 부터 하시라는지 알았습니다..) 당연히 무한루프를 돌았고

다시 while(i>0)으로 수정했는데 정답이 떴습니다.

사실 오답이어야 하는게 아닌가 싶어 질문드립니다.

c++코딩-테스트

답변 2

큰돌

지식공유자

안녕하세요 mch님 ㅎㅎ

while(i>=0) 으로 바꾸어보았는데

int sum(int idx){
    int ret = 0; 
    while(idx > 0){
        ret += tree[idx];

이부분은 tree를 기반 - 1부터시작하기 해야 하기 때문에 idx > 0으로 해야 합니다.

애초에 로직자체가 꼬여버리게 됩니다. 이진법 - 1, 2, 4 등을 기반으로 만들어진 펜윅트리기 때문이기 때문에 >= 0으로 해버리면 0을 참조해버리고 idx -= (idx & -idx); 이 부분 자체도 꼬여버리게 되서.. 애초에 0을 참조하지 않게 만들어야 합니다.

사실 오답이어야 하는게 아닌가 싶어 질문드립니다.

update_idx = 100000

Update(update_idx , 1);

mp[temp] = update_idx--;

넵 mch님 말씀이 맞습니다. ㅎㅎ

10만으로 하면 안됩니다.

저게 근데 정답이라고 뜬게 이상하네요. 제가 시도했을 때는 시간초과가 발생합니다.

http://boj.kr/744e91340d4a431093fc6620c59daa63

dist[a][b] = dist[a][b] ? min(dist[a][b],c) : c;

이 부분 dist[a][b] = min(dist[a][b], c); 이렇게 해도 괜찮지 않나요?
>> 이거는.. 플루이드 문제 - 해당 문제 : 질문 에서 맞는코드, 틀린코드 두개로 다시 질문부탁드립니다.

벨만 포드에서
왜 (정점-1)번 순회를 해야하는지 잘 이해가 가지 않아서.. 사이클..

벨만포드 사이클 찾는 방식을 보시면..

알고리즘의 작동 방식

초기화: 시작 정점을 제외한 모든 정점의 거리 값을 무한대로 설정
검사 -> 완화 : 모든 간선에 대해, 간선을 통해 다른 정점으로 이동하는 것이 더 짧은 경로를 제공하는지 검사하고, 필요한 경우 거리 값을 갱신합니다.
순회 횟수: 이 과정을 각 정점마다 반복합니다 근데 이때 마지막 정점에까지 왔는데 v - 1 이상황에서도 완화할 부분이 있다면 사이클이 있는 것은 자명하기 때문입니다 혹시 모든 정점을 탐색하고 마지막 정점이 남았다 = v - 1 이므로..

어떤 최단 경로도 한 정점을 두 번 이상 지나지 않습니다(사이클이 없는 경우).

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

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

감사합니다.

강사 큰돌 올림.