[면접총정리] 신입 개발자 인터뷰 대비 총정리 자료 - ① 자료구조

 

🧑🏻‍💻 글을 시작하기에 앞서..

- 신입 개발자 인터뷰에서 자주 나오는 질문을 모아 한 번에 정리한 포스트입니다.
- 신입 개발자 기술면접을 준비하는 사람으로, 정확하지 않은 정보가 포함될 수 있습니다. 더 올바른 답을 알고 있다면 댓글로 남겨주시면 반영하도록 하겠습니다.
- 필자는 Java 기반의 백엔드 엔지니어를 목표로 하고 있습니다. 따라서 글 내부에 Java 혹은 백엔드 관련 용어가 나올 수 있습니다. Java를 사용하지 않는다면, 자신의 직무 언어 및 프레임워크 관점에서 문제를 해결해보는 것을 추천합니다.

 

 

🧑🏻‍💻 자료구조 면접 질문

💡  Array와  LinkedList가 각각 무엇인지, 어떻게 다른지 설명해주세요.

Array는 순서가 있는 데이터를 저장하기 위한 선형 자료구조이며, 고정 길이의 크기를 가진 자료구조입니다. 순서가 있기 때문에 각 데이터의 순서를 의미하는 Index가 존재하며, Index를 통해 해당 데이터에 접근하는 Random Access를 지원합니다. Index를 통해 값을 색인하면 O(1)의 시간복잡도가 소요됩니다.

하지만, 중간에 값을 삽입 혹은 삭제에 대해선, 뒤의 요소들을 모두 한 칸씩 밀거나 당겨야 하므로 Worst Case의 경우 O(N)의 시간복잡도를 갖습니다.

 

고정길이, 느린 삽입 삭제 연산을 해결하기 위해서 나온 자료구조가 바로 LinkedList 입니다.

데이터를 저장하고 있는 각 노드를 서로 연결 시켜 만든 선형 자료구조로, 가변 길이의 크기를 가지고 있습니다.

중간에 값을 삽입하는 과정에서 기존의 연결을 끊고, 새로운 연결을 맺는 과정만 하면 되므로 O(1)의 시간 복잡도, 삭제하는 과정에서도 기존의 연결을 끊고 그 뒤의 노드와 연결하는 O(1)의 시간복잡도를 갖습니다.

반면 특정 값을 찾는 과정은 연결리스트 내부를 모두 완전탐색해야 하므로 worst case의 경우 O(N)인 단점이 존재합니다.

 

2022.10.23 - [🧪 컴퓨터과학 : CS] - [자료구조] Array와 LinkedList의 차이 (인터뷰 대비)

[자료구조] Array와 LinkedList의 차이 (인터뷰 대비)

 

 

💡  LinkedList를 손코딩으로 구현할 수 있나요?

class ListNode{
    private String data;
    public ListNode next;
    
    public ListNode(String data) {
        this.data = data;
        this.next = null;
    }

    public String getData() {
        return this.data;
    }
}

public class LinkedList {

    private ListNode head;

    public LinkedList() {
        head = null;
    }

    public void insertNode(ListNode preNode, String data) {
        ListNode newNode = new ListNode(data);
        newNode.next = preNode.next;
        preNode.next = newNode;
    }
    
    public void insertNode(String data) {
        ListNode newNode = new ListNode(data);
        if(head == null) {
            this.head = newNode;
        } else {
            ListNode tempNode = head;
            while(tempNode.next != null) {
                tempNode = tempNode.next;
            }
            tempNode.next = newNode;
        }
    }

    public void deleteNode(String data) {
        ListNode preNode = head;
        ListNode tempNode = head.next;
        
        if(data.equals( preNode.getData() )) {
            head = preNode.next;
            preNode.next = null;
        } else {
            while(tempNode != null) {
                if(data.equals( tempNode.getData() )) {
                    if(tempNode.next == null) {
                        preNode.next = null;
                    } else {
                        preNode.next = tempNode.next;
                        tempNode.next = null;
                    }
                    break;
                } else {
                    preNode = tempNode;
                    tempNode = tempNode.next;
                }
            }
        }
    }

    public void deleteNode() {
        ListNode preNode;
        ListNode tempNode;

        if(head == null) {
            return;
        }

        if(head.next == null) {
            head = null;
        } else {
            preNode = head;
            tempNode = head.next;

            while(tempNode.next != null) {
                preNode = tempNode;
                tempNode = tempNode.next;
            }
            preNode.next = null;
        }
    }

    public ListNode searchNode(String data) {
        ListNode tempNode = this.head;
        while(tempNode != null) {
            if(data.equals(tempNode.getData())) {
                return tempNode;
            } else {
                tempNode = tempNode.next;
            }
        }
        return tempNode;
    }

}

 

 

