배열 생성 시간복잡도1 자바에서 N개짜리 배열 생성은 O(N)이 걸린다. (C++, C 도 마찬가지) 혹시 C를 써봤다면, 자바에서는 배열 생성하면 모든 값이 초기화가 되어있는게 신기한 적이 있을 것이다. 배열을 만들어서 무언가 담고 싶을 때 C계열에서는 메모리 할당만 받고 끝나서 금방 끝나지만, 자바의 경우 배열을 만들고 초기화까지 해주는 아주 친-절한 언어이다. 그럼 단순히 int형 RxC 짜리 배열(int[][] arr = new int[R][C])을 만들 때 시간 복잡도가 어떻게 될까? 당연히 O(1)일 것 같지만, 자바에선 무려 O(RC)가 필요하다. 이하 10만x1만 짜리 배열 하나 만든건데 이것만 1초가 넘게 걸린다. 그럼 이하 코드를 보자. 알고리즘을 풀 때 bfs를 여러번 돌릴 수 있다. 이 때, 사실 하나의 방문체크로 가능하지만(예를들어 하나의 큰 배열에서 빈 칸들의 구역을 나눌 때) .. 2023. 3. 13. 이전 1 다음
