자료구조와 알고리즘

자료구조와 알고리즘에 대해 설명해주세요.

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

List

Array와 LinkedList의 차이가 무엇인가요? (N사 전화면접)

1. 접근

Array : Random Access를 지원한다. 요소들을 인덱스를 통해 직접 접근할 수 있다. 따라서 특정 요소에 접근하는 시간복잡도는 O(1)이다.
Linkedlist는 Sequential Access를 지원한다. 어떤 요소를 접근할 때 순차적으로 검색하며 찾아야 한다. 따라서 특정 요소에 접근할 때 시간복잡도는 O(N)이다.

저장방식도 배열에서 요소들은 인접한 메모리 위치에 연이어 저장된다. 반면 Linkedlist에서는 새로운 요소에 할당된 메모리 위치 주소가 linkedlist의 이전 요소에 저장된다.

2. 삽입과 삭제

저장방식도 배열에서 요소들은 인접한 메모리 위치에 연이어 저장된다.
Linkedlist에서는 새로운 요소에 할당된 메모리 위치 주소가 linkedlist의 이전 요소에 저장된다.배열에서 삽입과 삭제는 O(N)이 소요되지만, Linkedlist에서 삽입과 삭제는 O(1)이 소요된다.

3. 메모리 할당

배열에서 메모리는 선언 시 컴파일 타임에 할당이 된다.(정적 메모리 할당) 반면 Linkedlist에서는 새로운 요소가 추가될 때 런타임에 메모리를 할당한다.(동적 메모리 할당)

배열은 Stack 섹션에 메모리 할당이 이루어 진다. 반면 Linkedlist는 Heap 섹션에 메모리 할당이 이루어진다.

자세한 설명 바로가기

ArrayList와 LinkedList의 차이가 무엇인가요?

답

Array와 ArrayList의 차이가 무엇인가요?

답

List와 Set의 차이점과 사용해본 경험

List에는 중복되게 들어갈 수 있지만 Set은 중복이 허용이 되지 않습니다다. List에 있는 데이터를 Set에 넣으면 중복이 제거됩니다. DB의 distinct연산을 하는 효과가 있습니다. 중복이 제거되기 때문에 set에 들어 있다면 고유성이 보장 됩니다. 그래서 중복에 대한 처리를 안해줘도 됩니다.

데이터를 수집, 처리 할 때 중복된 자료들이 수집이 될 수 있습니다. 하지만 결과는 중복되지 않아야 합니다. 그러면 중복된 데이터들을 set에 넣으면 중복이 된 데이터가 있더라도 set안에 들어가면 중복이 없어지기 때문에 중복이 없다는 것이 보장이 됩니다.

대상 id가 저장이 되어 있는 list와 완료된 id가 저장이 되어있는 list가 있을 때 완료가 되지 않은 id만 뽑을 때 대상이 저장이 되어 있는 list와 완료된 id가 저장이 되어있는 두개의 list를 한개의 set으로 합치면 중복을 제거 할 수 있습니다.
자세한 설명 바로가기

Java Collection

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

• List
  ArrayList
  자바의 Vector를 개선한, 배열로 구현된 List이다. 그 말인 즉슨, 데이터가 저장된 순서가 같다는 말이다. 사실상 배열과 같은 자료구조이기 때문에, 리스트의 연산 자체의 수행시간 속도는 배열과 같다.
  LinkedList
  다음 노드의 주소를 기억하고 있는 List로, 배열에 비해 삽입과 삭제가 간단하다. 그러나 탐색의 경우 첫 번째 노드부터 탐색해 나가야 하기 때문에 느리다.
• Map
  HashMap
  가장 일반적으로 사용하는 Map. HashTable을 사용, Key값에 해시함수를 적용하여 나온 index에 Value를 저장하는 식. 중복성을 허용하지 않으며, 순서가 없다는 것이 특징
  TreeMap
  Red-Black Tree 자료구조를 이용한 Map이다. Tree 구조이기 때문에 어느 정도 순서를 보장한다.
  LinkedHashMap
  LinkedList로 구현된 HashMap이다. List로 구현되어있기 때문에 순서가 보장된다. 하지만 LinkedList 특성상 랜덤 접근에서 느릴 수 있다.
• Set
  HashSet
  HashMap에서 Key값이 없는 자료형. 집합이라고 생각해도 무방하다. 값이 포함되어 있는지 아닌지만 관심이 있다. 순서를 보장하지 않으며, 중복값을 허용하지 않는다. Set중에는 가장 많이 사용된다.
  TreeSet
  Red-Black Tree 자료구조를 사용한 Set.
  LinkedHashSet
  LinkedList로 구현된 HashSet. 순서를 보장한다.
• Stack & Queue
  Stack
  직접 new 연산자로 객체를 생성하여 사용 가능.
  Queue
  LinkedList 에 new 연산자로 객체를 생성함으로서 사용 가능.
• 추가로 자바 Array와 ArrayList의 다른점.
  둘 다 배열이라는 점은 동일하나, Array는 인덱스로 접근하는 반면, ArrayList는 메서드를 통해 접근한다(어짜피 Index로 호출한다는 점은 동일 하겠지만..). 또한 Array는 Object 뿐만 아니라 원시 형태(Primitive, 예를 들어 int, double 등)도 담을 수 있지만, Array는 Object형(Reference, 객체)만 담을 수 있다. 따라서 정수를 ArrayList에 넣을 경우 Integer형은 가능하지만 int형은 안 된다. 덧붙여서, Integer처럼 int와 같은 원시타입을 담을 수 있는 객체를 Wrapper Class라고 한다.

