[기술면접] 자료구조 - 1/2

2023. 5. 16. 14:55ㆍ기술 면접 준비

😎 Array(List)의 가장 큰 특징과 그로 인해 발생하는 장점과 단점에 대해 설명해 주세요.

Array의 가장 큰 특징은 순차적으로 데이터를 저장한다는 점입니다.


데이터에 순서가 있기 때문에 0부터 시작하는 index가 존재하며, index를 사용해 특정 요소를 찾고 조작이 가능하다는 것이 Array의 장점입니다.


순차적으로 존재하는 데이터의 중간에 요소가 삽입되거나 삭제되는 경우 그 뒤의 모든 요소들을 한 칸씩 뒤로 밀거나 당겨줘야 하는 단점도 있습니다.


이러한 이유로 Array는 정보가 자주 삭제되거나 추가되는 데이터를 담기에는 적절치 않습니다.

▶ Array를 적용시키면 좋을 데이터의 예를 들어주세요. Array를 적용하면 좋은 이유, 그리고 Array를 사용하지 않으면 어떻게 되는지 함께 설명해 주세요.

예로는 주식 차트가 있습니다.

주식 차트에 대한 데이터는 요소가 중간에 새롭게 추가되거나 삭제되는 정보가 아니며, 날짜별로 주식 가격이 차례대로 저장되어야 하는 데이터입니다.

 

즉, 순서가 굉장히 중요한 데이터이므로 Array 같이 순서를 보장해 주는 자료구조를 사용하는 것이 좋습니다.

 

Array를 사용하지 않고 순서가 없는 자료 구조를 사용하는 경우에는 날짜별 주식 가격을 확인하기 어려우며 매번 전체 자료를 읽어 들이고 비교해야 하는 번거로움이 발생합니다.

▶ Array와 ArrayList의 차이점에 대해 설명해 주세요.

Array

  • 크기가 고정적이므로 메모리 낭비를 할 수 있으며 크기를 변경하기 어려운 단점
  • 초기화 시 메모리에 할당되어 속도가 빠름
  • 기본 자료형(primitive type)과 객체 형태의 데이터 모두 저장 가능, 배열 내의 데이터에 빠르게 접근할 수 있어 처리 속도가 빠름

ArrayList

  • 크기가 가변적인 동적배열(dynamic array)이고 제네릭(generic)으로 선언되어 있어, 객체 형태의 다양한 데이터를 저장 가능
  • 데이터 추가 및 삭제 시 메모리를 재할당하므로 속도가 느림
  • 내부적으로 객체 배열을 사용하기 때문에 객체의 추가, 삭제, 검색 시 성능적으로 비효율적일 수 있습니다. 

⭐ Array와 LinkedList의 장/단점에 대해 설명해 주세요.

Array는 인덱스(index)로 해당 원소(element)에 접근할 수 있어 찾고자 하는 원소의 인덱스 값을 알고 있으면 O(1)에 해당 원소로 접근할 수 있습니다. 즉, RandomAccess가 가능해 속도가 빠르다는 장점이 있습니다.
하지만 삽입 또는 삭제의 과정에서 각 원소들을 shift 해줘야 하는 비용이 생겨 이 경우 시간 복잡도는 O(n)이 된다는 단점이 있습니다.

이 문제점을 해결하기 위한 자료구조가 linkedlist입니다. 각각의 원소들은 자기 자신 다음에 어떤 원소인지만을 기억하고 있기 때문에 이 부분만 다른 값으로 바꿔주면 삽입과 삭제를 O(1)로 해결할 수 있습니다.
하지만 LinkedList는 원하는 위치에 한 번에 접근할 수 없다는 단점이 있습니다. 원하는 위치에 삽입을 하고자 하면 원하는 위치를 Search 과정에 있어서 첫 번째 원소부터 다 확인해봐야 합니다. O(n)

Array는 검색이 빠르지만, 삽입, 삭제가 느리다.
LinkedList는 삽입, 삭제가 빠르지만, 검색이 느리다.

▶ LinkedList 사용하는 이유를 말씀해 주세요.

배열은 비슷한 유형의 선형 데이터를 저장하는 데 사용할 수 있지만 제한 사항이 있습니다.

  1. 배열의 크기가 고정되어 있어 미리 요소의 수에 대해 할당을 받아야 함
  2. 새로운 요소를 삽입하는 것은 비용이 많이 듬 (공간을 만들고, 기존 요소 전부 이동)

