[자료구조] 면접

자료구조와 알고리즘의 대한 설명

자료구조는 데이터를 원하는 규칙 또는 목적에 맞게 저장하기 위한 구조이고, 알고리즘은 자료구조에 쌓인 데이터를 활용해 어떠한 문제를 해결하기 위한 여러 동작들의 모임이다.

Array와 LinkedList의 차이

[Array]

• Random Access를 지원한다. 요소들을 인덱스를 통해 직접 접근할 수 있다. 따라서 특정 요소에 접근하는 시간복잡도는 O(1)이다.
• 배열은 데이터를 저장할 때 인접한 메모리 위치에 연이어 저장된다. 배열에서 삽입과 삭제는 O(N)이 소요된다.
• 배열에서 메모리는 선언 시 컴파일 타임에 할당이 된다.(정적 메모리 할당)
• 배열은 Stack섹션에 메모리 할당이 이루어진다.

[LinkedList]

• Sequential Access를 지원한다. 어떤 요소를 접근할 때 순차적으로 검색하며 찾아야 한다. 따라서 특정 요소에 접근할 때 시간복잡도는 O(N)이다.
• 새로운 요소에 할당된 메모리 위치 주소가 LinkedList의 이전 요소에 저장된다. LinkedList에서 삽입과 삭제는 O(1)이 소요된다.
• LinkedList에서는 새로운 요소가 추가될 때 런타임에 메모리를 할당한다.(동적 메모리 할당)
• LinkedList는 Heap섹션에 메모리 할당이 이루어진다.

Array와 ArrayList의 공통점과 차이점

[공통점]

• Array와 ArrayList는 요소를 추가하거나 가져올 때 성능이 비슷하다. 두 작업 모두 일정한 시간에 실행된다.
• 둘 다 중복되는 요소를 저장할 수 있다.
• Null값을 저장할 수 있고 인덱스를 사용하여 값을 참조할 수 있다.
• 순서가 지정되지 않는다.

[차이점]

• Array는 고정 길이를 갖는다. 따라서 정해진 길이의 배열을 모두 사용하면 새로운 데이터를 추가하고 싶을 경우 새로운 배열을 만들어주어야 한다.
• ArrayList는 가변 길이이다. 하지만 내부적으로는 배열로 구성되어 있다. ArrayList는 기본으로 10개의 공간을 가진 배열로 시작한다. 하지만 최적화로 인해 막 생성하면 0개의 사이즈로 시작된다. 성능은 Array보다 살짝 느리다.

	Array	ArrayList
사이즈	초기화시 고정	초기화시 사이즈를 표시하지 않음(동적)
속도	초기화시 메모리에 할당되어 속도 빠름	추가시 메모리를 재할당하여 속도가 느림
변경	사이즈 변경 불가	추가, 삭제 가능
다차원	가능	불가능
타입	primitive type	object element
제네릭	사용 불가능	사용 가능(타입 안전성 보장)
길이	length	size()
변수 추가	assignment 연산자 사용	add() 메서드 사용

List와 Set의 차이점

[List]

• List에는 데이터가 중복으로 들어갈 수 있다.
• List에 있는 데이터를 Set에 넣으면 중복이 제거된다. => DB의 distinct연산 효과

[Set]

• Set에는 데이터가 중복으로 들어갈 수 없다.
• Set에 존재하는 데이터는 고유성이 보장된다.
• 데이터를 수집, 처리할 때 중복된 자료들이 수집될 수 있다. 하지만 수집 결과는 중복되지 않아야 한다. 중복된 데이터들을 Set에 넣으면 중복이 된 데이터가 있더라도 중복이 제거되는 효과를 가져온다.

코로나 검사 대상 ID가 저장되어 있는 List와 코로나 검사 완료 ID가 저장되어 있는 List가 있을 때 완료가 되지 않은 ID만 뽑을 때 두개의 List를 한개의 Set으로 합치면 중복을 제거할 수 있다.

Java Collection

자바의 대표 Collection에는 List, Map, Set, Stack, Queue와 같은 것들이 있다. 이 추상화된 Collection인터페이스 아래, 특정한 기법으로 구현된 자료구조가 들어간다.

• List
  • ArrayList: 배열로 구현된 리스트이다. 데이터가 저장된 순서가 같고 리스트의 수행시간 속도는 배열과 같다.
  • LinkedList: 다음 노드의 주소를 기억하고 있는 리스트로, 배열에 비해 삽입과 삭제가 간단하다. 하지만 탐색의 경우 첫 번째 노드부터 탐색해 나가야 하기 때문에 느리다.
• Map
  • HashMap: 가장 일반적으로 사용하는 Map이고, HashTable을 사용하여 Key값에 해시 함수를 적용하여 나온 인덱스에 Value를 저장하는 방식이다. 중복을 허용하지 않고 순서가 없다는 것이 특징이다.
  • TreeMap: Tree구조이기 때문에 어느정도 순서를 보장한다. Red-Black Tree자료구조를 이용한 Map이다.
  • LinkedHashMap: LinkedList로 구현된 HashMap이다. List로 구현되어 있기 때문에 순서가 보장된다. 하지만 LinkedList의 특성 상 랜덤 접근에서 느릴 수 있다.
