기출로 대비하는 개발자 면접준비 with 디프만

Array

• 연관된 data를 메모리 상에 연속적이며, 순차적으로 미리 할당된 크기만큼 저장하는 자료구조
• 메모리상에서 각 data의 첫 메모리 주소값이 해당 데이터의 주소값이다.
  • ex: 1이라는 데이터가 0x4af1, 0x4af2, 0x4af3, 0x4af4 와 같이 4바이트를 차지할때 가장 첫 주소값인 0x4af1이 해당 데이터의 메모리 주소값이다.
• 배열은 메모리에 저장될때, 연속적으로 저장된다 → 빈공간을 두지 않는다

Array 특징

• 고정된 저장공간
• 순차적인 데이터 저장

Array 연산의 시간복잡도

• 조회 - O(1)
  • 연속적으로 데이터가 저장되어 있기 때문에 인덱스 값을 알면, 계산을 통해 바로 데이터 조회가 가능
• 마지막 인덱스에 데이터 추가 및 삭제: O(1)
• 데이터 삽입, 삭제: O(n)
  • 중간의 데이터 삽입, 삭제가 발생 시 전,후 데이터의 이동이 발생
• 탐색: O(n)
  • 특정 데이터 값이 어디에 존재하는지 순차 탐색

Array 장단점

• 장점
  • 조회, 삽입, 삭제가 빠르다.
• 단점
  • 배열 선언시 메모리를 고정적으로 할당하기 때문에 메모리 낭비 및 추가적으로 확장 및 축소 시 오버헤드 및 비용이 든다.
    • 따라서 위의 문제를 해결하기 위해 동적 배열(Dynamic Array)를 사용한다.
    • 혹은 LinkedList를 사용하여 데이터 추가 시 메모리를 할당받는 방식을 사용

Dynamic Array

• 기존 Array의 고정된 메모리 공간으로 발생하는 문제를 해결하기 위해
• resize를 통해 유동적으로 배열의 크기를 확장 및 축소시켜 데이터를 저장하는 자료구조

Resize

• 기존 배열의 크기보다 더 많은 데이터가 삽입되면, 크기를 2배 키우는 doubling과 배열의 3/4가 비어있으면 배열의 크기를 1/2로 축소하는 방법이 존재
• 새로운 데이터를 삽입하다가(O(1)) 배열이 꽉차면, 배열을 2배 늘린 배열로 데이터를 복사하고(O(n)), 기존배열을 삭제하고, 새로운 배열에 데이터를 삽입하는 과정으로 이루어짐

분할상환 시간복잡도(Amortized time complexity)

• 일반적으로 배열 삽입시 O(1)을 갖지만, 배열을 resize하는 경우 O(n)을 갖게된다.
• 그렇다면 배열에 데이터 삽입의 시간복잡도는 O(1)일까? O(n)일까?
• 대다수의 작업이 배열에 데이터를 삽입하는 O(1)이고, resize는 가끔 발생하므로 분할상환 시간복잡도가 O(1)이 된다
• 즉, resize의 시간을 append의 작업들이 분담에서 나눠 가지므로 전체적으로 O(1) 시간이 걸린다.

Dynamic Array와 Linked List의 비교 및 장단

• Dynamic Array의 장점
  • Array의 시간복잡도를 따르기 때문에 Linked List에 비해 조회 및 마지막에 데이터 삽입이 빠르다(O(1))
    • index 접근 연산 = [배열의 첫 주소값] + [offset]
• Dynamic Array의 단점
  • Array와 같이 중간에 데이터 삽입, 삭제가 느림(O(n))
  • resize(O(n))시 예상치 못한 성능 저하가 발생
  • 메모리 공간을 넉넉하게 할당하기 때문에, 사용하지 않는 메모리 공간이 낭비됨

LinkedList

