Q1. 스택과 큐에 대해 설명해주세요
A1. 스택은 LIFO 구조이며, 큐는 FIFO 구조입니다.
LIFO 구조는 마지막에 들어온 데이터가 가장 먼저 나오는 구조입니다
FIFO 구조는 처음에 들어온 데이터가 가장 먼저 나오는 구조입니다
Q2. 배열과 링크드 리스트의 차이점에 대해서 설명해주세요
A2.
배열과 링크드리스트에서 가장 큰 차이점을 보이는 부분은 검색과 삽입/삭제 연산입니다
검색에선 배열은 인덱스를 통해 바로 찾을 수 있으므로 O(1)의 시간복잡도를 가집니다. 그러나 링크드리스트는 찾는 노드까지 순차적으로 찾아 들어가야하므로 O(n)의 시간복잡도를 가집니다.
삽입/삭제에선 배열은 메모리 위치가 연속적이고 고정되어 있기 때문에 많은 시간이 소요되는 반면 링크드리스트는 삭제 시 이전 노드의 메모리 주소만 바꿔주면 되고 삽입 시 빈 메모리 위치에 저장만 하면 되기 때문에 연산이 빠릅니다
Q3. 트리에 대해 설명해주세요
A3. 트리는 노드로 이루어진 자료 구조이며 하나의 루트 노드를 갖습니다.
루트 노드는 0개 이상의 자식 노드를 가지고 있으며 계층적으로 반복해서 정의됩니다.
그리고 노드들과 노드들을 연결하는 간선으로 구성되어 있습니다.
방향성이 있는 비순환 그래프로도 정의됩니다
Q4. 그래프에 대해 설명해주세요
A4.
노드와 노드를 연결하는 간선으로 이루어진 자료구조이며 트리와 다르게 루트 노드의 개념이나 계층적(부모-자식) 개념이 없습니다.
Q5. 해시테이블에 대해 설명해주세요
A5.
해시 테이블이란 데이터를 효율적으로 관리하기 위해서 고정된 길이의 데이터로 매핑하는 것을 뜻합니다. 보통 해시 함수를 구현하여 해시 값으로 변환시켜서 매핑합니다.
Q6. 빅오 표기법에 대해 설명해주세요
A6. 빅오 표기법은 쉽게 말해 알고리즘의 시간/공간 효율성을 표기해주는 표기법입니다.
보통 시간복잡도와 공간 복잡도를 따질 때 빅오 표기법을 많이 씁니다.
다른 표기법으로 빅오메가, 빅세타 표기법이 있습니다. 그럼에도 빅오 표기법을 쓰는 이유는 빅오 표기법이 최악의 상황을 가정해서 표기해주는 표기법이기 때문입니다.
Q7. 퀵 정렬과 합병 정렬에 대해서 설명해주세요
A7. 퀵 정렬은 배열 중 한 개를 피벗으로 정하고 피벗보다 작은 원소들, 큰 원소들로 나눈 뒤 나눈 배열을 재귀적으로 돌려서 정렬하는 방법, 시간 복잡도는 최악의 경우 O(n^2)이며 최선의 경우 O(nlogn)이다. 실생활의 경우 시간 복잡도가 최악의 경우일 가능성이 적어서 많이 쓰이는 정렬입니다.
합병 정렬은 퀵 정렬과 비슷하게 분할 정복 방법으로 정렬을 하지만 다른 점은 각각의 배열은 반으로 쪼개서 정렬한 뒤 다시 합치면서 정렬을 해갑니다. 시간복잡도는 최악의 경우도 O(nlogn)입니다
3단계 요약노트 목적과 활용법은 아래 글을 읽어보시면 좋습니다
도움이 필요하시면 사연을 메일로 보내주세요
jek300300@gmail.com
도움이 되셨다면 공감과 구독 부탁드립니다
읽어주셔서 감사합니다
당신의 취업이 성공할 때까지 같이 하겠습니다! by 취업길잡이 Coy
