신입 개발자 기술면접 예상 질문 정리 - 자료구조(1)

1. 연결 리스트에서 값을 찾는데 시간 복잡도가 얼마나 걸리는가? 더 개선된 구조가 있는지? 단점은?

연결 리스트에서 값을 찾는 시간 복잡도는 O(n)입니다. 이는 리스트를 처음부터 순회해야 하기 때문입니다.
개선된 구조로는 해시 테이블을 사용할 수 있으며, 평균적으로 O(1)의 시간 복잡도로 값을 찾을 수 있습니다.
그러나 해시 테이블은 메모리 사용량이 많고 해시 충돌 문제가 발생할 수 있다는 단점이 있습니다. 또한, 이중 연결 리스트나 트리를 사용하여 검색 성능을 개선할 수 있지만, 이 경우 구현의 복잡성이 증가합니다.

O(n)의 시간 복잡도가 걸립니다. 뒤쪽 원소도 빠르게 검색할 수 있는 Doubly Linked List 구조도 있으며, 이는 저장 공간이 더 필요하다는 단점이 있습니다. 그 외에 Circular Linked List 등도 있습니다. 연결 리스트를 수도 코드로 간단하게 구현할 줄도 알면 좋습니다.

수도코드 (한글버전)
1. 데이터와 다음 데이터의 값을 가진 노드를 생성한다.
　 1-1. 새 노드 생성시 다음값으로 null로 가리킨다.
　 1-2. 새 링크드 리스트 생성시 객체를 생성한다.

2. 링크드 리스트에 맞는 메소드함수를 구현한다.
　 2-1. append(data) :
　 　 2-1-1. 헤드가 없으면 헤드 노드를 생성하고 null을 가리킨다.
　 　 2-1-2. 만약 헤드가 null을 가리키면, 헤드가 새로 생성된 데이터를 가리키게 한다.
　 　 2-1-3. 만약 헤드가 다음 데이터를 가르키고 있으면 그 다음 데이터가 새로운 데이터를 가리키게 하고 데이터를 추가한다.
　 2-2. removeAt(location) : 데이터의 위치에 따라 데이터를 삭제한다.
　 　 2-2-1. 삭제하고자 하는 데이터의 이전 데이터가 삭제하고자 하는 데이터의 다음 데이터를 가리키게 하고 삭제할 데이터는 null을 가리키게 한다.
　 　 2-2-2. 만약 리스트의 첫번째를 삭제하려면 헤드를 다음 데이터로 바꾸고 삭제할 데이터를 삭제한다.
　 2-3. indexOf(data) : 데이터를 순서대로 따라가면서 인덱스를 더해준다. 일치하는 데이터를 찾으면 인덱스를 반환한다.
　 2-4. remove(data) : 데이터 값을 기준으로 삭제를 원할 때 인덱스의 값을 찾아 일치하는 값을 removeAt(index)로 삭제한다.
　 2-5. insert(location, data) : 원하는 위치에 데이터를 추가할 때 인덱스 값을 기준으로 위치를 찾고 데이터를 추가한다.
　 2-6. isEmpty() : 자료의 수가 0 이상이면 false를 반환한다.
　 2-7. length() : 리스트내 전체 자료의 수를 반환한다.

2. 스택 2개를 활용해서 Queue처럼 작동하는 클래스를 만들어보세요.

스택 2개를 사용하여 Queue의 FIFO(First In First Out) 기능을 구현할 수 있습니다.
하나의 스택은 데이터를 삽입할 때 사용하고, 다른 스택은 데이터를 제거할 때 사용합니다. 삽입할 때는 첫 번째 스택에 데이터를 추가하고, 제거할 때는 두 번째 스택에 요소가 없을 경우 첫 번째 스택의 모든 요소를 두 번째 스택에 옮겨줍니다. 이로써 큐의 동작을 구현할 수 있습니다.

import java.util.Stack;

public class QueueWithTwoStacks<T> {
    private Stack<T> stack1 = new Stack<>();
    private Stack<T> stack2 = new Stack<>();

    public void enqueue(T item) {
        stack1.push(item);
    }

    public T dequeue() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.isEmpty() ? null : stack2.pop();
    }

    public boolean isEmpty() {
        return stack1.isEmpty() && stack2.isEmpty();
    }
}

이 클래스는 enqueue 메서드를 통해 요소를 추가하고 dequeue 메서드를 통해 요소를 제거하며, isEmpty 메서드를 통해 큐가 비어 있는지를 확인합니다. 두 스택을 사용함으로써 큐의 FIFO 동작을 구현할 수 있습니다.

