CS 정리 [자료구조]

유용한 모든 것

CS 정리 [자료구조]

뭉지(moonz) 2022. 4. 13. 11:15

해당 포스팅은 "기출로 대비하는 개발자 전공면접 [CS 완전정복]"을 수강하며 정리하였습니다.

기술면접에 대비하기 위해 많은 내용을 담지 않은 "질문과 작성" 틀을 갖춘 내용으로 작성할 예정입니다

다음과 같은 순서로 작성합니다.
🟥 질문
keyword
🚀 답변 (모든 답변은 더보기를 누르면 확인할 수 있습니다.)
🔏 추천

자료구조

🟥 Array는 어떤 자료구조인지 설명해주세요.

keyword
✔️ 메모리에 순차적인 데이터 저장
✔️ 고정된 저장 공간

🚀

Array는 "고정된 저장공간으로 할당"하여, 연관된 data를 메모리 상에 "순차적으로 저장"하는 자료구조입니다.

장점

Array는 index 기능을 이용하므로 조회와 마지막 인덱스에 데이터 추가하는 것이 빠릅니다.

단점

고정된 크기라는 배열의 특성 상, 선언 시에 Array의 크기를 미리 정해야한다는 것입니다.

이로인해 메모리 낭비나 추가적인 overhead가 발생할 수 있습니다.

🔏 추가 질문을 대비하여 LinkedList와 비교되는 특성들을 위주로 대답하는 것이 좋습니다.

🟥 LinkedList와 Array의 차이점은 무엇인지 설명해주세요.

keyword
✔️ 메모리 구조
✔️ operation의 시간 복잡도(Time Complexity, 연산 속도)

🚀

두 자료구조의 주 차이점은 메모리 구조입니다.

Array는 메모리 상에서 연속적으로 데이터를 저장하는 자료구조이고, Linked List는 메모리 상에서는 연속적이지 않지만, 각 Node가 다음 Node의 메모리 주소값을 갖고있음으로써 논리적 연속성을 유지하는 자료구조입니다.

그래서 각 Operation의 시간복잡도가 다릅니다.

데이터 조회 시, Array는 index를 이용하기 때문에 O(1), LinkedList는 O(n)의 시간복잡도를 갖습니다.

중간에 데이터 삽입/삭제 시 Array는 O(n), LinkedList는 O(1)의 시간복잡도를 갖습니다.

얼만큼의 데이터를 저장할 지 미리 알고있고, 조회를 자주 하는 경우 Array 자료구조를 많이 사용합니다.

반면 몇개의 데이터를 저장할지 불확실하고, 삽입/삭제가 잦은 경우 LinkedList 자료구조를 사용하는 것이 유리합니다.

시간복잡도?

특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 의미합니다.

특정 알고리즘이 수행되는데 걸리는 시간 중에서 가장 최악의 경우를 계산하는 방식을 빅-오(Big-O) 표기법이라 합니다.

빅-오 표기법 종류?

O(1) : 입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘
O(log2n) : 입력 데이터의 크기가 커질수록 처리 시간이 로그(log: 지수 함수의 역함수) 만큼 짧아지는 알고리즘 ex) 데이터: 10배 -> 처리 시간: 2배
- 이진 탐색이 대표적
O(n) : 입력 데이터의 크기에 비례해 처리 시간이 증가하는 알고리즘 ex) 데이터: 10배 -> 처리 시간: 10배
- 1차원 for문
O(nlog2n) : 데이터가 많아질수록 처리시간이 로그(log) 배만큼 더 늘어나는 알고리즘 ex) 데이터: 10배 -> 처리 시간: 약 20배
- 정렬 알고리즘 중 병합 정렬, 퀵 정렬이 대표적
O(n^2) : 데이터가 많아질수록 처리시간이 급수적으로 늘어나는 알고리즘다. ex) 데이터: 10배 -> 처리 시간: 최대 100배
- 이중 루프(n² matrix)가 대표적
O(2^n) : 데이터량이 많아질수록 처리시간이 기하급수적으로 늘어나는 알고리즘
- 피보나치 수열이 대표적