💡  Stack과 Queue에 대해 설명하고, 각각 어디에 사용되었는지 설명해주세요.

스택은, 선입후출의 특성을 가진 자료구조입니다. 스택을 구현하기 위해서는 배열 / 연결리스트 사용이 가능하며, 주로 배열을 통해 구현합니다. 스택이 실제로 사용되는 부분은 브라우저의 '뒤로가기' 기능이나, 메모리 영역의 스택 영역에 사용됩니다.

 

큐는, 선입선출의 특성을 가진 자료구조입니다. 큐를 구현하기 위해서는 배열 / 연결리스트 사용이 가능하며, 주로 연결리스트를 통해 구현합니다. 큐가 실제로 사용되는 부분은 프린터 큐, CPU 스케줄링의 Ready Queue 등에 사용됩니다.

 

2022.10.23 - [🧪 컴퓨터과학 : CS] - [자료구조] Stack과 Queue의 비교 (인터뷰 대비)

[자료구조] Stack과 Queue의 비교 (인터뷰 대비)

 

 

💡  Stack 클래스를 손코딩(직무언어)으로 구현할 수 있나요?

public class Stack {
    int[] array;
    private int top;
    private int size;

    public Stack(int length){
        this.array = new int[length];
        this.size = length;
        this.top = -1;
    }

    public boolean isEmpty(){
        return this.top == -1;
    }

    public boolean isFull(){
        return this.top == size-1;
    }

    public void append(int value){
        if(isFull()){
            System.out.println("stack is full");
            return;
        }
        this.array[++this.top] = value;
    }

    public int pop(){
        if(isEmpty()){
            System.out.println("stack is empty");
            return -1;
        }
        return this.array[this.top--];
    }

    public static void main(String[] args) {
        Stack stack = new Stack(10);

        stack.append(1);
        stack.append(2);
        stack.append(3);

        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
    }
}

 

 

💡  Queue 클래스를 손코딩(직무언어)으로 구현할 수 있나요?

import java.util.LinkedList;

public class Queue {
    private LinkedList<Integer> array;

    public Queue(){
        this.array = new LinkedList<>();
    }

    public void append(Integer value){
        this.array.add(value);
    }

    public Integer popLeft(){
        if(this.array.isEmpty()){
            System.out.println("Queue is empty");
            return -1;
        }
        return this.array.removeLast();
    }

    public static void main(String[] args) {
        Queue queue = new Queue();

        queue.append(1);
        queue.append(2);

        System.out.println(queue.popLeft());
        System.out.println(queue.popLeft());
        System.out.println(queue.popLeft());
    }
}

 

 

💡  Priority Queue가 무엇이고, 어떻게 구현할 수 있는지 설명할 수 있나요?

선입선출의 구조를 가진 큐와 다르게, 우선순위가 높은 원소가 우선적으로 빠져나오게 되는 자료구조입니다.

우선순위 큐는 배열, 연결리스트, Heap으로 구현할 수 있으며, 일반적인 경우에는 삽입과 삭제 연산이 모두 O(logN)이 보장된 Heap 자료구조를 사용해서 우선순위 큐를 구현합니다.

 

2022.10.23 - [🧪 컴퓨터과학 : CS] - [자료구조] Priority Queue (우선순위 큐) 인터뷰 대비

[자료구조] Priority Queue (우선순위 큐) 인터뷰 대비

 

 

💡  그렇다면, Heap이 무엇인지 , 삽입 및 삭제시 어떻게 동작하는지 설명할 수 있나요?

힙(Heap)은 '완전이진트리'면서, 모든 부모노드와 자식노드 간에 '크거나 같은' 혹은 '작거나 같은'의 관계를 가지고 있는 트리를 의미합니다.

 

이진트리는 자식노드를 최대 2개까지 가질 수 있는 트리를 의미하며, 완전이진트리는 리프노드 레벨을 제외한 나머지 트리는 포화 이진트리의 구조를 갖고, 리프노드 레벨의 노드들은 왼쪽 인덱스부터 차례로 채워진 트리를 의미합니다.

포화 이진 트리는 리프노드들을 제외한 나머지 노드들은 모두 자식을 2개를 가지며, 리프노드들은 자식을 갖지 않는 트리를 의미합니다.

 

삽입 및 삭제를 하면 Heap의 구조가 무너지게 되는데, 다시 Heap으로 만드는 과정을 Heapify라고 합니다.

삽입 시 트리의 가장 마지막 노드 다음 인덱스에 새로운 노드를 집어넣고 Heapify 연산을 통해 힙으로 구성합니다.

삭제 시 트리의 루트노드를 반환 및 제거하고, 트리의 가장 마지막 인덱스를 가진 노드의 위 치를 리프노드로 이동시킵니다. 그 후 Heapfiy 연산을 통해 다시 힙으로 구성합니다.

