[알고스팟] 삽입정렬 문제 관련 문의 chochogogo 안녕하세요? 알고스팟 책을 보면서 공부하는 중 여쭙고 싶은 것이 있어 글 남기게 되었습니다. 질문이 문제 풀이 관련 스포일러 성이 있으므로 아래에 기제하도록 하겠습니다. 구간합 구하기 에서는 tree.sum(pos) : A[1] ~ A[pos]의 총 합 tree.add(pos, val) : A[pos]와 관계된 tree[] 값에 +val 해줌(갱신) 로 이해했는데 삽입 정렬 시간 측정 코드에서 ret += tree.sum(999999) - tree.sum(A[i]); tree.add(A[i], 1); 의 의미가 이해가지 않아서요.... 위의 코드의 의미가 무엇인지 여쭙니다. 8년 전
1개의 댓글이 있습니다. JongMan tree.sum(999999) - tree.sum(A[i])는 지금까지 본 숫자 중에 A[i]+1 ~ 999999 범위 내에 있는 숫자들의 수를 계산합니다. 다시 말해 A[i] 보다 큰 숫자들의 수를 찾죠. 삽입 정렬에서는 자기 왼쪽에 자신보다 큰 수가 있을 경우 swap이 일어나니까, 지금까지 나온 수 중 A[i] 보다 큰 숫자들의 수를 세면 swap 의 수를 셀 수 있습니다. 8년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
chochogogo
안녕하세요?
알고스팟 책을 보면서 공부하는 중 여쭙고 싶은 것이 있어 글 남기게 되었습니다.
질문이 문제 풀이 관련 스포일러 성이 있으므로 아래에 기제하도록 하겠습니다.
구간합 구하기 에서는
tree.sum(pos) : A[1] ~ A[pos]의 총 합
tree.add(pos, val) : A[pos]와 관계된 tree[] 값에 +val 해줌(갱신)
로 이해했는데
삽입 정렬 시간 측정 코드에서
ret += tree.sum(999999) - tree.sum(A[i]);
tree.add(A[i], 1);
의 의미가 이해가지 않아서요....
위의 코드의 의미가 무엇인지 여쭙니다.
8년 전