배열의 삭제 시간복잡도

Question

배열의 삽입, 삭제 시간복잡도에 대해서 shift가 필요히니 O(n)이라고 하셨는데요. 삽입의 경우 해당 인덱스의 원소 값을 바꾸는 것이 아닌 기존 값을 유지하면서 새로운 값을 그 위치에 놓고자 한다면 O(n)이 맞겠습니다만 삭제의 경우 그냥 해당 위치를 초기화하면 되지 않을까요? 물론 말씀하신대로 쉬프트가 필요하다면 O(n)이 맞지만 삭제 연산에서 쉬프트가 필수적인가? 하는 의문이 있습니다.

개발남노씨 · Answer

안녕하세요 현강님. 삭제를 할 때와 삽입을 할 때 모두 shift를 해야만 하는 이유가 있어요.   배열은 연속적이고 순차적으로 메모리에 저장되어야 한다는 정의 때문이에요. 왜 굳이 연속적이고 순차적으로 저장하냐라고 물으신다면, random access의 장점을 이용하기 위해 그렇게 정의를 한 겁니다.   물론 삭제할 때 굳이 땡기지 말고 빈자리(공석)으로 남기면 안되나? 라고 물으신게 맞으시죠??! 삭제 후에 빈자리가 생기면 굳이 땡기지(shift)말고 그냥 놔두면, 그곳에 있는 데이터를 잘 못 접근했을 때 생기는 문제등을 해결하기 위해 "이곳은 빈 곳입니다" 라는 라벨을 걸어둬야 할 거에요.   결국 여러가지 효율적인 문제때문에도 그렇고, 배열의 정의때문에도 삽입 삭제를 할 때는 연속적이고 순차적인 성질을 유지하기 위해 shift를 해줘야 합니다.   혹시 질문에 대한 답이 됐을까요~? 더 궁금한점이 있으면 편하게 질문주세요!