자료구조

1. 스택과 큐 설명

2. 배열과 연결 리스트의 장단점

  1. 두 개의 포인터를 사용한다. 하나는 한 칸씩 방문하고, 다른 하나는 두 칸씩 방문한다.
  2. 두 칸씩 방문하는 포인터가 연결 리스트의 마지막에 도달했을때, 한 칸씩 방문하는 포인터가 가리키는 위치가 중간 노드이다.

4. 원형 연결 리스트인지 확인할 수 있는 방법은?

투포인터를 이용하여 한개의 포인터는 두개씩 이동, 한개의 포인터는 한개씩 이동하여 두 포인터가 만나게 된다면 리스트가 원형임을 확인할 수 있습니다.

5. 1에서 100까지의 정수가 있는 배열에서 한개가 중복되었다. 어떻게 찾을까?

1에서 n까지 정수를 더한 값은 n(n-2)/2이다. 배열 안의 숫자를 모두 더한 값에 이 값을 빼면 중복된 값을 찾을 수 있다. => n이 매우 큰 수일 경우, 이진수로 각 수가 나타났는지 체크하는 방법이 있다.

6. 자바에서 문자열을 뒤집는 방법은?

재귀적으로 가능하다.

7. 이진 탐색 트리 설명

이진 탐색 트리는 이진 탐색과 연결 리스트가 결합된 자료구조이다.

  1. 검색
    • 루트 노드에서 시작한다. 키 값과 찾으려는 값을 비교하고, 찾으려는 값이 더 작으면 왼쪽, 더 크면 오른쪽 자식 노드로 이동한다. 같을 경우 검색에 성공하며, 리프 노드에 도달할 때 까지 찾지 못하면 실패한다.
  2. 삽입
    • 검색과 동일하게 이루어진다. 검색에 실패하면 그 자리에 노드를 삽입한다.
    • 삽입의 시간복잡도는 O(h)이다.
  3. 삭제
    • (1) 삭제하려는 노드가 단말 노드인 경우
      단말 노드의 부모 노드를 찾아서 연결을 끊는다.
    • (2) 삭제하려는 노드가 서브트리를 하나만 가지고 있는 경우
      서브트리를 부모 노드에 붙여주고 노드를 삭제한다.
    • (3) 삭제하려는 노드가 두개의 서브트리를 가지고 있는 경우
      서브트리에서 삭제하려는 노드와 가장 비슷한 값을 가진 노드를 찾아 해당 위치로 옮긴다.

8. 해시 테이블에서 Collision발생 시 해결법

해시에서는 충돌이 발생 할 수도 있는데 최악의 경우에는 O(N), 일반적으로 잘 구현 된 경우에는 O(1)의 시간 복잡도를 가지게 됩니다.

충돌의 해결방식은 Chaining, Open addressing 이 있습니다.

9. 그래프와 트리 차이점

10. 우선순위 큐 구현방법 설명

우선순위 큐는 Complete Binary Tree로 삽입 연산때는 마지막 위치에 삽입되며 부모 노드와 비교하며 자신의 위치를 찾아간다. 삭제 연산에는 첫번째 노드를 삭제하며 마지막 노드를 첫번째 노드로 옮겨와 자식 노드와 비교하며 두 자식노드중 가장 조건에 부합한 노드와 비교하며 자신의 위치를 찾아간다.

11. 해시 테이블 설명

효율적인 탐색을 위한 자료구조로, Key값을 Value에 대응시킨다.

12. 배열과 연결리스트의 삽입 삭제 시간 복잡도 설명

  1. 배열에서의 삽입 삭제는 O(N) 타임이 소요됩니다. 왜냐하면 삽입이나 이후 요소들을 밀고 당기는 과정이 포함되기 때문입니다.
  2. 하지만 연결리스트의 삽입 삭제는 O(1) 이 소요됩니다. 삽입위치의 전후 포인터만 조정해주면 되기 때문입니다.

13. 문자열 검색을 위한 자료구조와 이에 대한 장단점

Trie 자료구조

14. 균형 이진 트리의 시간 복잡도

O(log N)