• Set
  • HashSet: HashMap에서 Key값이 없는 자료형으로 값이 포함되어 있는지 아닌지만 관심이 있다. 순서를 보장하지 않으며, 중복 값을 허용하지 않는다.
  • LinkedHashSet: LinkedList로 구현된 HashSet, 순서를 보장한다.

Stack과 Queue의 차이점

스택은 LIFO(Last-In First-Out)의 특징을 갖는 자료구조이다. TOP은 스택의 가장 상단 부분을 가리키고 있는데, TOP을 통해 PUSH나 POP연산을 수행하며 삽입과 삭제가 일어난다. 배열로 구현할 경우 TOP의 위치에 있는 값을 초기화하고 TOP의 위치를 -1한다.

큐는 FIFO(First-In First-Out)의 특징을 갖는 자료구조이다. 큐의 가장 앞을 Front 가장 뒤를 Rear로 부르고, 원소를 추가할 경우 현재 Rear의 위치 다음에 저장이되고 원소를 삭제할 경우 Front에서 삭제가 이루어진다. 배열로 구현할 경우 한 개의 원소를 삭제하면 기존에 있던 원소들을 한 칸씩 앞당겨 줘야하는 작업을 해야하는데 이때문에 연결리스트를 사용하는 것이 더 효과적이다.

PriorityQueue의 동작 원리

우선순위큐는 가장 우선순위가 높은 데이터를 먼저 꺼내기 위해 고안된 자료구조이다. 우선순위큐를 구현하기 위해서는 일반적으로 힙을 사용한다. 힙은 완전 이진트리의 특성을 갖고 시간 복잡도는 O(logN)이다. 루트노드가 최대일 경우 최대 힙, 루트노드가 최소일 경우 최소 힙으로 표현한다. 힙으로 구현된 이진트리는 모든 정점이 자신의 자식보다 우선순위가 높다는 성질을 갖고있다. 이 성질을 통해 삽입과 삭제 연산을 모두 O(logN)으로 수행할 수 있다.

Binary Search Tree와 Binary Tree

이진탐색트리는 이진 탐색과 연결 리스트를 결합한 자료구조이다. 이진 탐색의 효율적인 탐색능력을 유지하면서, 빈번한 자료 입력과 삭제가 가능하다는 장점이 있다. 이진탐색트리는 왼쪽 트리의 모든 값이 부모 노드보다 작아야하고, 반대로 오른쪽 트리의 모든 값이 부모 노드보다 커야하는 특성을 가지고 있어야 한다. 이진탐색트리의 탐색, 삽입, 삭제의 시간복잡도는 O(h)이다.

HashTable에 대해 설명

해시테이블은 효율적인 탐색을 위한 자료구조로, Key값을 Value에 대응시킨다. 해시테이블을 구현하기 위해서는 연결 리스트와 해시 함수가 필요하다. 해싱은 임의의 길이의 값을 해시 함수를 통해 고정된 크기의 값으로 변환하는 작업을 말하는데 키 값을 해시 코드로 변환한 후 해당 해시 코드로 배열의 인덱스를 참조하여 값을 찾는다.

해시테이블은 고유한 인덱스로 값을 조회하기 때문에 평균적으로 O(1)의 시간복잡도를 갖는다. 하지만 해시의 인덱스값이 충돌한 경우 충돌된 인덱스 값에 대해 연결된 데이터를 조회하여 원하는 값을 조회하기 때문에 O(N)까지 증가할 수 있다.

충돌을 해결하기 위해서는 Chaining방식, 선형 조사법, 이차 조사법, 이중 해시를 사용한다.

Chaining방식은 닫힌 어드레싱 방법으로 무슨일이 있어도 자신의 자리에 데이터를 저장하는 것을 의미한다. 이것을 가능하게 수행하려면 값을 저장할 자리를 여러 개 생성해야하는데 보통 연결리스트를 사용하여 구현한다.

선형 조사법은 충돌이 발생했을 때 그 옆자리가 비어있는지 살펴보고, 비어있을 경우 그 자리에 대신 저장하는 방법이다. 옆자리가 비어있지 않을 경우 한칸 더 이동을 해서 자리를 살피게 된다. 하지만 충돌의 횟수가 증가함에 따라 클러스터 현상이 발생한다.

이차 조사법은 선형 조사법의 단점을 극복하기 위해 고안된 방법이다.충돌이 발생하게 될 경우 좀 멀리서 빈 공간을 찾는 방법이다.

이중 해시는 빈 공간을 불 규칙적으로 구성하는 방법으로 두 개의 해시 함수를 사용한다.

해시테이블은 균형 이진탐색트리로 구현할 수 있다. 이 경우에는 탐색 시간이 O(logN)이된다. 이 방법은 크기가 큰 배열을 미리 할당해 놓지 않아도 되기 때문에 잠재적으로 적은 공간을 사용한다는 장점이 있다.