🟥 추가 질문 : 미리 예상한 것보다 더 많은 data를 저장하느라 Array의 크기를 넘어서게 됐을 때는 어떻게 해결할 수 있는가?

🚀

기존의 size보다 더 큰 Array를 선언하여 데이터를 옮겨 할당한 후, 기존 Array는 메모리에서 삭제합니다.

이런 식의 동적으로 배열 크기를 조절하는 자료구조로 Dynamic Array가 있습니다.

또 다른 방법으로, size를 예측하기 어렵다면 Array 대신 LinkedList를 사용하여 데이터가 추가될 때마다 메모리공간을 할당받는 방식을 사용하는 것이 좋습니다.

🟥 Dynamic Array는 어떤 자료구조인지 설명해주세요.

keyword :
✔️ resize

🚀

Array 자료구조는 size가 고정되어 있기 때문에 선언 시에 설정한 size보다 많은 개수의 data를 추가하면 저장할 수 없습니다. 이에 반해 Dynamic Array는 저장공간이 가득 찼을 때 유동적으로 size를 조절하여(resize) 데이터를 저장하는 자료구조입니다.

두가지를 중심으로 알아놓읍시다.

resize하는 방식

1. data를 계속 추가합니다. (추가할 때마다 length를 넘지 않는지 체크합니다.)

2. size가 초과되면 size를 *2배 늘린 새 배열을 선언하고 그곳에 데이터를 모두 옮깁니다.

4. 새 배열을 기존 배열에 덮어 씌웁니다.

5. 추가하려한 데이터를 기존 배열에 추가합니다.

* Doubling

resize의 대표적인 방법입니다.

데이터를 추가(O(1))하다 메모리를 초과하게 되면 기존 배열의 size보다 2배 큰 배열을 선언하여 데이터를 옮기는(O(n)) 방법입니다.

데이터를 추가(append)/삭제(remove)할 때 시간복잡도

맨 뒤에 데이터를 추가/삭제하는 것은 상대적으로 빠른 O(1)이 소요됩니다.
맨 끝이 아닌 곳에 데이터를 추가/삭제할 때 상대적으로 느린 O(n)이 소요됩니다.
- 이유는, 메모리상에서 연속적으로 데이터들이 저장되어 있기 때문에 데이터를 추가/삭제할 때 뒤에 있는 데이터들을 모두 한칸씩 shift해야하기 때문입니다.

🟥 추가 질문 : Dynamic Array를 LinkedList와 비교해서 장단점을 설명해주세요.

keyword : 모두 Array의 장단점과 비슷한 맥락
✔️ 데이터 접근과 할당 Good
✔️ 중간에 데이터 추가/삭제 Bad
✔️ 메모리 공간 낭비

🚀

장점

데이터 접근과 할당이 O(1)로 굉장히 빠릅니다.
맨 뒤에 데이터 추가/삭제하는 것이 O(1)로 빠릅니다.

단점

맨 끝이 아닌 곳에 데이터 추가/삭제가 상대적으로 느린 점 (O(n))의 시간복잡도)
resize를 해야할 때, 예상치 못하게 현저히 낮은 performance가 발생하기 때문에, 필요 이상으로 memory 공간을 할당함에 따라 낭비될 수 있는 메모리 공간이 발생할 수 있다는 점

🟥 Linked List는 어떤 자료구조인지 설명해주세요.

keyword :
✔️ Node
✔️ 물리적인 비연속성, 논리적인 연속성
✔️ 메모리를 효율적으로 사용

🚀

Node라는 구조체로 이루어져있는데, Node는 데이터 값과 다음 Node의 Address로 구성되어있습니다.

