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

Question

인덱스를 음수로 사용할 수 없으니까 처음의 값들을 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)으로 수정했는데 정답이 떴습니다. 사실 오답이어야 하는게 아닌가 싶어 질문드립니다.

큰돌 · Answer

안녕하세요 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점은 제게 큰 힘이 됩니다. :) 감사합니다. 강사 큰돌 올림.

큰돌 · Answer

안녕하세요 mch님 ㅎㅎ 혹시 어떤 문제인가요?