• Node를 이용해 데이터 값과 다음 Node의 주소값을 저장하여, 다음 주소값을 통해 다음 데이터와 연결하는 논리적인 연속성을 가진 자료구조
• 물리적인 메모리상으로는 비연속적으로 저장됨, 하지만 논리적인 연속성을 가짐
• 트리, 그래프와 같은 다른 자료구조 구현시 자주 사용되는 자료구조
• 데이터 추가시 메모리를 할당받으므로 효율적인 메모리 사용이 가능

논리적 연속성

• 각 Node들은 다음 주소값을 가지므로, 논리적 연속성을 유지하고, 연결되어 있다.
• Array는 물리적으로 연속적으로 데이터를 저장했으면, Linked List는 물리적으로 비 연속적으로 저장되어 있다.
• 따라서 메모리 연속성이 필요 없으므로 메모리 사용이 자유롭다
• 그러나, 다음 주소값도 추가로 메모리에 할당해야하므로 기존 Array에 비해 데이터 하나당 메모리 할당양이 많다.

시간복잡도

• 조회: O(n)
  • 물리적 메모리상에 연속적으로 저장된것이 아니기 때문에 인덱스의 산술 연산을 통해 조회(random access)가 불가능하고, 헤드로 부터 순차 탐색을 진행해야한다.
• 탐색: O(n)
• 삽입, 삭제: O(1)
  • Array에서 배열의 각 원소를 Shift한 것과 달리 각 데이터의 다음 주소값 변경을 통해 삽입과 삭제가 이루어진다.

Array와 Linked List의 비교

• Array는 메모리상 물리적인 연속성을 유지하며 저장하는 자료구조이다
• Linked List는 물리적으로는 비연속성이고, 다음 데이터의 주소값을 저장하는 논리적인 연속성을 유지하는 자료구조이다.
• Array는 조회시 O(1), 삽입,삭제시 O(n)의 시간복잡도를 갖는다.
• Linked List는 조회시 O(n), 삽입,삭제시 O(1)을 갖는다.
• 따라서 데이터의 크기, 자주 사용하는 연산의 종류를 미리 알고, 알맞는 자료구조를 이용해야 한다.

조회

• Array는 메모리상 연속 저장으로 인해 인덱스를 통해 즉시 접근이 가능함. O(1)
• Linked List는 메모리상 불 연속적으로 저장되므로 순차 접근이 가능함. O(n)

삽입,삭제

• Array는 맨 마지막 원소의 추가,삭제의 경우 O(1)이지만, 중간 원소의 추가,삭제는 다른 원소들이 shift 되므로 O(n)의 시간복잡도를 갖는다.
• Linked List는 원소 추가,삭제시 Node에서 다음 주소값을 변경해주면 되므로 O(1)이다.
  • 하지만, 추가,삭제를 하려는 index 까지 도달하는데 O(N)이 걸리므로 실질적으로 추가,삭제 시 O(n)이 걸린다고 생각하면 된다

메모리 관점에서의 Array와 Linked List

• Array는 배열 선언시 사이즈를 고정하기 때문에, 메모리 낭비 혹은 메모리 확장에 드는 비용이 발생한다.
• Linked List는 런타임중 배열의 크기를 조절할 수 있고, 배열 선언시 메모리를 초기화하지 않고, 필요한 만큼의 메모리만 할당하여 메모리 낭비가 없다.
  • 그러나 값, 다음 주소값을 저장하므로 Array에 비해 메모리를 더 많이 할당한다

메모리 할당 시점

• Array는 컴파일 단계에서 메모리 할당이 이뤄지는데, 이는 정적 메모리 할당으로 스택메모리 영역에 할당된다
• Linked List는 런타임 단계에 동적으로 할당되고, 이는 동적 메모리 할당으로 힙 메모리 영역에 할당된다.

---

Queue vs Stack

Queue

• 선입선출(FIFO) 자료구조
• 시간복잡도
  • enqueue: O(1)(삽입)
  • dequeue: O(1)(추출)
• 활용 예시
  • Cache구현
  • 프로세스 관리
  • BFS

구현방식