Linked List는 물리적인 메모리상에서는 비연속적으로 저장되지만, Node가 다음 Node의 Address를 가지고 있음으로써 논리적으로 연속성을 가진 자료구조입니다.

장점

데이터가 추가되는 시점에 메모리를 할당하기 때문에 메모리를 효율적으로 사용할 수 있다는 점
데이터를 중간에 추가/삭제 시 Node의 Address만 변경하면 되기 때문에 O(1)의 시간복잡도가 소요되는 점

단점

데이터 조회/접근 시 index가 없고, head부터 탐색해야하기 때문에 O(n)의 시간복잡도가 소요되는 점

🟥 추가 질문 : 어느 상황에 Array를 쓰는게 LinkedList보다 더 나은가?

keyword :
✔️ 조회에서 효율
✔️ 선언 시 메모리 할당
✔️ 한 데이터의 메모리 효율

🚀

조회 작업을 자주 해야되거나 데이터를 반복문을 통해 빠르게 순회할 때,

Array 선언 당시 데이터의 갯수를 미리 알고 있을 때, 그리고 메모리를 적게 쓰는게 중요한 상황일 때,

Array를 사용하는 것이 더 효율적입니다.

🟥 추가 질문 : Array와 LinkedList의 Memory allocation은 언제 일어나며, 메모리의 어느 영역에 할당되나요?

🚀

Array는 컴파일 단계에서부터 메모리 할당이 발생하여 스택 메모리 영역에 할당됩니다. (정적 메모리 할당)

LinkedList는 런타임 단계에서 새로운 Node가 추가될 때마다 메모리 할당이 발생하기 때문에 Heap 메모리 영역에 할당됩니다. (동적 메모리 할당)

🟥 queue는 어떤 자료구조인지 설명해주세요.

🚀

Queue는 선입 선출 FIFO (First In First Out) 방식의 자료구조로,

큐에서 enqueue는 맨 뒤에 데이터를 추가하므로, 시간복잡도 O(1)이고,

dequeue도 맨 앞에서 데이터를 삭제하므로 O(1)의 시간복잡도입니다.

Array와 List로 구현이 가능합니다.

활용 예) Cache 구현, 하나의 자원을 공유하는 프린터, CPU task scheduling, 너비우선 탐색(BFS) 알고리즘

🔏 면접에서 간단한 질문으로 종종 나오는 문제

FIFO 자료구조임을 기억하고, 활용 예시들, Circular Queue 자료구조를 알아두면 좋습니다.

추가 정리

- enqueue : queue에서 데이터를 추가하는 작업
- dequeue : queue에서 데이터를 추출하는 작업

구현 방식?
- Array-Based queue :

enqueue&dequeue 과정에서 남는 메모리가 발생하기 때문에 메모리를 효율적으로 사용하기 위해 *Circular Queue 형식으로 구현합니다.
또한 enqueue가 계속 발생하면 fixed size 이상으로 데이터가 들어오면 dynamic array 방식처럼 Array의 size를 확장시켜야 합니다.
- List-Based Queue : LinkedList를 이용해 구현하기 때문에 재할당이나 메모리 낭비의 걱정할 필요 X

*Circular Queue?

Circular Queue에 대한 구현은 github를 참고해주세요. (작성중)

circular queue는 마지막 위치(index)가 첫번째 위치와 연결되어 원을 만드는 형태입니다. (Ring Buffer라고도 불립니다.)

출처 : https://www.geeksforgeeks.org/circular-queue-set-1-introduction-array-implementation/

작성 중에 있습니다.

확장?
양쪽에서 enqueue&dequeue가 가능한 deque (double-ended queue)
시간 순서가 아닌 운선순위가 높은 순서로 dequeue할 수 있는 priority queue

🟥 추가 질문 : Array-Base와 List-Base의 차이점이 무엇인지 설명해주세요.

🚀

두 종류의 자료구조로 queue를 구현했을 시 enqueue, dequeue의 시간복잡도는 O(1)이지만