장점

  1. 동적 크기
  2. 삽입/삭제 용이

단점

  1. 임의로 액세스를 허용할 수 없음. 즉, 첫 번째 노드부터 순차적으로 요소에 액세스 해야 함 (이진 검색 수행 불가능)

😎 스택, 큐, 트리, 힙 구조에 대해 간단히 말씀해 주세요.

Stack과 Queue는 선형 자료구조의 일종이며, Array와 LinkedList로 구현할 수 있습니다.
Stack은

  • 후입선출(LIFO) 방식 즉, 나중에 들어간 원소가 먼저 나오는 구조
  • List로 구현하면 객체를 제거하는 작업이 필요하다. 하지만 Array로 구현하면 삭제할 필요 없이 index를 줄이고 초기화만 하면 되므로, Array로 구현하는 것이 좋다.

Queue는

  • 선입선출(FIFO) 방식 즉, 먼저 들어간 원소가 먼저 나오는 구조를 갖습니다.
  • Array로 구현하면 poll(), dequeue() 이후 객체를 앞당기는 작업이 필요하다. 하지만 List로 구현하면 객체 1개만 제거하면 되므로 삽입 및 삭제가 용이한 LinkedList로 구현하는 것이 좋다.

 

Tree는 스택과 큐와 같은 선형 구조가 아닌 비선형 자료구조이며, 계층적 관계를 표현하기에 적합합니다.
Heap은 최댓값 또는 최솟값을 찾아내는 연산을 쉽게 하기 위해 고안된 구조로,
각 노드의 키값이 자식의 키값보다 작지 않거나(최대힙) 그 자식의 키값보다 크지 않은(최소힙) 완전이진트리입니다.

 

😎 Stack과 Queue의 실사용 예를 들어 간단히 설명해 주세요.

Stack의 예: 자바의 Stack 메모리 영역
지역변수와 매개변수 데이터 값이 저장되는 공간이며, 메서드 호출 시 메모리에 할당되고 종료되면 메모리가 해제되며, LIFO(Last In First Out) 구조를 가집니다.

예

함수의 콜스택, 문자열 역순 출력, 연산자 후위표기법

 

함수

push()

pop()


Queue의 예: OS의 스케쥴러
자원의 할당과 회수를 하는 스케쥴러 역할을 큐가 할 수 있습니다.
메모리에 적재된 다수의 프로세스 중 어떤 프로세스에게 자원을 할당할 것인가 그 순서를 결정하는 것이 자원의 효율적인 사용에 있고, 가장 단순한 형태의 스케쥴링 정책이 선입선 처리(First Com First Served)입니다.

함수

enqueue()

dequeue()

 

큐의 단점 해결 : 원형 큐

  • 큐의 단점: rear가 끝에 도달했을 때, 큐에 빈 메모리가 남아 있어도, 꽉 차있는 것으로 판단할 수도 있음
  • 원형 큐: 논리적으로 배열의 처음과 끝이 연결되어 있는 것으로 간주함

원형 큐의 단점을 개선: 연결리스트 큐

  • 원형 큐 단점: 메모리 공간은 잘 활용하지만, 배열로 구현되어 있기 때문에 큐의 크기가 제한
  • 연결리스트 큐 : 크기가 제한이 없고 삽입, 삭제가 편리

😎 Stack 코드로 구현해 보세요. (자바)

Stack을 구성하는 함수

pop()

push()

peek() : 맨 위 데이터 반환

isEmpty() 

 

import java.util.EmptyStackException;

class Stack<T> {
    class Node<T> {
        private T data;
        private Node<T> next;

        // 생성자
        public Node(T data) {
            this.data = data;
        }
    }

    // 멤버변수 선언 - 스택은 맨위 원소의 주소만 알고 있으면 됨
    private Node<T> top;

    public T pop() {
        if(top == null){
            throw new EmptyStackException();
        }

        // pop하기 전에 그 뒤에있는 요소를 top으로 만들기
        T item = top.data;
        top = top.next;
        return item;
    }

    public void push(T item) {
        Node<T> t = new Node<T>(item); // item을 받아서 Node 생성
        //  top 앞에 노드를 위치시킴
        t.next = top;
        top = t;
    }

    public T peek() {
        if(top == null){
            throw new EmptyStackException();
        }
        return top.data;
    }

    public boolean isEmpty() {
        return top == null;
    }
}

