[직무 면접 대비] 자료구조 예상 면접 질문
1. 아래 자료구조에 대해 설명해보시오.
Array(배열)
List(리스트)
LinkedList(링크드 리스트)
Stack(스택)
Queue(큐)
Dequeue(디큐)
Tree(트리)
Heap(힙)
Graph(그래프)
Red-Black Tree
레드 블랙 트리
이진 탐색 트리 기반 트리 형식 자료구조.
삽입, 삭제, 검색에 logN의 시간 복잡도 소요.
동일한 노드일 때 깊이를 최소화하여 시간 복잡도를 줄이는 것. 이경우는 트리가 완전 이진트리인 경우.
각 노드는 레드 또는 블랙 색을 갖는다.
루트 노드의 색은 블랙이다.
리프 노드의 색은 블랙이다.
어떤 노드의 색이 레드라면 두 자식 노드의 색은 모두 블랙이다.
루트 노드부터 단말 노드까지의 모든 경로중 최소 경로와 최대 경로의 크기 비율은 2보다 크지 않다. 이러한 상태를 balanced 상태.
노드의 자식이 없을 경우 널 값 저장. 널은 단말 노드로 간주
📌 아래 포스트 참고
[Java] Collection Framework1 - List(ArrayList / Vector / LinkedList)
[Java] Collection Framework2 - Set(HashSet / LinkedHashSet / TreeSet)
[Java] Collection Framework 3 - Map(HashMap / LinkedHashMap / TreeMap / HashTable/ Properties)
[Java] Stack, Queue 클래스
[Java] Graph 그래프 / 인접 행렬 / 인접 리스트
[C & Java] 트리 Tree 1 - 트리? / 이진트리? / 트리 표현법
[Java] 트리 Tree 2 - 이진 트리의 순회(전위, 중위, 후위, 반복, 레벨) / 구현
[Java] 트리 Tree 3 - 이진 탐색 트리
[Java] Red-Black Tree
[C & Java] Heap 힙
[C & Java] 그래프2 - MST / Kruskal / Prim / Dijkstra / Floyd / Topological Sort
2. BFS, DFS란?
DFS 깊이 우선 탐색 (Depth Fisrt Search)
"더 나아갈 길이 보이지 않을 때까지 깊이 들어간다"를 원칙으로 그래프 내의 정점을 방문하는 알고리즘이다.
미로 찾기처럼 그래프의 정점을 타고 깊이 들어가다가 더 이상 방문해왔던 정점 말고는 다른 이웃을 갖고 있지 않은 정점을 만나면
뒤로 돌아와 다른 경로로 뻗어있는 정점을 타고 방문을 재개하는 방식으로 동작한다.
* 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
* 사용하는 경우: 모든 노드를 방문하고자 하는 경우에 이 방법을 선택한다. (완전 탐색 알고리즘에 자주 이용됨)
DFS의 특징
- 자기 자신을 호출하는 순환 알고리즘의 형태
- 트리 순회(전위, 중위, 후위 순회)는 모두 DFS의 한 종류
- 그래프 탐색의 경우 어떤 노드를 방문했었는지의 여부를 반드시 검사해야함(안하면 무한루프 빠질 위험 있음)
📌 DFS 포스트
BFS 너비 우선 탐색(Breadth First Search)
"꼼꼼하게 좌우를 살피며 다니자"와 같이 시작 정점으로부터 가까운 정점을 먼저 방문하고
멀리 떨어져 있는 정점을 나중에 방문하는 알고리즘이다.
시작 정점을 지나고 나면 깊이가 1인 모든 정점을 방문하고, 그다음에는 깊이가 2인 모든 정점을 방문한다.
이런 식으로 한 단계씩 깊이를 더해가며 해당 깊이에 있는 모든 정점들을 방문해 나가다가 나중에는 더 이상 방문할 곳이 없을 때 탐색을 종료한다.
* 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법
* 사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.
BFS의 특징
- BFS는 시작 정점으로부터 거리가 가까운 정점의 순서로 탐색한다. (거리 1부터 2, 3 순서대로)
- 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다. (이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다.)
- BFS는 재귀적으로 동작하지 않는다.
- BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다.
- 즉, 선입선출(FIFO) 원칙으로 탐색
- 일반적으로 큐를 이용해서 반복적 형태로 구현하는 것이 가장 잘 동작한다.
📌 BFS 포스트
3. Queue란? Stack이란?
둘 다 데이터를 저장하는 자료형으로
스택은 후입선출(LIFO) 가장 늦게 넣은 데이터가 가장 먼저 나가는 방식으로 데이터를 저장하고,
큐는 선입선출(FIFO) 가장 먼저 넣은 데이터가 가장 먼저 나가는 방식으로 데이터를 저장한다.
📌 [Java] Stack, Queue 클래스
4. 다이나믹 프로그래밍이란?
알고리즘을 짤 때 분할 정복 기법을 사용하는 경우가 많습니다.
큰 문제를 한 번에 해결하기 힘들 때 작은 여러 개의 문제로 나누어서 푸는 기법인데요.
작은 문제들을 풀다 보면 같은 문제들을 반복해서 푸는 경우가 생깁니다.
그 문제들을 매번 재계산하지 않고 값을 저장해두었다가 재사용하는 기법이 동적 프로그래밍입니다.
*메모이제이션(memoization)
- 메모이제이션(memoization)은 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술이다.
- 메모이제이션은 재귀 호출 시, 반복적으로 계산되는 것들의 계산 횟수를 줄이기 위해 이전에 계산했던 값을 저장해두었다가 나중에 재사용하는 방법입니다. 메모이제이션이 동적 프로그래밍 중 하나입니다.
5. 오버로딩과 오버라이딩의 차이점은?
- 자바에서 다형성을 지원하는 방법입니다.
- 오버 라이딩은 상위 클래스가 가지고 있는 메서드를 하위 클래스가 재정의해서 사용하는 기술입니다. 상속에서 주로 이루어집니다.
- 오버 로딩은 같은 이름의 메서드 여러 개를 가지면서 매개변수의 유형과 개수가 다르도록 하는 기술이고
6. 상속이란?
7. 객체지향 프로그래밍이란? 객체지향 프로그래밍의 3대 특징은?
소프트웨어의 각 요소들을 객체로 만든 후, 객체들을 조립해서 소프트웨어를 개발하는 기법입니다.
- 객체 : 데이터와 이를 처리하기 위한 함수를 묶어 놓은 소프트웨어 모듈
- 클래스 : 공통된 속성과 연산을 갖는 객체의 집합
- 인스턴스 : 클래스에 속한 각각의 객체
- 메시지 : 객체들 간의 상호작용에 사용되는 수단. 객체의 동작이나 연산을 일으키는 외부의 요구사항
특징
캡슐화 / 상속 / 다형성 / 정보은닉 / 추상화
캡슐화
- 외부에서의 접근을 제한하기 위해 인터페이스를 제외한 세부 내용을 은닉하는 것
- 데이터와 함수를 하나로 묶는 것(재사용성 용이, 변경 파급효과 적음)
정보은닉
- 캡슐화의 중요 개념. 캡슐 내의 세부 내용을 외부에 숨기는 것. 자신만의 연산으로 접근 (자바의 접근제어자)
- private : 자기 클래스 내부의 메서드만 접근 허용
- protected : 자기 클래스, 상속받은 자식 클래스에서의 접근을 허용
- public : 모든 접근을 허용
상속
- 상위 클래스의 모든 속성과 연산을 하위 클래스가 물려받는 것
- 재정의 하지 않아도 즉시 자신의 속성으로 사용
다형성
- 하나의 메시지에 대해 각각의 객체가 가지고 있는 고유한 방법으로 응답할 수 있는 능력
- ex) + 연산자
추상화
- 불필요한 부분을 생략하고, 객체의 속성 중 가장 중요한 것에만 중점을 두어 개략화하는 것, 즉 모델화 하는 것이다.
8. 인터페이스와 추상 클래스 각각의 특징과 차이점은?
9. Call by value, call by reference는 각각 무엇인가?
Call by value(값에 의한 호출)는 인자로 받은 값을 복사하여 처리를 한다.
Call by reference(참조에 의한 호출)는 인자로 받은 값의 주소를 참조하여 직접 값에 영향을 준다.
간단히 말해 값을 복사를 하여 처리를 하느냐, 아니면 직접 참조를 하느냐 차이인 것이다.
C++을 예로 든다면 매개변수 그냥 또는 &참조 변수로 주소 값에 접근해 직접 값 변경하느냐 아니냐의 차이
Call by value(값에 의한 호출)
- 장점 : 복사하여 처리하기 때문에 안전하다. 원래의 값이 보존이 된다.
- 단점 : 복사를 하기 때문에 메모리가 사용량이 늘어난다.
Call by reference(참조에 의한 호출)
- 장점 : 복사하지 않고 직접 참조를 하기에 빠르다.
- 단점 : 직접 참조를 하기에 원래 값이 영향을 받는다.(리스크)
10. static의 의미는?
11. garbage collection이란?
프로그램을 개발하다 보면 유효하지 않은 메모리인 가바지(Garbage)가 발생하게 된다.
C언어를 이용하면 free()라는 함수를 통해 직접 메모리를 해제해주어야 한다.
하지만 Java나 Kotlin을 이용해 개발을 하다 보면 개발자가 메모리를 직접 해제해주는 일이 없다.
그 이유는 JVM의 가비지 컬렉터가 불필요한 메모리를 알아서 정리해주기 때문이다.
대신 Java에서 명시적으로 불필요한 데이터를 표현하기 위해서 일반적으로 null을 선언해준다.
가비지를 회수하여 사용할 수 있는 메모리 공간을 늘리는 작업을 가비지 컬렉션이라고 한다.
그리고 이러한 일을 수행하는 것을 가비지 컬렉터라고 한다.
12. 그래프를 정의한다면?
13. 해싱이란?
해싱
해싱은 키 값에 직접 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근한다. 이렇게 키 값의 연산에 의해 직접 접근이 가능한 구조를 해시 테이블(hash table)이라 부르고, 해시 테이블을 이용한 탐색을 해싱(hashing)이라 한다.
출처: https://mattlee.tistory.com/62
해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조이다.
해시 테이블이 빠른 검색 속도를 제공하는 이유는 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문이다.
해시 테이블은 각각의 Key값에 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색하게 된다. 여기서 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다.
출처: https://mangkyu.tistory.com/102
14. priority queue란?
15. 정렬 알고리즘에는 무엇이 있는가? 그중 하나를 구현한다면?
출처: https://butter-shower.tistory.com/184
16. Array와 LinkedList의 차이가 무엇인가요? (N사 전화면접)
Array는 Random Access를 지원한다. 요소들을 인덱스를 통해 직접 접근할 수 있다. 따라서 특정 요소에 접근하는 시간 복잡도는 O(1)이다. 반면 Linkedlist는 Sequential Access를 지원한다. 어떤 요소를 접근할 때 순차적으로 검색하며 찾아야 한다. 따라서 특정 요소에 접근할 때 시간 복잡도는 O(N)이다.
저장 방식도 배열에서 요소들은 인접한 메모리 위치에 연이어 저장된다.
반면 Linkedlist에서는 새로운 요소에 할당된 메모리 위치 주소가 linkedlist의 이전 요소에 저장된다.
배열에서 삽입과 삭제는 O(N)이 소요되지만, Linkedlist에서 삽입과 삭제는 O(1)이 소요된다.
배열에서 메모리는 선언 시 컴파일 타임에 할당이 된다. (정적 메모리 할당)
반면 Linkedlist에서는 새로운 요소가 추가될 때 런타임에 메모리를 할당한다. (동적 메모리 할당)
배열은 Stack 섹션에 메모리 할당이 이루어진다. 반면 Linkedlist는 Heap 섹션에 메모리 할당이 이루어진다.
* LinkedList
ArrayList와 사용 방법은 똑같지만 내부 구조는 정말 다르다.
ArrayList는 내부 배열에 객체를 저장해서 인덱스로 관리하지만, LinkedList는 인접 참조를 링크해서 체인처럼 관리한다.
LinkedList에서 특정 인덱스의 객체를 제거하면 앞뒤 링크만 변경되고 나머지 링크는 변경되지 않는다.
삽입도 마찬가지다.
Array VS LinkedList VS ArrayList 시간 복잡도 및 차이
https://woovictory.github.io/2018/12/27/DataStructure-Diff-of-Array-LinkedList/
[Data Structure] Array vs LinkedList
2019.03.20 일자 기준으로 공부했던 내용을 수정하려고 한다. 이유는 이렇게 정리해놨지만 머리에 기억으로 남지 않기 때문이다.
woovictory.github.io
17. Stack과 Queue의 차이점은 무엇인가요?
스택은 쌓아 올리는 자료구조이다.
같은 구조와 크기의 자료를 정해진 방향으로 쌓을 수 있고, 한 방향으로만 접근할 수 있다.
top을 통해서 push, pop을 하면서 삽입과 삭제가 일어난다. 후입 선출 구조이다.
DFS나 재귀에서 사용된다.
큐는 원소의 줄을 세우는 자료구조이다.
큐는 한쪽 끝에서 삽입 작업을, 다른 쪽 끝에서 삭제 작업을 진행한다.
선입선출 구조이다. 주로 데이터가 입력된 시간 순서대로 처리되어야 하는 경우 사용한다.
BFS나 캐시를 구현할 때 사용한다.
18. BST와 Binary Tree에 대해서 설명하세요.
이진 탐색 트리(Binary Search Tree)는 이진 탐색과 연결 리스트를 결합한 자료구조이다.
이진 탐색의 효율적인 탐색 능력을 유지하면서, 빈번한 자료 입력과 삭제가 가능하다는 장점이 있다.
이진 탐색 트리는 왼쪽 트리의 모든 값이 반드시 부모 노드보다 작아야 하고, 반대로 오른쪽 트리의 모든 값이 부모 노드보다 커야 하는 특징을 가지고 있어야 한다.
이진 탐색 트리의 탐색, 삽입, 삭제의 시간 복잡도는 O(h)이다. 트리의 높이에 영향을 받는데,
트리가 균형이 맞지 않으면 워스트 케이스가 나올 수 있다. 그래서 이 균형을 맞춘 구조가 AVL Tree이다.
19. PriorityQueue의 동작 원리가 어떻게 되나요?
우선순위 큐는 힙이라는 자료구조를 가지고 구현한다.
top이 최대면 최대 힙, top이 최소면 최소 힙으로 표현한다.
힙으로 구현된 이진트리는 모든 정점이 자신의 자식 요소보다 우선순위가 높다는 성질을 가지고 있다.
이 성질을 통해 삽입과 삭제 연산을 모두 O(logN)으로 수행할 수 있다.
20. 해시 테이블(HashTable)에 대해서 설명해주세요.
해시 테이블은 효율적인 탐색을 위한 자료구조로 key값을 value에 대응시킨다.
해시 테이블을 구현하기 위해서는 연결 리스트와 해쉬 함수가 필요하다.
해싱은 임의의 길이의 값을 해쉬 함수를 통해 고정된 크기의 값으로 변환하는 작업을 말하는데, 키 값을 해시 코드로 변환한 후 해당 해시 코드로 배열의 인덱스를 참조하여 값을 찾는다.
충돌이 발생할 수 있으며, 최악의 경우 O(N), 일반적으로 잘 구현된 경우는 O(1)의 시간 복잡도를 가지게 된다.
충돌은 Chaining, Open addressing 등의 방식으로 해결할 수 있다.
해시 테이블은 균형 이진 탐색 트리로도 구현할 수 있다. 이 경우는 탐색 시간이 O(logN)이 된다.
이 방법은 크기가 큰 배열을 미리 할당해 놓지 않아도 되기 때문에 잠재적으로 적은 공간을 사용한다는 장점이 있다.
21. 최소 스패닝 트리(Minimum Spanning Tree)에 대해서 설명해주세요.
그래프 G의 스패닝 트리 중 edge weight 값이 최소인 스패닝 트리를 말한다.
스패닝 트리란 그래프 G의 모든 vertex가 cycle 없이 연결된 형태를 말한다.
n개의 vertex를 가지는 그래프에서 반드시 (n-1) 개의 edge만을 사용해야 하며 사이클이 포함되어서는 안 된다.
Kruskal과 Prim을 통해서 MST를 구현할 수 있다.
Kruskal의 경우 그래프의 간선들을 오름차순으로 정렬하여 가장 낮은 가중치의 간선부터 차례로 MST에 집합체 추가하는 그리디 알고리즘 방식을 사용한다.
Prim의 경우는 시작 정점부터 단계적으로 트리를 확장하는 방법이다.
출처: https://devowen.com/285
22. 자료구조의 정의와 중요한 이유를 설명하세요.
자료 구조란 데이터의 편리한 접근과 조작을 가능하게 하는 데이터를 저장하거나 조직하는 방법입니다.
문맥과 데이터의 종류에 따라 적절한 자료 구조를 사용하는 것은 전체 개발 시스템에 큰 영향을 끼칩니다.
그렇기 때문에 자료구조의 다양한 종류와 각각의 장점과 한계를 잘 이해하고 상황에 맞게 올바른 자료 구조를 선택하고 사용하는 것이 중요합니다.
23. Array(List)의 가장 큰 특징과 그로 인해 발생하는 장점과 단점에 대해 설명하세요.
Array의 가장 큰 특징은 순차적으로 데이터를 저장한다는 점입니다.
이렇게 데이터에 순서가 있기 때문에 0부터 시작하는 index가 존재하며, index를 사용해 특정 요소를 찾고 조작이 가능하다는 것이 Array의 장점입니다.
반면에 이에 따른 단점도 존재하는데, 순차적으로 존재하는 데이터의 중간에 요소가 삽입되거나 삭제되는 경우 그 뒤의 모든 요소들을 한 칸씩 뒤로 밀거나 당겨줘야 하는 단점이 있습니다.
이러한 경우 메모리 상에서 이루어지는 작업이 다른 자료구조에 비해 커지기 때문에 Array는 정보가 자주 삭제되거나 추가되는 데이터를 담기에는 적절치 않습니다.
24. Array를 적용시키면 좋을 데이터의 예를 구체적으로 들어주세요. (ex. 주식 차트) 구체적 예시와 함께 Array를 적용하면 좋은 이유, 그리고 Array를 사용하지 않으면 어떻게 되는지 함께 서술해주세요.
Array를 적용시키면 좋은 예로 주식 차트가 있습니다.
주식 차트에 대한 데이터는 요소가 중간에 새롭게 추가되거나 삭제되는 정보가 아니며, 날짜별로 주식 가격이 차례대로 저장되어야 하는 데이터입니다.
즉, 순서가 굉장히 중요한 데이터 이므로 Array 같이 순서를 보존해주는 자료구조를 사용하는 것이 좋습니다.
이와 같은 데이터에 Array를 사용하지 않는 경우, 즉 순서가 없는 자료 구조를 사용하는 경우에는 날짜별 주식 가격을 확인하기 어려우며 매번 전체 자료를 읽어 들이고 비교해야 하는 번거로움이 발생합니다.
출처: https://velog.io/@ybnr_92/면접-기출-Data-Structure-1.-자료구조-Array