15. 스택 두개로 큐를 만드는 방법

  1. 메인 스택과 서브 스택을 만든다.
  2. 큐의 enqueue는 메인 스택에 데이터를 push한다.
    처음으로 큐에서 dequeue을 할때, 메인 스택의 데이터들을 모두 pop해서 서브 스택에 push한다.
    그러면 메인 스택의 데이터들의 순서가 뒤집히게 된다. 이 때, 서브 스택에서 pop하면 dequeue를 구할 수 있다.
    또 다시 dequeue해야 한다면 서브 스택에서 pop을 하면 된다.
  3. enqueue를 할 때는 서브 스택의 데이터들을 모두 pop하여 메인 스택에 push하고 그 위에 데이터를 push한다.

16. n개의 배열에서 k번째로 큰 수를 찾는 방법

  1. 퀵소트의 pivot찾기를 활용합니다.
    1. pivot을 기준으로 좌측의 수들은 pivot보다 작은수 우측의 수들은 pivot 보다 큰 수 이므로 좌, 우측의 정렬 여부와 상관없이 해당 pivot의 위치는 확정적이므로 pivot의 인덱스가 k-1(인덱스시작이 0이라고 했을때)로 잡히는 경우 k번째 큰 수 라고 할 수 있습니다.
  2. max heap을 이용합니다.
    1. tree 의 크기가 k가 될 때 까지 입력을 받고 k보다 큰경우 heap에 넣은뒤 한개 씩 삭제하여 tree의 크기를 k로 유지하게합니다.
    2. 그렇게 다 입력을 받은 경우 루트노드에 있는 값이 k번째로 큰 수입니다.

17. 최소 스패닝 트리(Minimum Spanning Tree)에 대해서 설명해주세요.

MST는 그래프의 Spanning Tree중 간선의 가중치 합이 최소인 Spanning Tree를 의미한다. 여기서 Spanning Tree는 루프가 없고 모든 그룹 노드를 포함하고 있어야 한다.

18. selection sort란?

O(n^2)의 시간복잡도와 O(1)의 공간복잡도를 가지는 unstable한 정렬이다. 0 ~ n번째 위치를 순회하며 현재 자리에 들어오기 가장 적합한 노드를 선택해 스왑한다. 그 뒤엔 1 ~ n 번째, 2 ~ n 번째.. 반복적으로 수행한다.

19. Insertion Sort란?

O(n^2)의 시간복잡도와 O(1)의 공간복잡도를 가지는 stable한 정렬이다. 1번째 노드를 그 앞 노드들과 비교하며 조건에 맞다면 스왑을 하고 조건에 맞지 않으면 멈춘다. 그 다음엔 2번째, 3번째, .. n번째 노드를 반복적으로 수행한다. 이런 특성상 이미 정렬된 상태의 배열이라면 O(n)의 최선의 시간복잡도를 가진다.

20. Merge Sort란?

  1. 필요한 데이터만 복사한다. 정렬해야할 그룹이 left = {3, 4, 5}, right = {1, 2} 일때 임시 버퍼를 buffer[5] 즉 {x, x, x, x, x}의 공간을 할당받지 않고 개수가 많은쪽의 데이터의 크기만큼만 복사한다.(여기서는 left) 그렇게 되면 정렬은 다음과 같이 진행할 수 있다.

buffer = {3, 4, 5} //임시로 할당되는 공간
right = {1, 2} //개념적 공간임 사용하는 공간은 array의 공간을 사용하되 구분짓기 위한
array = {3, 4, 5, 1, 2} //현재 배열에 들어가있는 데이터의 순서

이 때 정렬은 left의 데이터를 가져왔으므로 앞에서부터 수행해야 한다. (right의 공간을 가져왔으면 뒤에서부터 채워넣어야함)

buffer = {3, 4, 5}
right = {2}
array = {1, 4, 5, 1, 2}

buffer = {3, 4, 5}
right = {}
array = {1, 2, 5, 1, 2}
이 때 right가 비게 되므로 기존 Merge Sort의 방식 그대로인 남아있는 곳의 데이터를 모두 복사하는 방식으로 진행

