Array와 ArrayList의 차이점에 대해 설명해주세요. -> 정진님
뭐가 더 빠를까요 ?
왜 그렇게 생각하나요 ?
어떨때 사용하면 좋을까요 ?
Array와 LinkedList의 장/단점에 대해 설명해주세요. -> 영선님
어떨때 사용하면 좋을까요 ?
Stack과 Queue의 실사용 예를 들어 간단히 설명해주세요. -> 채린님
java 에서 Stack은 어떤 클래스를 상속 받고 있는지 ? -> Vector
그렇다면 솔리드 원칙에서 어떤것을 위해하는 거 같은지 ?
왜 그렇게 생각하는지 ?
BST(Binary Search Tree)와 Binary Tree에 대해 설명해주세요. -> 영선님
어떨때 사용하면 좋을지 ?
BST(Binary Search Tree)와 Binary Tree는 데이터 구조로서 서로 다른 용도에 사용됩니다:
BST (Binary Search Tree):
BST는 정렬된 데이터를 저장하고 탐색하는 데에 효율적입니다.
BST는 모든 노드에 대해 다음 규칙을 만족합니다: 왼쪽 서브트리에 있는 모든 노드의 값은 해당 노드의 값보다 작고, 오른쪽 서브트리에 있는 모든 노드의 값은 해당 노드의 값보다 큽니다.
이러한 정렬된 속성으로 인해 BST는 이진 탐색 알고리즘을 구현하는 데에 유용합니다.
주로 탐색, 삽입, 삭제 연산을 수행해야 할 때 BST를 사용합니다.
Binary Tree:
Binary Tree는 각 노드가 최대 두 개의 자식 노드를 갖는 트리 구조입니다.
Binary Tree는 데이터를 구조화하고 계층적으로 표현하는 데에 사용됩니다.
데이터의 순서를 유지할 필요가 없거나, 특정한 정렬 순서를 갖지 않는 데이터를 다룰 때 Binary Tree를 사용할 수 있습니다.
예를 들어, 파일 시스템의 폴더 구조, 계층적인 조직도, 파싱 트리 등의 구조를 표현할 때 Binary Tree를 사용할 수 있습니다.
따라서 BST는 정렬된 데이터와 탐색 연산에 특화되어 있으며, Binary Tree는 계층적인 데이터 구조를 표현할 때 사용됩니다. 데이터의 특성과 필요에 따라 BST 또는 Binary Tree를 선택하여 구현해야 합니다.
직접 구현해 본적있는지 있다면 어떻게 구현했는지 ?
없다면 어떻게 구현하면 좋을지 ?
해시 테이블(Hash Table)과 시간 복잡도에 대해 설명해주세요. -> 채린님
시간 복잡도가 O(1) 인데 다른 구조 말고 해시 테이블로만 사용하면 안되나요 ?
왜 그럴까요 ?
충돌(Collision):
해시 함수를 사용하여 키를 해시 코드로 변환하고 해당 해시 코드에 대응하는 인덱스에 값을 저장합니다. 그러나 서로 다른 키가 동일한 해시 코드를 생성할 수 있습니다. 이를 해시 충돌이라고 합니다.
충돌이 발생하면 값을 저장하거나 검색할 때 충돌을 해결하기 위한 추가 작업이 필요합니다. 충돌을 해결하기 위한 방법으로는 체이닝(Chaining) 또는 개방 주소법(Open Addressing) 등이 있습니다. 이는 추가적인 메모리 및 연산 비용을 초래할 수 있습니다.
메모리 사용량:
해시 테이블은 일반적으로 키와 값의 쌍을 저장하기 위한 고정 크기의 배열을 사용합니다. 따라서 큰 데이터셋을 다루거나 키 공간이 큰 경우에는 메모리 사용량이 커질 수 있습니다.
해시 충돌을 해결하기 위해 체이닝 방식을 사용할 경우, 각 버킷에 연결 리스트를 유지해야 합니다. 이는 추가적인 메모리 오버헤드를 발생시킬 수 있습니다.
정렬된 순서의 유지가 어려움:
해시 테이블은 주로 키-값 쌍을 빠르게 저장하고 검색하기 위해 사용됩니다. 그러나 해시 테이블은 일반적으로 키에 대한 정렬된 순서를 유지하지 않습니다.
만약 정렬된 순서가 필요한 경우, 해시 테이블을 사용하기보다는 TreeMap 등의 자료구조를 고려해야 합니다.
해시 함수의 선택:
해시 함수의 품질에 따라 충돌이 더 빈번하게 발생할 수 있습니다. 좋은 해시 함수를 선택하고 충돌을 최소화하기 위해 추가적인 작업이 필요할 수 있습니다.
HashMap에서 key가 Int, Long등을 쓸 경우에 어떤 일이 일어나는지 설명해 주시세요 -> 정진님 or 같이 ?
: 기본적으로 HashMap은 해시코드를 통해 검색을 합니다. 그래서 Int나 Long 같은 기본 타입으로 키를 지정할 경우 해당 값을 해시코드로 변환해줘야합니다. 이 과정에서 검색에 성능저하를 가져올 수 있고, 만약 기본 타입을 감싸는 래퍼 클래스를 사용하면 불필요한 객체 생성이 발생하여 메모리 사용량이 늘어나는 문제가 있습니다.
해결 방법으로는 안드로이드에서는 SparseArray라는 클래스를 지원해 주고 있습니다. SparseArray의 동작 방식은 HashMap과 유사하지만 key가 기본 타입인 경우에도 별도의 래퍼 클래스를 사용하지 않고 직접 사용할 수 있습니다.
HashMap의 기본 동작인 put, get에 대해 각각 설명해 주시고, HashMap 동작 방식을 Object 클래스의 equlas(), hash() 메소드와 연관시켜 설명해 주세요. -> 채린님
Put은 해당 키 값이 있다면 값을 수정해주고, 없다면 할당해줍니다. Get 의 경우는 해당 키 값이 있을 경우 해당 값을 반환해주고 없다면 null을 반환합니다.
그리고 해시맵은 기본적으로 key와 값을 해시 테이블에 저장하고, key 값들은 고유의 해시 코드를 가집니다. put이나 get을 실행할때 키값을 해시코드로 변환해서 검색을 하게 되는데, 이때 만약 equals()와 hashCode() 메서드가 재정의 되어 있지 않으면 Object 의 클래스에 정의 되어있는 equals()와 hashCode() 메서드를 사용하게 됩니다. Object 클래스의 equals()와 hashCode()는 참조 주소를 비교하는것이 아니라 값자체를 비교하기 때문에, 같은 key라도 다른 객체로 인식할수 있습니다. 그래서 hashMap을 사용할 때는 equals()와 hashCode() 메서드를 재정의 해서 같은 key 라면 같은 객체라고 정의하는 것이 좋다고 알고 있습니다.