• Array-Based queue: 배열을 통해 큐를 구현하는 것으로, enqueue, dequeue 과정에서 남는 메모리가 생기므로, 메모리 낭비를 줄이고자 Circular queue 형식으로 구현
• List Based queue: Linked List를 이용해서 큐를 구현하는 것으로, 재할당이나 메모리 낭비가 걱정이 없음

확장,활용

• deque: 양쪽에서 enqueue, dequeue 가 가능
• priority queue: 우선순위가 높은 순으로 dequeue가 가능
• 예시: 하나의 자원을 공유하는 프린터, cpu 스케쥴링

Circular queue(원형큐)

• 배열에서 enqueue, dequeue 를 수행하면 할수록 앞에 메모리에는 빈공간이 생겨 낭비가 된다.
• 배열의 처음과 끝이 맞물려서 마지막 인덱스 이후 첫번째 인덱스에 enqueue를 할 수 있다.

Array-Based, List-Based 비교

• Array-Based의 경우는 보통 circular queue로 구현한다.

• 이때 size를 넘어서면 동적 배열과 같은 방법으로 resize가 필요하다.

• 시간복잡도는 enqueue, dequeue시 (amortized)O(1)을 갖는다.

• List Based의 경우 single linked list로 구현한다

• enqueue는 append하는것으로 구현되고, dequeue는 head를 변경하면 되기 때문에 둘다 O(1)을 갖는다.

• 따라서 두 자료구조의 경우 enqueue, dequeue 둘다 O(1)을 갖는다.

• 일반적으로 Array-Based의 경우가 성능이 좋지만, 최악의 경우 resize로 인해 o(n)을 가지므로 더 느릴 수 있다.

• List-Based는 enqueue시 메모리 할당이 필요하므로 런타임이 전반적으로 느릴 수있다.

Stack

• 후입선출(LIFO) 자료구조

• 시간복잡도

  • push: O(1)
  • pop: O(1)

• 활용 사례

  • 후위표기법, DFS

• 시간 순서상 가장 최근에 추가한 데이터가 가장 먼저 나오는 후입선출 형식

• push는 데이터를 추가하는 것으로 맨 뒤에 추가하므로 o(1)을 갖는다.

• pop은 데이터를 삭제하는 것으로 맨 뒤의 데이터를 삭제하므로 o(1)을 갖는다.

Stack 2개로 Queue 구현

• queue의 enqueue를 구현할 때는 첫번째 스택(instack)을 사용하고, dequeue()를 구현할때는 두번째 스택(outstack)을 사용하여 queue를 구현

1. enqueue(): instack에 push()
2. dequeue():
   1. if len(outstack )==0 이면 instack.pop()하고, 그 pop한 값을 outstack.push()를 하여 instack에서 outstack으로 데이터 이동. → instack 하단 데이터= outstack 상단 데이터
   2. outstack.pop()

시간복잡도

• enqueue(): instack.push()는 O(1)
• dequeue()
  • worst case인 outstack이 비어있는 경우 instack의 n개의 데이터를 pop. push해야 하므로 n번씩 2번하므로 O(n)
  • outstack이 비어있지 않은 경우에는 pop 만 하면되므로 O(1)
  • 따라서 종합적으로 amortized O(1)을 갖는다

Queue 2개로 Stack 구현

• 2개의 큐에서 1개의 큐에서 마지막 원소만 제외하고 dequeue를 하여 나머지 큐에 enqueue하고, 해당 마지막 원소를 dequeue해서 꺼내는 방식을 반복한다.

1. push(): q1으로 enqueue()를 하여 데이터 저장
2. pop()
   1. q1에 저장된 데이터 개수가 1이하로 남을때 까지 dequeue(), 추출한 데이터는 순서대로 q2에 enqueue()
   2. q1에 남은 하나의 데이터를 dequeue() 해서 가장 최근 저장 데이터 반환(LIFO)
   3. 다음에 진행될 pop()을 a~b처럼 진행하기 위해 이름을 swap

시간복잡도

• push(): enqueue 한번만 하므로 O(1)
• pop(): n개중 n-1개를 다른 큐로 옮기므로 O(n)