buffer = {}
right = {}
array = {1, 2, 3, 4, 5}

O(n/2)의 공간 복잡도를 가지게 되지만 Big-O 표기를 하게 되면 O(n)이라고 표현하게 된다.
그냥 이런 방법도 있다는걸 알아 두시면 좋을꺼 같아요 어짜피 표현은 둘다 O(n)이라고 표현하게 되겠지만요..

21. quick sort란?

퀵 소트 또한 분할 정복을 이용하여 정렬을 수행하는 알고리즘 입니다.

pivot point 라는 기준이되는 값을 하나 설정하여 이값을 기준으로 작은 값은 왼쪽 큰값은 오른쪽으로 옮기는 방식으로 정렬을 진행합니다.

이를 반복하여 분할된 배열의 크기가 1이되면 모두 정렬이 된 것 입니다.

여기서 pivot point는 주로 배열의 값중 맨 앞이나 맨뒤, 중간 혹은 랜덤값으로 정하게 되는데 배열의 맨 앞값이나 맨 뒤의 값으로 정하는 경우 정렬된 상태에서 최악의 케이스로 시간 복잡도 O(n^2) 을 가지게 됩니다.

그래서 주로 배열의 중간값이나 랜덤 값으로 pivot point 를 잡습니다.

평균적인 시간 복잡도는 O(nlogn) 입니다.

22.list, set, map의 차이

Java의 Collection을 구현한 대표적인 자료구조로 lisk, set, map이 있다.

+LinkedHashMap
HashMap과 비슷하지만, 각 요소가 이전 값과 다음 값의 포인터를 가지고 있어 순서를 이룰 수 있다.

++HashTable
Map을 구현한 클래스로, Thread safe를 보장한다. key 값에 null을 허용하지 않는다.

23. 데이터의 개수가 백만개일때 정렬방법

외부정렬(External Sort)를 이용한다. 외부정렬이란 입력크기가 매우커 읽고 쓰기가 오래 걸리는 보조 기억장치에 저장할 수 밖에 없는 상태에서 수행되는 정렬이다.

메모리에서 다룰 수 있는 크기에 데이터를 다루던 정렬은 내부정렬(Internal Sort)로 분류한다.

24. 그래프를 구현하는 방법

장점: 노드 i와 노드 j가 연결되었는지 확인하고 싶을 때 인덱스로 바로 접근이 가능해 O(1)의 시간 복잡도를 가진다.
단점: 어떤 노드에 연결된 모든 노드에 방문해 보고 싶을 때 나머지 모든 노드와의 관계를 확인해야 해서 적은 수의 간선을 가지는 희소 행렬에는 효율이 좋지 않다. 그리고 항상 n^2의 메모리 공간이 필요해 메모리를 많이 사용한다.

장점: 인접 행렬에 비해 메모리를 적게 차지한다. 연결된 노드를 확인하려면 포인터로 바로 접근이 가능해 효율적이다.
단점: 노드 i와 노드 j가 연결되었는지 확인하고 싶을 때 직접 해당 노드까지 이동해보면서 확인해야 해 접근 속도가 느리다.

25. AVL 트리 만드는 방법 4가지

참고

26. 이중 연결 리스트란?

이중 연결 리스트의 요소들은 이전 값과 다음 값을 가리키는 포인터를 가지고 있다. 그래서 노드를 양방향으로 탐색할 수 있고, 탐색 시 O(n/2)만큼의 시간복잡도를 가진다. 리스트를 절반으로 나눠서 앞 부분은 첫번째 노드부터, 뒷 부분은 마지막 노드부터 거꾸로 탐색할 수 있기 때문이다. 일반 연결 리스트보다 효율적으로 queue를 구현할 수 있다. 변수를 하나 더 사용해야 해서 메모리를 더 많이 사용한다는 단점이 있지만 장점이 더 크다.

27. 1부터 100까지 정렬한다면 어떤 정렬 알고리즘을 써야 할까?

Counting Sort 를 이용한다. 만약 숫자의 범위가 크다면 radixsort가 좋을 수도 있다.