안녕하세요. 세그 트리 공부중에 있는데 채점돌릴때 메모리랑 시간을 은근 잡아서

단축할 수 있는지 궁금해서 질문 올립니다.

코드 한번만 봐주시고 조언 부탁드리겠습니다~!

메모리 41048, 시간 136 으로 나왔습니다.

clrmt   11달 전

"맞은 사람" 목록에서 상위권에 있는 코드들을 읽는게 좋을 것 같네요.

여기서 더 시간을 줄이는 것은 크게 의미가 없지만 fread를 이용한 입력 가속과 비재귀 세그트리를 이용하는 방법이 있겠네요.

메모리를 더 줄이려면 tree 배열의 크기를 1000001 * 4 대신에 1048577 * 2를 잡는 방법이 있겠습니다.

답변 감사드립니다! 상위 목록 코드 보고 이해해보고 다시 짜보도록 해야겠습니다. 입력 가속이랑 비재귀 세그트리도 검색해서 찾아보도록하겠습니다 키워드 알려주셔서 너무 감사합니다.

아 그리고 배열 크기를 1048577 * 2 로 하는 이유에 대해서 더 자세한 설명 가능할까요?ㅠㅠ

clrmt   11달 전

가장 가까운 2^n꼴의 메모리의 2배만큼 필요하기 때문이죠. n + n/2 + n/4 + n/8 + ... 은 2n이니까요.

4배를 잡는 것은 가장 가까운 2^n를 모를 때 사용할 수 있는 방법입니다.

친절한 답변 정말 감사드립니다 clrmt님!

댓글을 작성하려면 로그인해야 합니다.