h59168   1년 전

배열 형태가 필요할 때 저는 vector를 이용해서 입력을 받고 정렬을 하는데, 다른 분들의 풀이를 보다 보면 문제에서 요구하는 최대의 크기로 전역에 배열을 선언하고 풀이하는 경우가 왕왕 있더라고요.

(문제에서 N개(N <= 10000)의 수가 주어진다고 할 때 전역 변수로 int n[10000]; 선언해두는 것 등을 말한 겁니다)

이런 경우 vector로 선언하는 것보다 배열로 선언하는 것의 이점(속도 등)이 있어서 이렇게 풀이하는 것인가요? 아니면 그냥 개인의 코딩 스타일 차이인가요?

검색을 해 봐도 벡터는 배열과 비슷하다 동적 할당이 가능하다 정도만 나와서 이곳에 질문드려봅니다.

zenith82114   1년 전

전역 배열은 컴파일 시점에 해당 메모리가 예약되어 바이너리 파일에 포함되고, vector나 new/delete 등의 동적 할당은 실제로 실행을 하는 도중에 (런타임에) 운영체제에 syscall을 해서 메모리를 마련합니다.

이곳 BOJ를 포함한 대부분의 채점 사이트와 코딩 테스트에서 두는 시간제한은 컴파일 타임은 제외하고 런타임만 고려하기 때문에 배열을 쓰는 편이 약간의 시간 이득이 있으나, 알고리즘 문제에서 사용하는 길이는 커봐야 $10^6, 10^7$ 정도로 총 소요시간에 상당한 차이를 낳는 일은 드물기 때문에 취향에 따라 어느 것을 사용하셔도 무리가 없습니다.

단, 동적 할당을 사용한다면 할당과 해제를 불필요하게 반복하는 일만 피하도록 (특히, 1번의 실행에 여러 개의 테스트 케이스가 들어오는 경우) 주의하시면 됩니다.

h59168   1년 전

감사합니다!

1번의 실행에서 여러 개의 테스트 케이스를 처리해야 하는 경우 주의해야 한다는 것은, 각 테스트 케이스마다 vector 등을 새롭게 동적 할당하게 되면 이로 인해(할당 및 해제로 인해) 런타임이 늘어난다고 이해했는데 맞을까요?

zenith82114   1년 전

맞습니다.

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