Array-Base는 최악의 상황(worst-case)에서 resize를 하는 작업으로 인해 급 느려질 수 있고

List-Base는 enqueue할 때마다 메모리 할당이 발생해 전반적인 runtime이 상대적으로 느릴 수 있습니다.

🟥 Stack은 어떤 자료구조인지 설명해주세요.

🚀

Stack은 Last In First Out의 후입선출 자료구조입니다. top 위치에 데이터를 추가/삭제하는 push와 pop 모두 시간복잡도 O(1)입니다.

Stack은 재귀적인 특징이 있어서 프로그램 개발 시 자주 쓰이는 자료구조입니다.

활용 예시로 call stack, 후위 표기법 연산, 괄호 유효성 검사, 웹 브라우저 방문 기록(뒤로가기), 깊이우선탐색 (DFS) 등에 쓰입니다.

🟥 추가 질문 : Stack 두개를 이용해서 Queue를 구현해보세요

🚀

Stack은 LIFO, Queue는 FIFO 방식입니다.

Stack 한개는 instack, 한개는 outstack으로 두면

Queue에 enqueue() 할때는 instack에 push하면 됩니다. ex) 1,2,3,4

Queue에 dequeue() 할 때는 outstack이 비어있다면 instack.pop()한 데이터를 outstack.push()를 통해 데이터를 넣고,

그것을 다시 push하면 반대로 저장이 됩니다. ex) 4,3,2,1

outstack에서 다시 pop하면 LIFO 이므로, 1부터 나와서 1,2,3,4 순으로 추출됩니다.

class Queue {
	private Stack<Integer> instack;
    private Stack<Integer> outstack;
    
	void init() {
    	instack = new Stack<>();
    	outstack = new Stack<>();
    }
    void enqueue(int element) {
    	instack.push(element);
    }
    int dequeue() {
    	if (!outstack.isEmpty()) {
        	outstack.push(instack.pop());
        }
        return stack.pop();
    }
}

시간복잡도

enqueue() : instack.push() 한번 진행하므로 O(1)

dequeue() :

1. outstack이 비어있는 경우(최악) : instack에 있는 데이터 n개를 pop() 후 데이터 n개를 outstack.push() 해야합니다. 총 2*n번 operation이 실행되므로 O(n)

2. outstack이 비어있지 않은 경우 : outstack.pop()만 하면 되므로 O(1)

🟥 추가 질문 : Queue 두개를 이용해서 Stack을 구현해보세요.

🚀

Queue 2개 q1, q2를 이용하는데,

Stack의 push(data) : q1에 offer(dta)합니다.

Stack의 pop() : 1개 크기가 남을 때 까지 q1에서 poll()한 데이터를 q2에 offer(data)합니다. 남은 데이터 1개를 poll()하면, 그값을 Stack에서 pop()한 값으로 리턴합니다.

시간복잡도

push() : O(1)이 소요됩니다.

pop() : 데이터를 1개 제외한 n-1개의 데이터를 모두 q1 -> q2로 옮겨야하기 때문에 O(n)이 소요됩니다.

public class Stack_byQueue {
    private Queue<Integer> q1;
    private Queue<Integer> q2;
    public Stack_byQueue() {
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
    }
    void push(int data) {
        q1.offer(data);
    }

    int pop() {
        while (q1.size()>1) {
            q2.offer(q1.poll());
        }
        Queue<Integer> tmp = q1;
        q1 = q2;
        q2 = tmp;
        return q2.poll();
    }

    public static void main(String[] args) {
        Stack_byQueue stck = new Stack_byQueue();
        for (int i=1; i<=4; i++) {
            stck.push(i);
        }
        for (int i=0; i<3; i++) {
            System.out.print(stck.pop() + " ");
        }
    }
}

Q. Queue vs priority queue를 비교하여 설명해 주세요

참고

https://coding-factory.tistory.com/608

저작자표시