Today 요약

1.CS 면접대비

1. What I Learned?

CS 면접대비

Array는 어떤 자료구조 인가요?

Array는 연관된 데이터를 순차적이며 연속적으로 할당된 크기만큼 저장하는 자료구조입니다.

Array의 특징

• 연속적이며 순차적으로 저장하기 때문에 특정 인덱스를 조회하는 것은 첫 데이터에서 인덱스만 더해서 조회하면 되기 때문에 시간복잡도가 O(1)입니다.
• 또한 가장 마지막 데이터에 더하거나 마지막 데이터를 삭제할 때도 마지막 인덱스에 접근해서 더하거나 삭제하면 되기 때문에 이 또한 시간복잡도가 O(1)입니다.
• 하지만 중간에 더하거나 삭제할 때는 더하거나 삭제하고자 하는 인덱스 뒤에 있는 배열 요소들을 뒤로 전체적으로 밀어주거나 앞으로 당겨주어야 하기 때문에 이 경우에는 시간복잡도가 O(n)입니다.
• 그리고 특정 값을 검색할 때도 배열을 모두 일일히 접근해서 해당 데이터가 내가 찾고자 하는 데이터와 일치하는지 비교 검색해야 되기 때문에 검색할 때도 시간복잡도는 O(n)입니다.
• 할당된 크기만큼 저장하기 때문에 메모리가 낭비되거나 추가적인 오버헤드가 발생할 수 있습니다.