Queue VS Priority Queue

• Queue는 시간 순서상 먼저 저장한 데이터가 먼저 나오는 선입선출FIFO의 방식
• Priority Queue는 우선순위가 높은 데이터가 먼저 나오는 방식

시간복잡도

• Queue
  • enqueue, dequeue: O(1)
• Priority Queue
  • push, pop: O(logn)

Heap

• 그 자체로 우선순위큐와 동일함
• 완전 이진트리구조
  • 마지막 레벨 노드를 제외하고 모든 노드에 데이터가 채워진 형태의 트리
  • 레벨에서 가장 왼쪽부터 채워지는 트리
• 각 node에 저장된 값은 child node들에 저장된값보다 크거나 같음(max heap)
  • 즉, root node의 값이 가장 큰값
• 각 node에 저장된 값은 child node들에 저장된값보다 작거나 같음(min heap)
  • 즉, root node의 값이 가장 작은값

Heap 구현

• 트리는 보통 Linked List로 구현하지만, Heap은 array로 구현해야 새로운 node를 힙의 마지막 위치에 추가하기 편하다.
• 구현의 편의를 위해 0번 index는 사용x
• 완전 이진트리 특성으로 index를 통해부모자식관계를 정의
  • parent node = n/2
  • left child node = n*2
  • right child node = n*2+1

Heap에서 push(Max-Heap)

• 제일 마지막 인덱스에 값을 저장한다
• 부모노드와 비교하여 값이 더 크면 부모노드와 swap
• 위의 방식을 부모노드가 값이 더 큰 경우까지 반복
• 복잡도는 O(log n) 그 이유는 레벨수 만큼만 이동하기 때문에 logn개가 최대

Heap에서 pop(Max-Heap)

• 가장 큰 값(=루트노드)가 pop된다.
• 마지막 인덱스의 값을 루트노드로 옮긴다.
• max heap의 부합조건인 child node 보다 큰지를 확인
  • 작으면 child node중 큰 값이랑 swap
• 위의 과정을 계속 반복
• 복잡도는 O(log n) 그 이유는 레벨수 만큼만 이동하기 때문에 logn개가 최대

---

Hash table & BST

BST

• 이진탐색트리는 정렬된 트리로 어느 노드를 선택하든 해당 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드로 이루어지고, 오른쪽 서브트리는 그 노드보다 큰 값들을 지닌 노드들로 이루어져있다.
• 검색, 저장, 삭제 시간복잡도는 O(logn)이고, 최악의 경우 한쪽으로 치우쳐진 트리일때 O(n)을 갖는다.
• 저장과 동시에 정렬하는 자료구조로 저장시 일정한 규칙에 따라 데이터가 이동됨

조건

• 루트 노드의 값보다 작으면 왼쪽, 크면 오른쪽 서브트리에 존재
• 서브트리도 위의 조건을 따른다

→ 이진 트리는 모든 노드의 child node의 갯수가 2개 이하인 트리

BST가 한쪽을 치우친 경우 해결법

• 자가 균형 이진 탐색 트리(Self-Balancing BST)는 알고리즘으로 이진 트리의 균형이 잘 맞도록 유지하여 높이를 가능한 낮게 유지
• AVL트리와 Red-Black 트리가 존재함
• 자바에서는 hashmap구현시 seperate chaning으로써 Linked List와 Red-Black 트리를 병행하여 저장

Hash Table

• 효율적인 탐색(빠른 탐색)을 위한 자료구조로써 key-value쌍의 데이터를 입력받음
• hash function h에 key값을 입력으로 넣어 얻은 해시값 h(K)를 위치로 지정하여 key-value 쌍으로 저장
• 저장, 삭제, 검색 시간복잡도는 O(1)

Direct-address Table

• 직접 주소화 테이블은 key값으로 k를 갖는 원소는 index k에 저장하는 것
• 불필요한 공간 낭비(예로 key가 큰번호부터 시작하면 그 앞에 빈공간이 남음), 다양한 자료형을 담을 수 없는 문제가 있음(key값으로 스트링을 쓸수 없음)

