안녕하세요 좋은 강의 감사드립니다! 강의 9:20 "우리는 Dynamic Array의 size를 미리 알고 있기 때문에" 문장에서 궁금증이 생겼습니다. 우리는 Dynamic Array의 size를 머리속에 기억 하고 있기 때문에 a.append(4) 를 했을때 O(1)인것을 알지만 컴퓨터의 경우 a.append(4)를 했을때 Dynamic Array의 size를 어떻게 알고 값을 저장할까요?? 따로 저장이 될까요? size를 아는 경우 배열 포인터(배열 변수)에 저장된 초기 주소값 + size*Byte(자료형에 따라 다름) 으로 바로 접근 가능 하여 O(1) 이라고 납득이 되지만 size를 모를 경우 마지막 데이터가 있는 주소값으로 바로 가려면 array 를 전부 훑어서 O(n)이 될 수 있지 않을까 궁금했습니다. a 라는 배열 포인터에 초기 주소값과 size 정보를 저장해놓는다. 배열 포인터가 아닌 다른곳에 정보를 저장한다. array를 전부 훑는건 O(1)이다. 1번, 2번, 3번 중에 어떤 걸까요?? 그리고 검색하다 size와 capacity 에 대한 내용을 봤는데 capacity가 Dynamic array에서 처음 선언할때 비어 있는 index를 포함한 크기 로 알고있습니다. 위 제가 판단한것에서 1번, 2번 일경우 size 뿐만 아니라 capacity 정보도 저장해놔야 할것 같은데 저장한다면 어디에 저장 하는 걸까요?? 저장을 안한다면(3번) 직접 빠르게 훑어보고 값을 추가 or 삭제 하는 걸까요?? 강의 후반부에 설명해 주시는 내용이라면 죄송합니다.. 항상 감사합니다!

안녕하세요, 인프런 AI 인턴입니다. s3490147님께서 질문해 주신 Dynamic Array의 size 와 capacity 에 대한 궁금증에 대한 답변을 드리겠습니다. Dynamic Array를 사용할 때, 컴퓨터는 배열의 크기( size )와 용량( capacity ) 정보를 저장하기 위해 별도의 메모리 공간을 활용합니다. 이는 배열을 효율적으로 관리하고, 필요한 경우 크기를 동적으로 조절할 수 있도록 돕습니다. 일반적으로 이러한 정보는 다음과 같은 방식으로 관리됩니다: 배열 포인터 또는 메타데이터 블록에 저장 : Dynamic Array는 실제 데이터와 함께 관련 메타데이터를 보유합니다. 이에 따라 size 와 capacity 정보가 배열의 메모리 첫 부분이나 별도의 메타데이터 블록에 저장되어 있습니다. 이는 배열 포인터에 객체 형태로 저장되기도 하며, 이러한 메타데이터 덕분에 size 와 capacity 를 빠르게 참조할 수 있습니다. size 와 capacity 를 유지하는 이유 : 새로운 요소를 추가해야 할 때, 현재의 size 와 capacity 정보를 통해 배열의 크기를 변경할지를 결정합니다. 이 과정은 효율적이며, size 정보가 즉시 접근 가능하기 때문에 요소를 배열에 추가하는 작업이 O(1) 시간 복잡도에서 이루어질 수 있습니다. size 와 capacity 변경의 예 : 예를 들어, 파이썬의 리스트는 내부적으로 배열을 사용하여 구현되어 있으며, 이때 capacity 는 보통 이진수 배수로 조절되면서 요소를 저장할 충분한 공간을 제공하고, 공간이 부족해지면 자동으로 더 큰 배열을 할당하여 데이터를 복사합니다. Dynamic Array 작동 원리에 대해 더 깊이 이해하고 싶으시다면, 다음의 유사한 질문과 답변들을 참고하시면 좋을 것 같습니다: 동적배열 8:23 제가 이해한게 맞는지 확인부탁드립니다. [동적배열 8: 16초] 저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

Dynamic Array 의 size 정보가 저장되는 곳 - 인프런

코딩테스트 [ ALL IN ONE ]

동적 배열 (Dynamic Array)

Dynamic Array 의 size 정보가 저장되는 곳

해결된 질문

2025. 01. 27. 03:39 작성

안녕하세요 좋은 강의 감사드립니다!

강의 9:20

"우리는 Dynamic Array의 size를 미리 알고 있기 때문에"

문장에서 궁금증이 생겼습니다.

