신입 개발자 기술면접 질문 정리 - 자료구조
목차
- Array와 ArrayList의 차이점에 대해 설명하시오.
- Array와 LinkedList의 장/단점에 대해 설명하시오.
- 해시 테이블과 시간 복잡도에 대해 설명해주세요.
1. Array와 ArrayList의 차이점에 대해 설명하시오.
- Array와 ArrayList는 Java에서 데이터를 저장하는데 사용되는 자료구조
- 연속된 메모리 공간에 데이터를 저장하지만, 사용방법과 기능 면에서는 차이가 있음
1) 사이즈 변경 가능성
1-1) Array
- 고정된 크기를 가지며, 초기화 시에 크기가 정해진다.
- 따라서 배열의 크기를 동적으로 변경할 수없다.
1-2) ArrayList
- 가변 크기를 가지며, 데이터를 추가하거나 삭제함에 따라 크기가 자동으로 조정
- 초기화시에 크기를 명시하지 않아도 된다.
ArrayList<Integer> arrList = new ArrayList<>();
2) 속도
2-1) Array
- 메모리에 연속적으로 할당되기 때문에 ArrayList보다 접근 속도가 빠를 수 있다.
2-2) ArrayList
- 데이터의 추가, 삭제가 발생할 때마다 내부적으로 배열의 크기를 조정하므로, 해당 작업들에서 Array에 비해 손해를 볼 수 있다.
3) 크기변경
3-1) Array
- 크기를 변경할 수 없다.
- 크기 변경이 필요한 경우 새로운 배열을 생성하고 기존 데이터를 복사해야 한다.
3-2) ArrayList
- 추가, 삭제 메소드를 통해 요소를 자유롭게 추가하거나 제거 할수 있어, 보다 유연한 자료구조
3) 결론
- Array는 고정된 크기에 빠른접근 속도가 필요할 때 사용하는 것이 좋다.
- ArrayList는 동적인 데이터 관리가 필요할 때 적합
2. Array와 LinkedList의 장/단점에 대해 설명하시오.
Array (배열의 특징)
1) 장점
- 인덱스를 통한 빠른 데이터 접근 : 배열 내의 특정 데이터에 인덱스를 이용하여 빠르게 접근 가능
- 메모리 사용 효율성 : 연속적인 메모리 공간에 데이터를 저장 하기 때문에 공간의 낭비가 적다. 관리에 효율적
2) 단점
- 고정된 크기 : 배열을 선언할 때 크기가 고정되어, 나중에 크기를 조정하기 어려움
- 삽입, 삭제 작업의 비효율성 : 중간에 데이터를 삽입하거나, 삭제할 때 해당 위치 뒤에 모든 데이터를 이동해야 하므로 비효율적
LinkedList (연결 리스트)의 특징
1) 장점
- 동적인 크기 조정 : 삽입과 삭제가 빈번한 경우, 연결 리스트는 크기를 동적으로 조정할 수 있어 유용
- 삽입, 삭제 작업의 용이성 : 연결 리스트는 데이터를 삽입하거나 삭제할 때 해당 노드의 링크만 변경하면 되므로, 작업이 빠르고 간단
2) 단점
- 접근시간 : 인덱스가 없기 때문에 특정 데이터에 접근하기 위해서는 처음부터 노드를 순회해야 하므로 접근 속도가 배열에 비해 느림
- 메모리 사용량 : 각 데이터마다 다음 데이터의 위치를 가르키는 추가적인 메모리 공간이 필요하기 때문에 , 배열에 비해 메모리 사용량 이 많음
결론
- Array는 인덱스 접근이 빈번하거나 데이터의 크기가 고정적인 경우에 유리
- Linkedlist는 데이터의 추가 및 삭제가 자주 발생하는 동적인 상황에서 효과적
3. 해시 테이블과 시간 복잡도에 대해 설명해주세요.
Hash Table
1) 정의
- 키(Key)와 값(Value)을 연결하여, 한 쌍을 데이터로 저장하는 자료 구조이다. 이를 통해 데이터를 빠르게 검색 할 수 있음
2) 시간 복잡도
- 평균 경우 : O(1)
- 최학의 경우 (충돌 발생 시) : O(N)
- 해시테이블은 대부분의 경우 매우 빠른 데이터 접근 속도를 제공하지만, 여러 키가 동일한 해시값을 가질 때 충돌이 발생 할 수 잇음
시간 복잡도
1) 정의
- 알고리즘 실행 시간의 성능을 나타내는 지표
- 입력 크기가 커질대, 알고리즘 수행 시간이 얼마나 증가하는지를 나타냄
2) 대표적인 시간 복잡도
- O(1) : 상수 시간. 입력데이터의 크기에 상관없이 실행시간이 일정
- O(log n) : 로그 시간. 데이터량이 많아져도 성능이 급격히 떨어지지 않은 효율적인 알고리즘
- O(n) : 선형 시간. 입력 데이터의 크기에 비례하여 실행 시간이 증가
- O(n log n): 선형 로그 시간. 대부분의 효율적인 정렬 알고리즘이 이 시간 복잡도를 가짐
- O(n^2) : 제곱시간. 데이터의 크기에 따라 실행 시간이 제곱으로 증가
출처
신입 개발자 기술면접 질문 정리 - 자료구조
댓글남기기