Hash Table 정리

따라서 Hash Table 이란 (key,value)쌍을 저장하기 위한 방법으로 hash function h를 통해 (key,value)를 index:h(k)에 저장한다. 이때 키 k 값을 갖는 원소의 위치 h(k)에 hash된다. 혹은 h(k)는 키 k의 해시값이다 라고 할 수 있다.

중복되는 key가 존재하면 안된다.

Hash 값 충돌(Collision)

• 서로 다른 Key의 hash 값이 같을 때 충돌을 말함
• 중복 key는 없지만, 중복 hash 값이 발생
• 최대한 중복 hash값이 발생하지 않도록 잘 설계하는 방법이 해결방법
• collision 발생시 seperate chaining, open addressing 등을 활용해야함

시간복잡도, 공간효율성

• 시간복잡도 저장,삭제,검색 모두 O(1)
  • collision 발생시 최악의 경우 O(n)
• 공간효율성은 데이터 저장전 미리 저장공간을 확보해야하기 때문에 비효율적이다

좋은 해쉬 함수의 조건

• 연산이 빠르고
• 해쉬값이 안겹쳐야함

Collision 해결방법

• open addressing
  • Collision 발생시 미리 정한 규칙에 따라 hash table의 빈 slot을 찾음
  • 빈 slot을 찾는 방법으로는 Linear Probing(선형조사법), Quadratic Probing(이차조사법, Double Hashing(이중해시, 중복해시)이 있음
• separate chaining
  • Linked List에 노드 즉, 슬롯을 추가하여 데이터를 저장한다

Open addressing

• Collision 발생시 미리 정한 규칙에 따라 hash table의 빈 slot을 찾음

• 별도로 메모리 할당을 하는 separate chaining에 비해 메모리를 적게 사용함

• 선형조사법

  • 충돌발생한 해시값으로 부터 (+1,+2,+3..)을 하여 빈 공간을 찾는 방식

• 이차조사법

  • 충돌발생한 해시값으로 부터 (+1^2,+2^2,+3^2..)을 하여 빈 공간을 찾는 방식

→ 충돌이 여러번 발생시 여러번 건너 뛰어 빈 Slot을 찾는 방식으로 충돌횟수가 많아지면 특정 영역에 데이터가 밀집되는 클러스터링 현상이 발생하고, 이는 평균 탐색시간이 증가하게 됨

• 이중해싱
  • 선형조사법, 이차조사법은 탐사이동폭(이동하는 폭)이 같아서 클러스터링 문제가 발생함
  • 해당 문제가 발생하지 않도록 2개의 해시함수를 사용하는 이중해싱 방식
  • 하나의 해시함수는 최초 해시값을 얻을 때 사용되고, 나머지 하나는 해시 충돌시 탐사 이동폭을 얻을 때 사용
  • 충돌 키값을 해시함수에 넣어서 새로운 해시값을 얻는 방식을 반복

Seperate chaining

• Linked List 혹은 tree 를 이용하여 collision을 해결함
• 총돌 발생 시 Linked List에 새로 노드(slot)을 추가하여 데이터 저장
  • 즉, 하나의 노드(slot)에 여러 데이터가 존재할 수 있음
• 삽입: 서로 다른 두 key가 같은 해시값을 가지면, Linked List에 노드를 추가하기 때문에 O(1)이다
• 검색: 기본적으로 O(1), 최악의 경우 O(n)
  • 최악의 경우는 n개의 모든 key가 동일한 해기값을 갖게되면, 길이 n의 Linked List가 생기기 때문
• 삭제: 삭제를 위해서는 검색을 먼저하므로 검색의 시간을 따른다.

사실 이번 방학때 자료구조나 면접 준비를 열심히 해봐야겠다고 생각했는데, 운좋게? 디프만에서 지원해주는 인프런 스터디를 참여할 수 있어서 잘 대비할 수 있을 것 같다!

본 글은 디프만, 인프런의 지원으로 운영된 스터디입니다