예를 들어 1 2 3 4를 큐에 넣으면 순서대로 1 2 3 4가 나옵니다. 이를 선입선출이라고 합니다. 하지만 스택은 1 2 3 4를 넣으면, 4 3 2 1이 나옵니다. 스택은 큐와 다르게 선입후출의 구조입니다. 하지만, 스택 2개를 활용하는 경우. 2번째 스택에 아무것도 없는 상태에서 pop를 수행한다면 첫 번째 스택에 쌓여있는 값을 2번째 스택으로 이관시킬 수 있습니다.

관련하여 잘 정리된 블로그 글 함께 첨부합니다. https://limkydev.tistory.com/185

3. ArrayList의 크기(size)가 어떻게 변하는지 설명해 보세요.

ArrayList는 동적 배열로, 요소를 추가할 때 현재 용량(capacity)이 부족하면 자동으로 크기를 증가시킵니다. 초기 용량이 설정되어 있지만, 요소가 추가되면서 용량이 부족해지면 ArrayList는 새로운 배열을 생성하고 기존 배열의 요소를 복사하여 저장합니다.
일반적으로 ArrayList의 크기는 용량이 초과될 때마다 1.5배에서 2배로 증가합니다. 이는 내부적으로 `ensureCapacity()` 메서드를 통해 관리되며, 추가적인 메모리 할당과 복사 작업이 발생합니다. 이러한 방식으로 ArrayList는 효율적으로 크기를 조정하며 동적으로 요소를 관리합니다.

A4. 자바 버전마다 그 구현 방식이 다를 수 있지만, 기본적인 틀은 최초 ArrayList 내부에 특정 크기의 배열이 생성된 다음 용량이 가득 찰 때마다 일정 비율로 늘려간다고 알고 있습니다. 자바 8 버전 이상을 기준으로 했을 때 크기를 지정하지 않으면 최초 10 크기의 배열이 생성되고, 용량이 가득 찰 때마다 1.5배씩 늘어나는 것으로 기억합니다.

해설)
면접자가 항상 정확한 답을 알고 있기를 바라면서 질문하는 것은 아닙니다. ArrayList의 최초 크기가 10이고, 1.5배씩 늘어난다라는 숫자를 외우길 바라는 것이 아니라는 말입니다(물론 ArrayList의 경우 면접에서 상당히 자주 등장하는 주제이므로 자연스럽게 기억하게 될 것입니다). 질문의 목적은 합리적으로 추론하는 능력을 가지고 있는지를 확인해 보려는 것입니다. 만약 면접자가 ArrayList의 크기가 어떻게 변하는지를 모른다고 가정하고 추론해 보겠습니다.

ArrayList는 Array와 List를 합친 이름이죠. 인터페이스가 List이고 내부 구현은 배열 형태라는 느낌을 줍니다. 그렇다면 내부에 배열을 가지고 있을 것이고, 배열은 생성할 때 그 크기를 지정해 줘야 하겠죠? 그럼 이 배열의 최초 용량이 가득 찼다면 다음 배열의 크기는 새롭게 어느 정도로 생성해 줘야 할까요? 단순히 1만큼 큰 배열을 생성하면 용량이 금방 다시 차므로 새로운 배열을 또 생성해야 할 것입니다. 그렇다고 무작정 엄청 큰 배열을 생성하는 것은 메모리 낭비로 이어질 수 있습니다. 따라서 현재 배열의 크기에 비례하여 적당한 크기의 새로운 배열을 생성해야 한다는 결론이 나옵니다.

혹은 면접관이 면접자가 자바 API에 관한 문서나 구현 방식을 살펴보는 습관을 가졌는지를 판단하려고 할 수도 있습니다. 훌륭한 면접자라면 합리적으로 추론하고, 자주 사용하는 라이브러리의 구현에 관심을 가지는 것도 중요합니다.

⭐참고자료

 

1) 한빛출판네트워크, "백엔드 기술 면접 TIP: 자바 기본 문법 예상 질문 5가지와 해설", 2024.02.08, https://www.hanbit.co.kr/channel/category/category_view.html?cms_code=CMS1626582373&cate_cd=

2) 제로베이스, "현직자가 말하는 신입 백엔드 개발 면접 질문 ｜ 백엔드 스쿨", https://zero-base.co.kr/event/media_BE_school_qna

3) 스파르타코딩클럽, "2024 백엔드 면접 질문 문제은행 - 개발자 면접 준비 101", 2024.08.22, https://spartacodingclub.kr/blog/2024-backend-jobinterview-question

https://hoons-dev.tistory.com/95

이 글은 참고자료를 바탕으로 각 질문에 대한 답변을 정리한 것으로, 틀린 부분이 있을 수도 있습니다.