기술 면접에서 나올 수 있는 기본적인 자료구조 예상 질문에 대해서 정리해보았다!
아직 가야 할 길이 멀지만 하나씩 차근차근 정리하다 보면 좋은 결과가 있을거라고 믿는다
큰돌쌤 코테 강의를 보고있어서 자료구조에 대한 내용은 제법 익숙하게 느껴졌다
역시 사람은 배워야하는건가..
자료구조의 정의 및 자료구조가 중요한 이유는?
1
자료구조란 데이터를 저장하고 처리하는 방식을 말하며 자료구조에 따라 데이터의 처리 속도가 달라지기 때문에 상황에 맞는 구조를 사용하는 것이 프로그램의 성능에 있어 중요한 역할을 하기때문에 중요합니다.
Java Collection의 종류는?
1 2 3 4 5 6 7 8 9
List, Set, Map, Stack, Queue등이 있습니다. List는 삽입 순서에 맞게 저장, 중복 가능 Set은 순서와 상관없이 중복저장이 불가능한 자료구조입니다. Map은 Key, Value 형태로 이루어지며 Key의 중복이 불가능합니다. Stack은 후입 선출의 특징을 가지며 Queue는 선입선출의 특징을 가진 자료구조입니다.ArrayList란 어떤 자료구조인가요?
1 2 3
Array리스트는 논리적 저장순서와 물리적 저장 순서가 일치하는 자료구조입니다. 인덱스를 통해 데이터에 접근할 수 있기 때문에 참조에 O(1)의 시간 복잡도를 가집니다. 하지만 데이터를 삽입하거나 삭제하는데에는 다른 데이터의 순서를 모두 옮겨야 하기 때문에 O(N)의 시간 복잡도를 가지게 됩니다.LinkedList는 어떤 자료구조인가요?
1 2 3
LinkedList는 연결리스트라고도 하며, 논리적 저장 순서와 물리적 저장 순서가 일치하지 않는 자료구조입니다. 각 원소들은 데이터와 그 다음 원소의 의 참조 주소를 값으로 가지는 특징이 있습니다, 주소 값을 바꾸는 것만으로 삽입과 삭제가 가능합니다. 원하는 원소에 접근하기 위해서는 처음부터 순회를 시작해야한다는 단점이 있으며 접근, 삽입, 삭제 작업 모두 O(N)의 시간이 소요됩니다.ArrayList와 LinkedList의 차이
1 2 3
ArrayList와 LinkedList는 서로 다른 특징을 가집니다. Array리스트는 각 원소에 인덱스를 부여하여 값을 관리하므로 원소에 접근할 때 O(1)의 시간 복잡도를 가지지만 LinkedList는 원하는 원소에 접근할 때 항상 첫 원소부터 순회해야 하므로 O(n)의 복잡도를 가지게 됩니다. 삽입, 삭제의 경우 O(n)으로 시간 복잡도는 동일하지만 Array리스트는 다른 원소의 위치를 모두 옮겨야 하는 반면 LinkedList는 원소의 주소값만 변경하면 삽입 삭제가 가능하다는 차이가 있습니다.Stack은 어떤 자료구조인가요?
1
stack은 선형 자료구조로 후입 선출(LIFO)의 특징을 가지고 있습니다.
Queue는 어떤 자료구조인가요?
1
큐는 선형 자료구조료, 선입 선출의 특징을 가진 자료구조입니다.
Stack과 Queue의 차이
1
스택과 큐의 가장 큰 차이는 데이터의 사용 순서에 있습니다.
Binary tree에 대해서 설명하세요
1 2 3 4 5 6 7 8 9
이진트리라고도 하며 가장 상위에 루트노드가 오고 그 아래로 자식노드가 2개 이하인 자료 구조를 말합니다. 종류로는 포화 이진트리, 완전 이진트리, 정 이진트리가 있습니다. 포화 이진트리는 모든 노드가 2개의 자식노드를 가지며 빈 노드가 없는 트리를 말하며 완전 이진트리는 왼쪽으로 정렬되어 왼쪽에 빈 노드가 없는 트리를 말합니다. 정 이진트리는 트리의 모든 자식 노드가 0개 또는 2개인 트리를 말합니다.BST(Binary Search Tree)에 대해서 설명하세요
1 2 3
이진 탐색 트리란 이진 트리의 일종으로 데이터를 효율적으로 처리하기 위해 고안된 자료 구조입니다. 이진 탐색 트리의 모든 노드는 유일한 값을 가지며 왼쪽 자식 노드는 부모 노드보다 작은 값이, 오른쪽 자식 노드는 부모 노드보다 큰 값이 오게 됩니다. 접근, 삽입, 삭제 모두 O(logN)의 시간 복잡도를 가집니다Hash Table에 대해서 설명하세요
1 2 3 4 5
해시 테이블은 효율적인 자료 검색을 위해서 만들어진 자료 구조로, Key값을 통해 Value에 접근할 수 있습니다. key값을 Hash code로 변환한 후 hash code를 배열의 인덱스 값으로 변환하여 value를 배열에 저장합니다. 여기서 key를 hash code로 변환하는 알고리즘에 따라 collision(충돌)의 발생 빈도가 달라지기 때문에 효율적인 해시 코드 알고리즘을 설정하는 것이 매우 중요합니다. 빠른 경우 O(1) 최악의 경우 O(n)의 시간 복잡도를 가집니다.BFS란?
1 2 3
너비우선 탐색을 말하며, 트리나 그래프에서 레벨 단위로 위에서부터 아래방향으로 탐색하는 방식을 말합니다. 두 노드 사이의 최단 경로를 찾을 때 사용할 수 있습니다. 재귀적으로 동작하지 않으며 보통 Queue 자료구조를 통해 구현합니다.DFS란?
1
깊이 우선 탐색을 말하며, 트리나 그래프에서 왼쪽부터 가장 깊은 레벨까지 먼저 탐색 한 후 다음 순서를 탐색하는 방식입니다. 재귀적으로 동작하며 보통 Stack을 통해 구현합니다.
PriorityQueue에 대해서 설명하세요
1
우선순위 큐란 먼저 넣은 자료가 가장 먼저 처리되는 기존의 큐와 달리 각 자료에 우선 순위가 부여되고 우선순위가 높은 자료를 먼저 처리하는 자료구조 입니다. 리스트 또는 힙 자료구조를 통해 구현할 수 있습니다.
다이나믹 프로그래밍(DP, 동적계획법)이란?
1
DP, 동적 계획법이라고도 하며 동일한 작은 문제들이 반복하여 나타나는 경우 작은 문제들의 결과를 따로 기록해 두었다 재사용해서 반복횟수를 줄이는 것이 다이나믹 프로그래밍이다. 일반 재귀함수를 사용하는 것보다 처리를 빠르게 할 수 있다.