신입 개발자 기술면접 질문 정리 - 자료구조

목차

1. Array와 ArrayList의 차이점에 대해 설명하시오.
2. Array와 LinkedList의 장/단점에 대해 설명하시오.
3. 해시 테이블과 시간 복잡도에 대해 설명해주세요.

1. Array와 ArrayList의 차이점에 대해 설명하시오.

• Array와 ArrayList는 Java에서 데이터를 저장하는데 사용되는 자료구조
• 연속된 메모리 공간에 데이터를 저장하지만, 사용방법과 기능 면에서는 차이가 있음

1) 사이즈 변경 가능성

1-1) Array

• 고정된 크기를 가지며, 초기화 시에 크기가 정해진다.
• 따라서 배열의 크기를 동적으로 변경할 수없다.

    int[] arr = new int[3];

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) : 제곱시간. 데이터의 크기에 따라 실행 시간이 제곱으로 증가

출처

신입 개발자 기술면접 질문 정리 - 자료구조