public class StackCode {
    public static void main(String[] args) {
        // 객체 생성
        Stack<Integer> s = new Stack<Integer>();

        s.push(1);
        s.push(2);
        s.push(3);
        s.push(4);

        System.out.println(s.pop()); // 4
        System.out.println(s.pop()); // 3
        System.out.println(s.peek()); // 2
        System.out.println(s.pop()); // 2
        System.out.println(s.isEmpty()); // false
        System.out.println(s.pop()); // 1
        System.out.println(s.isEmpty()); // true

    }
}

 

😎 Queue 코드로 구현해보세요. (자바)

Queue를 구성하는 함수

add(), enqueue() : 맨 끝에 데이터 하나 추가

remove(), dequeue() : 맨 앞에서 데이터 하나 꺼내기

peek()

isEmpty()

 

import java.util.NoSuchElementException;

class Queue<T> {
    class Node<T> {
        private T data;
        private Node<T> next;

        // 생성자
        public Node(T data) {
            this.data = data;
        }
    }

    // 멤버변수 선언 - 큐는 앞뒤로 주소를 알고 있어야 함
    private Node<T> first;
    private Node<T> last;

    public void add (T item) {
        // item을 가지고 Node 생성
        Node<T> t = new Node<T>(item);

        if(last != null){
            last.next = t;
        }
        last = t;
        if(first == null) {
            first = last;
        }
    }

    public T remove() { // T 타입의 데이터를 제거
        if (first == null) {
            last = null;
            throw new NoSuchElementException();
        }

        // 반환하기 전 뒤에 있는 Node를 first로 만들어주기
        // 1. 데이터 백업
        T data = first.data;

        // 2. 다음 노드를 first로 만들기
        first = first.next;
        return data;
    }

    public T peek() {
        if(first == null){
            throw new NoSuchElementException();
        }
        return first.data;
    }

    public boolean isEmpty(){
        return first == null;
    }
}

public class QueueCode {
    public static void main(String[] args) {
        Queue<Integer> q = new Queue<Integer>();
        q.add(1);
        q.add(2);
        q.add(3);
        q.add(4);
        System.out.println(q.remove()); // 1
        System.out.println(q.remove()); // 2
        System.out.println(q.peek()); // 3
        System.out.println(q.remove()); // 3
        System.out.println(q.isEmpty()); // false
        System.out.println(q.remove()); // 4
        System.out.println(q.isEmpty()); // true
    }
}

▶Priority Queue(우선순위 큐)에 대해 설명해 주세요.

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

 

우선순위 큐는 배열, 연결리스트, 힙으로 구현가능한데 힙으로 구현하는 게 가장 효율적입니다. 

힙 → 삽입 : O(logn) , 삭제 : O(logn)

▶ 힙(Heap)에 대해 설명해 주세요.

힙은, 우선순위 큐를 위해 만들어진 자료구조입니다. 완전 이진트리의 일종입니다.

  • 완전이진트리는, 여러 값 중 최댓값과 최솟값을 빠르게 찾아내도록 만들어진 자료구조

반정렬 상태로 힙 트리는 중복된 값 허용합니다. (이진 탐색 트리는 중복값 허용 X)

 

힙 종류

  • 최대 힙
    • 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리
  • 최소 힙
    • 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리

구현

힙을 저장하는 표준적인 자료구조는 배열

구현을 쉽게 하기 위해 배열의 첫 번째 인덱스인 0은 사용되지 않음

특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않음

(ex. 루트 노드(1)의 오른쪽 노드 번호는 항상 3)

 

- 부모노드와 자식노드의 관계

왼쪽 자식 index = (부모 index) * 2
오른쪽 자식 index = (부모 index) * 2 + 1
부모 index = (자식 index) / 2

 

 

 

 

 

 

 

2편에서 이어서 작성하도록 하겠습니다. 

 

 

 

 

출처:

https://gyoogle.dev/blog/algorithm/Bubble%20Sort.html

https://dev-coco.tistory.com/159

https://mangkyu.tistory.com/89

저작자표시 비영리 변경금지

'기술 면접 준비' 카테고리의 다른 글

[기술면접] 알고리즘 - 1/2 (6개 정렬 알고리즘)  (1) 2023.05.22
[기술면접] 자료구조 - 2/2  (1) 2023.05.16
[기술면접] 운영체제 - 2/2  (0) 2023.04.04
[기술면접] 운영체제 - 1/2  (0) 2023.04.04
[운영체제] 교착 상태(데드락, Deadlock) - 5/5  (0) 2023.04.03

관련글

티스토리툴바