injaesong   1년 전

자바로 일반적인 크루스칼 알고리즘으로 풀었습니다.

다만 2가지 정도 추가해서 시간복잡도를 더 개선시켜봤어요.

1. Union을 할 때마다 카운트해서 카운트가 n - 2면 break

2. 카운팅 배열을 통해 정렬 생략

2번은 사실 배열보단 해시맵을 사용했습니다.

시간복잡도가 개선은 됐습니다.

하지만 카운팅 배열을 사용하면 메모리를 더 많이 잡아먹을거라고 생각했는데, 오히려 메모리도 개선됐더라고요.

왜 그렇게 되는건지 잘 생각을 해봐도 감이 잘 안 잡혀서 질문 남겨봅니다.

도와주시면 감사하겠습니다.

첫번째가 카운팅 배열을 사용했을 때고, 두번째가 정렬 했을 때입니다.

preview

bupjae   1년 전

최대 크기의 데이터가 주어졌을 때, 생성되는 Edge 객체의 개수는 1000000개 입니다

제출번호 100087548 의 경우 Edge 객체 하나의 크기는 12 byte, 제출번호 100087594 의 경우 8 byte 입니다.

반면, 등장할 수 있는 길의 유지비의 "종류"는 1000 종류이기 때문에,

제출번호 100087594 는 제출번호 100087594 보다 ArrayList 객체 999개 와 HashMap 객체 1개를 더 생성합니다.

 .

생성되는 Edge 객체의 개수가 워낙 많다 보니까

Edge 객체의 메모리 감소가 ArrayList + HashMap 객체 추가 생성에 의한 메모리 증가보다 훨씬 큽니다.

.

ps) 사람마다 관점이 다를 수 있지만

제출번호 100087594 에서 사용한 기법을 "정렬을 생략했다" 라기 보다는 "카운팅 정렬 (Counting Sort)을 사용했다" 라고 봅니다.

이 문제로 경험하신 것 처럼 입력 데이터의 개수에 비해 정렬하려는 키의 종류가 좁을 때 유리한 정렬 방식입니다.

injaesong   1년 전

답변 감사드립니다.

말씀대로면 Edge에 실제로 사용하진 않더라도 int 필드 하나 추가해서 12byte로 맞춘다면 처음에 생각했던대로 메모리가 더 맞을까요?

bupjae   1년 전

Edge 객체의 크기를 똑같이 맞춘다면 처음 예측하신 대로 카운팅 기반의 메모리 소비량이 더 클 것으로 예상됩니다.

단, VM 언어는 그 특성상 VM 이 아닌 언어에 비해 메모리 사용량 예측이 좀 많이 어렵고, +1000개 객체 더 만드는 정도는 오차 범위 안에 묻힐 가능성도 존재합니다.

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