동적 배열

https://unsplash.com/photos/OZfT7migxQM

알고리즘 문제를 풀다 제한된 메모리를 초과해서 문제를 틀린 적이 있다.

무엇이 문제인가 찾아봤더니 for문에서 append를 사용하면 시간이 더 걸릴 수 있다고 나왔다.

왜 그런지 알아보자

 

 

 

 

 

---

얻어갈 지식

• append() 사용 시 받는 불이익

 

 

 

 

 

동적 배열과 append()

 

동적 배열은 여유분의 메모리를 미리 할당받아 놓는 방식으로 만들어진다.

• 배열에 실제 데이터가 있는 크기를 size 그리고 여유 메모리를 포함한 할당받은 전체 메모리 크기를 capacity라고 한다.
• append()가 호출되면 size의 값을 1 키우고 그 위치에 새로운 값을 할당시키는 방식으로 돌아간다.
• 하지만 여유 메모리를 모두 사용하게 되면 하는 수 없이 아래와 같은 재할당 과정을 거쳐야 하는데, 이 재할당 과정이 빈번히 일어나면 일어날수록 시간이 오래 걸리게 된다.
  
  • 새 배열을 할당받음
  • 기존의 원소들을 모두 새 배열로 복사함
  • 포인터가 새 배열을 참조하도록 변경 
    
    
    

동적 배열의 size와 capacity

 

 

 

 

 

---

https://frhyme.github.io/datastructure/java_dynamic_array/

Java - Dynamic Array(동적배열)

 

https://novlog.tistory.com/70

[DataStructure] 동적 배열 (Dynamic Array)