삽입과 삭제 연산 모두 트리의 높이에 따라 연산횟수가 결정되며, worst case의 시간 복잡도는 둘 다 O(logN)을 보장합니다.

 

2022.10.23 - [🧪 컴퓨터과학 : CS] - [자료구조] Priority Queue (우선순위 큐) 인터뷰 대비

[자료구조] Priority Queue (우선순위 큐) 인터뷰 대비

 

 

 

💡  해시 테이블(Hash Table)에 대해서 설명할 수 있나요?

해시 테이블은 Key-Value 쌍으로 값을 저장하는 자료구조로, 검색 시간 복잡도로 Θ(1)를 갖고 있는 것이 특징입니다.

해시 테이블에 접근할 수 있는 Key와, Key와 매핑되어 있는 Value로 저장되어 있는 것이 특징입니다.

 

 

💡  해시 테이블(Hash Table)의 검색 시간 복잡도는 어떻게 O(1)을 유지할 수 있나요?

해시 테이블에 Key로 접근하면, Hash Function에 Key 값을 집어 넣어 나온 Hash 값을 저장소의 인덱스로 활용합니다. 해당 인덱스에 값을 저장하기 때문에, Hash Function의 시간 복잡도를 제외하면 시간 복잡도 O(1)을 보장할 수 있습니다.

 

 

💡 그렇다면 Hash Collision (해시 충돌)에 대해 설명할 수 있나요? 해결 방법은 어떻게 되나요?

해시 테이블에 접근하는 Key 값은 무한하고, Hash Function을 통해 나온 Hash 값은 유한합니다. (값이 저장되는 메모리는 한계가 있으므로.)

 

비둘기집의 원리는 N+1마리의 비둘기가 N개의 비둘기 집에 들어간다면, 반드시 하나의 비둘기 집에는 두 마리 이상의 비둘기가 들어가 있다는 것입니다.

해시 테이블의 Key는 비둘기고, Hash 인덱스가 비둘기 집이라고 했을 때, Key는 무한하고 Hash 는 유한하므로 특정 Hash Index에 대해서 겹치는 Key가 존재할 수 밖에 없습니다.

이렇게 서로 다른 Key에 대해 같은 해시값을 갖는 경우를 해시 충돌이라고 합니다.

 

해결 방법은, Chaining 방식과 Open Addressing 방식이 있습니다.

• 체이닝(Chaining) : 인덱스의 버킷을 연결리스트로 구현해, 이미 값이 존재하더라도 연결리스트에 해당 값을 삽입하는 방식
• 개방주소법(Open Addressing) : 해시 충돌이 일어난 경우, 특정한 간격만큼 이동 후 비어있는 주소 값에 저장하는 방식

 

 

💡 그렇다면, 체이닝 방식과 개방주소법의 장단점을 비교해주세요.

체이닝 방식 : 

장점 :
1) 한정된 저장소(Bucket)을 효율적으로 사용할 수 있다.
2) 해시 함수(Hash Function)을 선택하는 중요성이 상대적으로 적다.
3) 상대적으로 적은 메모리를 사용한다. 미리 공간을 잡아 놓을 필요가 없다.

단점 :
1) 한 Hash에 자료들이 계속 연결된다면(쏠림 현상) 검색 효율을 낮출 수 있다.
2) 외부 저장 공간을 사용한다.
3) 외부 저장 공간 작업을 추가로 해야 한다.

 

개방주소법 방식 : 

장점 :
1) 또 다른 저장공간 없이 해시테이블 내에서 데이터 저장 및 처리가 가능하다.
2) 또 다른 저장공간에서의 추가적인 작업이 없다.

단점 :
1) 해시 함수(Hash Function)의 성능에 전체 해시테이블의 성능이 좌지우지된다.
2) 데이터의 길이가 늘어나면 그에 해당하는 저장소를 마련해 두어야 한다.

 

 

💡 해시  테이블의 단점은 무엇이 있을까요? 언제 사용하면 안 될까요?

업데이트 예정

 

 

 

💡  BST (Binary Search Tree)와 BST의 특징에 대해 설명할 수 있나요?

데이터의 빠른 검색을 위해 만들어진 트리 자료구조입니다.

아래와 같은 조건을 만족하는 트리에 대해 BST라고 부를 수 있습니다.

• 이진 트리 (자식을 최대 2개까지 가질 수 있는 트리)
• 루트노드에 대해서 왼쪽 자식은 루트 노드보다 더 작은 값을, 오른쪽 자식은 루트 노드보다 더 큰 값을 저장한다.
• 루트노드의 왼쪽 서브트리, 오른쪽 서브트리에 대해 위의 조건을 만족한다.

 

탐색에 유리한 자료구조로, 특정 값에 대해 탐색하는 시간 복잡도가 트리의 높이에 의존하기 때문에 평균적으로 logN의 시간복잡도를 갖습니다.

 