우리는 Dynamic Array의 size를 머리속에 기억 하고 있기 때문에 a.append(4) 를 했을때 O(1)인것을 알지만

컴퓨터의 경우 a.append(4)를 했을때 Dynamic Array의 size를 어떻게 알고 값을 저장할까요?? 따로 저장이 될까요?

size를 아는 경우 배열 포인터(배열 변수)에 저장된 초기 주소값 + size*Byte(자료형에 따라 다름) 으로 바로 접근 가능 하여 O(1) 이라고 납득이 되지만

size를 모를 경우 마지막 데이터가 있는 주소값으로 바로 가려면 array 를 전부 훑어서 O(n)이 될 수 있지 않을까 궁금했습니다.

a 라는 배열 포인터에 초기 주소값과 size 정보를 저장해놓는다.
배열 포인터가 아닌 다른곳에 정보를 저장한다.
array를 전부 훑는건 O(1)이다.

1번, 2번, 3번 중에 어떤 걸까요??

그리고 검색하다 size와 capacity 에 대한 내용을 봤는데

capacity가 Dynamic array에서 처음 선언할때 비어 있는 index를 포함한 크기 로 알고있습니다.

위 제가 판단한것에서 1번, 2번 일경우 size 뿐만 아니라 capacity 정보도 저장해놔야 할것 같은데 저장한다면 어디에 저장 하는 걸까요??

저장을 안한다면(3번) 직접 빠르게 훑어보고 값을 추가 or 삭제 하는 걸까요??

강의 후반부에 설명해 주시는 내용이라면 죄송합니다..

항상 감사합니다!

python 코딩-테스트 알고리즘

답변 2

개발남노씨

지식공유자

2025. 01. 27. 05:46

안녕하세요. s3490147님

좋은 질문 주셨네요.

간단히 설명드리면 2번 (배열 포인터가 아닌 다른곳에 정보를 저장한다.)이 맞겠네요.

Dynamic Array는 class라고 생각하시면 됩니다.

해당 class 안에

첫 주소를 저장한 변수도 있고

할당된 메모리의 크기를 저장하는 변수도 있다고 생각하시면 됩니다.

class 개념으로 설명드리면 이해가 되실거같아서 짧게 설명드립니다.

이해가 잘 안가신다면 다시 말씀해주세요 :)

인프런 AI 인턴

2025. 01. 27. 03:41

안녕하세요, 인프런 AI 인턴입니다.

s3490147님께서 질문해 주신 Dynamic Array의 size와 capacity에 대한 궁금증에 대한 답변을 드리겠습니다.

Dynamic Array를 사용할 때, 컴퓨터는 배열의 크기(size)와 용량(capacity) 정보를 저장하기 위해 별도의 메모리 공간을 활용합니다. 이는 배열을 효율적으로 관리하고, 필요한 경우 크기를 동적으로 조절할 수 있도록 돕습니다. 일반적으로 이러한 정보는 다음과 같은 방식으로 관리됩니다:

배열 포인터 또는 메타데이터 블록에 저장: Dynamic Array는 실제 데이터와 함께 관련 메타데이터를 보유합니다. 이에 따라 size와 capacity 정보가 배열의 메모리 첫 부분이나 별도의 메타데이터 블록에 저장되어 있습니다. 이는 배열 포인터에 객체 형태로 저장되기도 하며, 이러한 메타데이터 덕분에 size와 capacity를 빠르게 참조할 수 있습니다.
size와 capacity를 유지하는 이유: 새로운 요소를 추가해야 할 때, 현재의 size와 capacity 정보를 통해 배열의 크기를 변경할지를 결정합니다. 이 과정은 효율적이며, size 정보가 즉시 접근 가능하기 때문에 요소를 배열에 추가하는 작업이 O(1) 시간 복잡도에서 이루어질 수 있습니다.
size와 capacity 변경의 예: 예를 들어, 파이썬의 리스트는 내부적으로 배열을 사용하여 구현되어 있으며, 이때 capacity는 보통 이진수 배수로 조절되면서 요소를 저장할 충분한 공간을 제공하고, 공간이 부족해지면 자동으로 더 큰 배열을 할당하여 데이터를 복사합니다.

Dynamic Array 작동 원리에 대해 더 깊이 이해하고 싶으시다면, 다음의 유사한 질문과 답변들을 참고하시면 좋을 것 같습니다:

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

인프런 커뮤니티 질문&답변

Dynamic Array 의 size 정보가 저장되는 곳