Stack과 Queue

Stack과 Queue의 차이점은 무엇인가요? (N사 전화면접)

세로로 된 바구니와 같은 구조로 먼저 넣게 되는 자료가 마지막으로 나오게 되는 First-In Last-Out(FILO) 구조이다. List로 구현하면 객체를 제거하는 작업이 필요하다. 하지만 Array로 구현하면 삭제할 필요 없이 index를 줄이고 초기화만 하면 되므로, Array로 구현하는 것이 좋다.
top을 통해서 push, pop을 하면서 삽입과 삭제가 일어난다. DFS나 재귀에서 사용된다.

큐는 원소의 줄을 세우는 자료구조이다. 가로로 된 통과 같은 구조로 먼저 넣게 되는 자료가 가장 먼저 나오는 First-In First-Out(FIFO) 구조이다. Array로 구현하면 poll 연산 이후 객체를 앞당기는 작업이 필요하다. 하지만 List로 구현하면 객체 1개만 제거하면 되므로 삽입 및 삭제가 용이한 LinkedList로 구현하는 것이 좋다.큐는 한 쪽 끝에서 삽입 작업을, 다른 쪽 끝에서 삭제 작업을 진행한다. 선입선출 구조이다. 주로 데이터가 입력된 시간 순서대로 처리되어야 하는 경우 사용한다. BFS나 캐시를 구현할 때 사용한다.

자세한 설명 바로가기

PriorityQueue의 동작 원리가 어떻게 되나요? (N사 전화면접)

우선순위큐는 가장 우선순위가 높은 데이터를 먼저 꺼내기 위해 고안된 자료구조입니다. 우선순위 큐를 구현하기 위해서 일반적으로 힙을 사용합니다. 힙은 완전이진트리를 통해서 구현되었기 때문에 우선순위 큐의 시간복잡도는 O(logn)입니다.

우선순위 큐는 힙이라는 자료구조를 가지고 구현한다. top이 최대면 최대힙, top이 최소면 최소힙으로 표현한다. 힙으로 구현된 이진 트리는 모든 정점이 자신의 자식 요소보다 우선순위가 높다는 성질을 가지고 있다. 이 성질을 통해 삽입과 삭제 연산을 모두 O(logN)으로 수행할 수 있다.
자세한 설명 바로가기

Tree

BST와 Binary Tree에 대해서 설명하세요. (N사 전화면접)

이진탐색트리(Binary Search Tree)는 이진 탐색과 연결 리스트를 결합한 자료구조이다. 이진 탐색의 효율적인 탐색 능력을 유지하면서, 빈번한 자료 입력과 삭제가 가능하다는 장점이 있다. 이진 탐색 트리는 왼쪽 트리의 모든 값이 반드시 부모 노드보다 작아야 하고, 반대로 오른쪽 트리의 모든 값이 부모 노드보다 커야 하는 특징을 가지고 있어야 한다. 이진 탐색 트리의 탐색, 삽입, 삭제의 시간복잡도는 O(h)이다. 트리의 높이에 영향을 받는데, 트리가 균형이 맞지 않으면 워스트 케이스가 나올 수 있다. 그래서 이 균형을 맞춘 구조가 AVL Tree이다.
자세한 설명 바로가기

Hash

해시테이블(HashTable)에 대해서 설명해주세요.

해시테이블은 효율적인 탐색을 위한 자료구조로 key값을 value에 대응시킨다. 해시테이블을 구현하기 위해서는 연결 리스트와 해쉬 함수가 필요하다. 해싱은 임의의 길이의 값을 해쉬 함수를 통해 고정된 크기의 값으로 변환하는 작업을 말하는데, 키 값을 해시 코드로 변환한 후 해당 해시 코드로 배열의 인덱스를 참조하여 값을 찾는다. 충돌이 발생할 수 있으며, 최악의 경우 O(N), 일반적으로 잘 구현된 경우는 O(1)의 시간 복잡도를 가지게 된다. 충돌은 Chaining, Open addressing 등의 방식으로 해결할 수 있다.

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

해시 테이블와 해시 테이블의 시간 복잡도에 대해 설명하시오.

해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠른 데이터 검색이 필요할 때 유용합니다. 해시 테이블은 Key값에 해시함수를 적용해 고유한 index를 생성하여 그 index에 저장된 값을 꺼내오는 구조입니다.

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

HashMap과 HashTable의 차이점에 대해 설명 해보세요.

동기화 지원 여부의 차이가 있다.

// 해시테이블의 put
public synchronized V put(K key, V value) {
    // Make sure the value is not null
    if (value == null) {
        throw new NullPointerException();
    }
    // Makes sure the key is not already in the hashtable.
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    Entry<K,V> entry = (Entry<K,V>)tab[index];
    for(; entry != null ; entry = entry.next) {
        if ((entry.hash == hash) && entry.key.equals(key)) {
            V old = entry.value;
            entry.value = value;
            return old;
        }
    }
    addEntry(hash, key, value, index);
    return null;
}

// 해시맵의 put
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

병렬 처리를 하면서 자원의 동기화를 고려해야 하는 상황이라면 해시테이블(HashTable)을 사용해야 하며, 병렬 처리를 하지 않거나 자원의 동기화를 고려하지 않는 상황이라면 해시맵(HashMap)을 사용하면 된다.

출처
https://devowen.com/285
https://mangkyu.tistory.com/89
https://velog.io/@hygoogi/%EA%B8%B0%EC%88%A0%EB%A9%B4%EC%A0%91-%EC%A4%80%EB%B9%84%ED%95%98%EA%B8%B0