다만, 이진탐색트리의 왼쪽 서브 트리와 오른쪽 서브 트리의 균형이 맞지 않고 한 쪽으로만 치우쳐진 경우에는 트리의 높이 자체가 N이 되므로 Worst Case의 경우 O(N)의 시간복잡도를 갖습니다.

 

 

💡  BST의 성능을 개선하기 위한 방법에는 무엇이 있나요?

위에서 언급했듯이, BST의 양쪽 높이의 균형을 맞추는 것이 성능을 개선하는 방식입니다.

대표적으로 개량된 BST 트리로써, AVL 트리, Red-Black 트리가 있습니다.

 

 

💡  AVL 트리는 무엇인가요?

업데이트 예정

 

 

💡  트리와 그래프의 차이에 대해서 설명할 수 있나요?

그래프는 트리보다 더 포괄적인 개념입니다. 즉, 트리는 그래프라고 부를 수 있으나 모든 그래프를 트리라고 부를 순 없습니다.

그래프는 각 요소를 나타내는 노드와 노드 사이의 관계를 나타내는 엣지로 나타낼 수 있습니다.

트리는 그래프와 동일하나, 사이클이 없는 그래프를 의미하며 계층 구조를 나타낼 때 용이합니다.

 

 

💡  이진트리의 전위 / 중위 / 후위 순회가 무엇인가요? 설명하고, 자신이 직무 언어로 순회 결과를 코딩해보세요.

 

• 루트를 방문하는 작업을 V
• 왼쪽 서브 트리 방문을 L
• 오른쪽 서브트리 방문을 R

 

• 루트를 서브 트리에 앞서서 먼저 방문하면 전위 순회
• 루트를 왼쪽과 오른쪽 서브 트리 중간에 방문하면 중위 순회
• 루트를 서브 트리 방문 후에 방문하면 후위 순회가 됩니다.

 

public class TreeOrder {
    public static void main(String[] args) {
        int[] array = {1, 3, 2, 5, 6, 4, 7, 9, 8};

        Tree tree = new Tree(array);
        tree.preOrder(1);
        System.out.println("");
        tree.inOrder(1);
        System.out.println("");
        tree.postOrder(1);
    }
}


class Tree{
    int[] binaryTree;

    public Tree(int[] array){
        int tree_size = array.length + 1;
        this.binaryTree = new int[tree_size];
        this.binaryTree[0] = 0;
        System.arraycopy(array, 0, binaryTree, 1, tree_size - 1);
    }

    public void preOrder(int idx){
        if(0 > idx | idx >= binaryTree.length){
            return;
        }
        System.out.println(this.binaryTree[idx]);
        this.preOrder(idx*2);
        this.preOrder(idx*2 + 1);
    }

    public void inOrder(int idx){
        if(0 > idx | idx >= binaryTree.length){
            return;
        }
        this.preOrder(idx*2);
        System.out.println(this.binaryTree[idx]);
        this.preOrder(idx*2 + 1);
    }

    public void postOrder(int idx){
        if(0 > idx | idx >= binaryTree.length){
            return;
        }
        this.preOrder(idx*2);
        this.preOrder(idx*2 + 1);
        System.out.println(this.binaryTree[idx]);
    }
}

 

 

💡  + Java의 Collections에 대해서 알고 있나요?

업데이트 예정.

 

 

 

🏃‍♂️ 다른 질문 대비 자료

[📝 신입 인터뷰 준비] - [면접총정리] 신입 개발자 인터뷰 대비 체크리스트 - ⓪ 체크리스트

[📝 신입 인터뷰 준비] - [면접총정리] 신입 개발자 인터뷰 대비 총정리 자료 - ① 자료구조
[📝 신입 인터뷰 준비] - [면접총정리] 신입 개발자 인터뷰 대비 총정리 자료 - ② 알고리즘
[📝 신입 인터뷰 준비] - [면접총정리] 신입 개발자 인터뷰 대비 총정리 자료 - ③ 데이터베이스
[📝 신입 인터뷰 준비] - [면접총정리] 신입 개발자 인터뷰 대비 총정리 자료 - ④ 네트워크
[📝 신입 인터뷰 준비] - [면접총정리] 신입 개발자 인터뷰 대비 총정리 자료 - ⑤ 운영체제
[📝 신입 인터뷰 준비] - [면접총정리] 신입 개발자 인터뷰 대비 총정리 자료 - ⑥ 자바(Java)
[📝 신입 인터뷰 준비] - [면접총정리] 신입 개발자 인터뷰 대비 총정리 자료 - ⑦ 백엔드(Java Spring 기반)
[📝 신입 인터뷰 준비] - [면접총정리] 신입 개발자 인터뷰 대비 총정리 자료 - ⑧ 개발공통 / 인성면접