자료구조와 알고리즘에 대해 설명해주세요.
자료구조는 데이터를 원하는 규칙 또는 목적에 맞게 저장하기 위한 구조입니다. 알고리즘은 자료구조에 쌓인 데이터를 활용해 어떠한 문제를 해결하기 위한 여러 동작들의 모임입니다.
시간복잡도와 공간복잡도에 대해서 설명해주세요.
좋은 알고리즘이란 작은 메모리 공간을 차지하면서 적은시간 내에 주어진 임무를 수행하는 알고리즘입니다. 이렇게 알고리즘이 좋은 알고리즘인지 판단하는데에 있어서 수행시간과 메모리 사용량을 평가 기준으로 둡니다. 이 각각이 시간복잡도와 공간복잡도입니다.
선형 자로구조와 비선형 자료구조에 대해서 설명해주시고, 각각 어떤 자료구조가 이에 해당하는 지 설명해보세요
선형 구조는 한 원소 뒤에 하나의 원소만이 존재하는 형태를 말합니다. 자료들이 선형으로 나열되어 있습니다.어레이나 링크드리스트, 스택,큐 자료구조가 이에 해당합니다.
비선형 구조는 원소 간 다대다 관계를 가지는 구조로 계층적 구조나 망형 구조를 표현하기에 적절합니다. 그래프나 트리 자료구조가 이에 해당합니다.
배열이 무엇인지 설명해보세요
배열은 연속된 메모리 공간에 순차적으로 저장된 데이터 모음입니다.
Array를 적용시키면 좋을 데이터의 예를 구체적으로 들어주세요. 구체적 예시와 함께 Array를 적용하면 좋은 이유, 그리고 Array를 사용하지 않으면 어떻게 되는지 함께 설명해주세요.
주식 차트를 예로 들을 수 있습니다. 데이터가 새롭게 추가되고 삭제되는 정보가 아니고 날짜별로 주식 가격이 차례대로 저장이 되는 데이터이기 때문입니다. 배열을 사용하지 않고 순서가 없는 자료구조를 사용하게 되면 주식 차트에서 주로 이루어지는 탐색 작업을 할때 많은 시간이 소요되어 굉장히 비효율적일 것이라고 생각합니다.
Array와 ArrayList의 차이점에 대해 설명해주세요.
array는 크기가 고정적이고 arraylist는 크기가 가변적입니다. array는 초기화 시 메모리에 할당되어 arraylist보다 속도가 빠르다는 특징이 있습니다.
Array의 가장 큰 특징과 그로 인해 발생하는 장단점을 설명해보세요.
배열의 가장 큰 특징은 순차적으로 데이터를 저장한다는 점입니다. 데이터에 순서가 있기 때문에 0부터 시작하는 index가 존재하고 그 인덱스를 사용해 특정 요소를 찾고 조작이 가능하다는 것이 배열의 장점입니다. 반면 단점으로는 중간에 요소가 삽입되거나 삭제되어야 하는 경우 그 뒤의 모든 요소들이 한칸식 뒤로 밀리거나 당겨줘야한다는 점입니다. 그리하여 추가와 삭제가 반복되는 경우보다는 탐색이 많은 경우에 배열을 사용하는게 좋습니다.
Array와 Linked list의 차이점은 무엇인가요?
둘의 차이점은 크게 세가지 관점에서 볼 수 있습니다. 특정 요소에 접근할 때, 요소를 삽입하거나 삭제할때 그리고 메모리 할당 시에 차이점을 보입니다. 특정요소에 접근할때 배열의 경우 직접 접근하기 때문에 시간복잡도가 O(1)인 반면 링크드 리스트는 순차적으로 검색하며 접근해야되어서 O(n)이 소요됩니다. 삽입,삭제의 경우 배열은 O(n), 링크드 리스트의 경우는 O(1)이 소요됩니다. 마지막으로 메모리 할당 시 배열에서 메모리는 선언 시 컴파일 타임에 할당되고 stack영역에 할당이 이루어지는 반면, 링크드 리스트는 새로운 요소 추가될 때 런타임에 메모리를 할당하고, 힙영역에 할당이 이루어집니다.
스택과 큐의 차이점은 무엇인가요?
스택은 먼저 넣은 자료가 마지막에 나오는 구조입니다. 리스트로 구현하면 객체를 제거하는 작업이 필요하지만 배열로 구현하면 index를 줄이고 초기화만 하면되므로, 배열로 구현하는게 좋습니다. 주로 DFS나 재귀에 사용됩니다. 큐는 먼저 들어간 자료가 먼저 나오는 구조입니다. 배열로 구현하면 shift할때 고려해야돼서 연결리스트로 구현하는게 좋습니다. 데이터가 입력시간 순서대로 처리되어야 하는 경우에 사용됩니다. 주로 BFS나 캐시에 사용됩니다.
스택과 큐의 실사용 예를 들어 간단히 설명해주세요.
스택은 자바의 스택 메모리 영여에 사용됩니다. 지역변수와 매개변수 데이터 값이 저장되는 공간이고, 메소드 호출 시 메모리에 푸쉬하고 종료되면 pop해서 삭제합니다. 큐는 자원의 할당과 회수를 하는 스캐쥴러 역할을 하는 OS의 스케쥴러에서 쓰입니다.
트리에 대해 설명해주세요
비선형 자료구조로 계층적 관계를 표현하는 자료구조입니다. 값을 가진 노드와 그 노드들을 연결해주는 간선으로 이루어져있습니다. 특징으로는 정점이 N개인 트린 반드시 N-1개의 간선을 가져야합니다.
그래프와 트리의 차이점이 무엇인가요?
둘 다 노드와 간선으로 구성된 자료 구조이지만, 사이클 여부, 루트 정의 여부, 간선이 단방향이냐 양방향이냐, 부모 자식관계, 레벨과 깊이의 개념 유무 등등에서 차이를 보입니다. 트리를 그래패의 특수한 형태라고 생각하시면 될 것 같습니다.
이진트리와 이진탐색트리에 대해 설명해주세요.
이진트리는 각 정점이 최대 2개의 자식을 가지는 트리로, 루트 노드를 중심으로 두개의 서브 트리로 나뉩니다.
종류로는 완전 이진 트리, 포화 이진 트리 , 편향 이진 트리가 있습니다. 이진탐색트리는 이진 탐색과 연결 리스트를 결합한 자료구조입니다. 왼쪽 트리의 모든 값은 부모 노드보다 작고, 오른쪽은 모두 부모 노드보다 크다는 특징을 가집니다. 탐색, 삽입, 삭제의 시간 복잡도는 높이의 영향을 받아 O(h)입니다.
이진탐색트리의 한계점에 대해 설명해보세요.
트리 모양이 한쪽으로 치우친 편향 트리 구조가 되면 트리 탐색의 장점인 O(logN) 시간복잡도가 O(N)에 가까워집니다. 배열보다 많은 메모리를 사용하여 데이터를 저장했는데 탐색에 필요한 시간복잡도가 베열과 같아져버려서 비효율적이게 됩니다. 그래서 이런 편향트리가 되지 않게 해주는 rebalancing 기법을 써서 BBST를 구현해야합니다.
Balanced Binary Search Tree와 그 종류에 대해 설명해주세요.
편향 트리가 되지 않게 rebalancing기법을 사용하여 균형잡힌 이진 탐색 트리를 구현한 것이 bbst입니다.
red-black tree와 avl 트리가 대표적인 bbst입니다.
Red-Black-Tree에 대해 설명해주세요
BST를 기반으로 하는 트리 형식의 자료구조이며, 탐색, 삽입, 삭제에 O(logN)의 시간복잡도가 소요됨.
동일한 노드의 개수일 때, depth를 최소화하여 시간 복잡도를 줄이는 것이 핵심 아이디어임
BST의 특성을 유지하며 삽입,삭제를 진행하며, Java Collection의 ArrayList 그리고 HashMap에서도 쓸정도로 효율이 좋고 중요한 자료구조임
힙에 대해서 설명해보세요
힙은 완전 이진 트리의 일종으로 반정렬 상태를 유지하여 최대값이나 최소값을 빠르게 반환할 수 있는 자료구조입니다. 루트가 가장 큰 값이 되는 최대 힙과 루트가 가장 작은 값이 되는 최소 힙이 있습니다. 주로 우선순위 큐를 구현하기 위해 사용됩니다.
힙의 삽입,삭제 방식에 대해 설명하고, 왜 이진탐색트리와 달리 편향이 발생하지 않는지 설명해주세요.
삽입은 맨 마지막 자리에 요소를 삽입 후 힙의 속성에 맞을 때까지 부모,자식간의 교환을 진행합니다. 마찬가지로 삭제도 이루어진 후 힙의 속성에 맞을 때까지 부모, 자식간의 교환을 진행합니다.
이진탐색트리와 달리 편향이 발생하지 않는 이유는 데이터를 삽입하고 삭제할때 특별한 규칙에 따라 트리를 조정하기 때문입니다.
PriorityQueue에 대해 설명해주세요.
우선순위 큐는 들어간 순서에 상관없이 우선순위가 높은 데이터를 먼저 꺼내기 위해 고안된 자료구조입니다. 우선순위 큐를 구현할 떄 배열, 링크드 리스트, 힙을 사용할 수 있지만 그 중 힙 방식이 O(logN)을 보장하기 때문에 일반적으로 완전 이진 트리 형태의 힙을 이용해 구현합니다.
힙 정렬의 시간복잡도는 어떻게 되나요? Stable 한가요?
데이터를 힙으로 구성하는데 O(n)이 소요되고, 힙을 재조정하는 작업을 반복해야해서 O(nlogn)시간이 소요됨
stable한지 안한지는 동일한 값들의 상대적인 순서가 정렬 전후에도 유지되냐안되냐를 말하는데, 힙정렬은 보다시피 원래 배열의순서를 무시하고 힙을 구성하기 때문에 , Stable하다고 할 수 없음
Hash 자료구조에 대해 설명해주세요.
데이터를 효율적으로 관리하기 위해, 임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는 것입니다. 그래서 데이터가 많아지면 다른 데이터가 같은 해시 값으로 충돌나는 현상이 발생합니다.
해시값이 충돌했을 때, 어떤 방식으로 처리할 수 있을까요?
크게 두가지 방법이 있습니다. 체이닝과 개방주서법입니다. 체이닝은 연결리스트로 중복된 값을 제거하는 방법입니다. 그리고 개방주소법은 충돌이 발생한 경우, 다른 빈 슬롯을 찾아 데이터를 저장하는 방법입니다. 선형 탐사, 제곱 탐사, 더블 해싱 등의 방법이 있습니다. 주로 구현이 간단한 체이닝 방법을 많이 사용합니다.
해시 맵과 해시테이블의 차이점에 대해 설명해주세요.
동기화 지원 여부와 null값 허용 여부에서 차이를 보입니다. 자원의 동기화를 고려햐아 하는 상황이라면 해시 테이블을 사용해야 하며, 해시테이블은 널값을 허용하지 않습니다. 반면 해시 맵의 경우는 병렬처리를 하지않고 동기화도 고려하지 않는 경우에 사용합니다. null값을 허용하며 thread-safe하지 않습니다.
B-tree와 B+Tree를 비교하여 설명해주세요.
B-tree는 이진 트리를 확장해서 더 많은 수의 자식을 가질 수 있게 일반화 시킨 것입니다. B+트리는 B트리의 변형 구조로 인덱스 역할만 하는 비단말 노드가 추가로 있습니다. b+트리의 경우 모든 키가 리프노드에 있어서 검색이 빠르고 정확하며, 삭제 또한 b-tree보다 쉽습니다.
Trie에 대해 설명해주세요
트라이는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조입니다.
그래프 자료구조에 대해 설명해보세요
그래프는 정점과 간선으로 이루어진 자료구조입니다. 사실 트리도 그래프의 일종인데 그래프는 트리와 달리 정점마다 간선이 존재하지 않을 수 있으며, 루트노드, 부모,자식 노드개념이 존재하지 않습니다.
그래프를 구현할 수 있는 두 방법에 대해서 설명해주세요
인접행렬과 인접리스트가 있습니다. 인접행렬은 메모리가 많이 드는 대신 탐색이 빠릅니다. 간선이 많을때 주로 사용합니다 인접리스트는 메모리는 많이 들지 않지만 탐색이 느립니다.
정점의 개수가 N개, 간선의 개수가 N^3개라면, 어떤 방식으로 구현하는게 효율적일까요?
간선의 개수가 많은 경우는 매우 밀집된 그래프입니다. 이렇게 밀집된 그래프일 경우 일반적으로 연결 리스트로 구현하는게 더 효율적입니다. 연결리스트는 공간효율성과 간선 추가 및 삭제에 있어서 효율적이기 때문입니다.
사이클이 없는 그래프는 모두 트리인가요? 아니라면 예시를 들어주세요
그래프가 되려면 사이클이 없는 것 뿐더러, 간선의 방향성이 존재해야합니다. 사이클은 없지만, 간선의 방향성이 존재하지 않는 그래프는 트리가 아닙니다.
그래프에서 최단거리를 구하는 방법에 대해 설명해주세요
그래프에서 최단거리 알고리즘으로는 다익스트라 알고리즘, 벨만-포드 알고리즘, BFS 등이 있습니다. bFS는 가중치가 모두 없거나 모두 같은 경우, 다익스트라나 밸만포드 알고리즘의 경우는 가중치가 있는 그래프에서 최단거리를 구할때 용이합니다.
