면접 준비
알고리즘
자료구조와 알고리즘의 개념에 대해 서술하세요.
자료구조는 데이터를 담기 위한 구조를 의미합니다. 이는 데이터들의 저장형태를 결정하는 것을 말합니다.
알고리즘은 어떤 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것을 말합니다. 즉, 어떤 사람이든 해당 알고리즘을 보고 같은 결과를 도출할 수 있어야 합니다.
자료구조와 알고리즘의 관계
일반적으로, 효율적인 알고리즘을 구현하기 위해 자료구조의 선택이 중요하며, 두 개념은 밀접한 관계를 갖습니다. 예를 들면, BFS를 구현하기 위해서는 Queue 자료구조가 사용되어야 합니다.
추가 학습
참고 자료
자료구조를 여러 기준에 따라 분류가 가능합니다.
구현
- 배열 : 동일한 타입의 데이터들이 메모리 상에 연속된 주소로 저장된 자료구조.
- 튜플 : 두개 이상의 타입의 데이터를 묶어서 다루는 자료구조.
- 연결리스트 : 노드 단위, 연결 리스트의 노드에는 값과 다음 노드를 가리키는 참조값으로 구성.
- 원형연결리스트 : 연결리스트와 동일한 노드 구성을 가지며, 마지막 노드의 다음 참조값이 처음 노드이다.
- 이중연결리스트 : 노드가 이전 노드와 다음 노드를 가리키는 참조값으로 구성. 원형은 아니다.
- 환형이중연결리스트 : 이중연결 + 원형리스트
- 해시테이블 : 해시값을 기준으로 인덱싱되는 자료구조.
형태
-
선형 : 자료구조 내 원소들이 하나씩 순차적으로 나열시킨 형태.
- 스택 : LIFO 구조의 자료구조
- 큐 : FIFO 구조의 자료구조
- 환형큐 : ??
- 덱 : 양 끝에서 원소 삽입/추출이 가능한 자료구조
-
비선형 : 하나의 원소 뒤에 여러개의 원소가 존재할 수 있는 형태.
- 그래프 : 노드와 간선으로 이뤄진 자료구조
- 유향 그래프, 무향 그래프 : 간선에 방향성을 갖는지 여부에 따른 그래프 분류. 유향간선 방향이 부모 노드로 올라가는 방향성을 갖음, 무향방향성이 없음.
- 트리 : ??
- 이진 트리 : 자식이 최대 2개인 트리 구조.
- 힙 : 이진트리의 일종으로 이진트리에서 어떤 특성을 부여한 자료구조.
- 최소힙 : 부모의 키 값이 자식의 키 값보다 작거나 같다.
- 최대힙 : 부모의 키 값이 자식의 키 값보다 크거나 같다.
-
파일구조
- 순차 파일
- 색인 파일
- 직접 파일
그래프와 트리의 차이점에 대해 설명하세요.
그래프와 트리 모두 노드와 간선으로 구성된 자료구조를 말합니다.
트리는 그래프에 포함된 자료구조의 일종으로써, 그래프는 하나의 노드에 여러 간선이 존재할 수 있짐만, 트리는 노드 간에 하나의 간선만 존재할 수 있습니다. 이로 인해 그래프보다 데이터를 탐색하는 것에 조금 더 용이하다는 장점이 있습니다.
비교
- 그래프
- 방향 : O or X
- 사이클 : 순환, 비순환, 자기순환
- 루트 노드 : X
- 부모-자식 : X
- 모델 : 네트워크 모델
- 간선 수 : 자유
- 트리
- 방향 : O
- 사이클 : 비순환
- 루트 노드 : O
- 부모-자식 : O
- 모델 : 계층형 모델
- 간선 수 : N~1개
이진 탐색 트리에 대해 설명해주세요.
이진 탐색 트리는 이진 탐색과 연결리스트를 결합한 자료구조 입니다.
부모 노드는 최대 2개의 자식노드를 가질 수 있으며, 부모 노드를 기준으로 부모 노드보다 작은 값을 왼쪽으로 정렬하고 큰 값을 오른쪽으로 정렬해줍니다.
해당 개념은 이진 트리 탐색의 단점인 원소 추가,삭제가 불가하다는 점과 연결리스트의 단점인 탐색이 O(N)의 시간 복잡도가 발생하는 단점을 보완하기 위해 고안된 자료구조입니다.
해당 자료구조에서 연산하는 원리에 대해 간단하게 설명드리겠습니다.
- 검색
루트 노드에서 시작하며, 찾으려는 값과 비교하여 값이 작으면 왼쪽, 크면 오른쪽으로 탐색 범위를 좁힙니다. 리프 노드에 도달할 때까지 탐색을 못하면 탐색을 실패하게 됩니다. 시간 복잡도는 계층 수(h) 만큼의 시간이 걸립니다. - 삽입
삽입할 값을 가진 노드를 생성합니다. 현재 트리의 루트 노드부터 시작하여 삽입할 위치를 탐색합니다. 이를 리프 노드까지 탐색합니다. 적절한 위치를 탐색 후 해당 위치에 노드를 삽입합니다. - 삭제
삭제하려는 노드의 자식 수에 따라 3가지로 나누어 생각합니다.
- 자식이 없는 경우
해당 노드를 트리에서 단순히 제거합니다. - 자식이 하나인 경우
해당 노드를 제거한 뒤, 노드의 자식을 부모 노드와 연결합니다. - 자식이 두개인 경우
삭제하려는 노드를 대체할 노드를 찾습니다. 대체할 노드는 일반적으로 삭제하려는 노드의 오른쪽 서브트리에서 가장 작은 값을 가지는 노드 또는 왼쪽 서브트리에서 가장 큰 값을 가지는 노드로 합니다.
대체할 노드를 삭제하려는 노드이 위치에 보갓한 뒤, 대체할 노드가 원래 있던 위치에서 다시 삭제 연산을 수행합니다.
트리순회 방식
스택과 큐에 대해 설명하세요.
두 자료구조 모두 선형자료 구조로 배열과 연결 리스트를 사용하여 구현이 가능합니다.
두 자료구조의 차이점은 다음과 같습니다.
스택은 LIFO 방식으로 구현된 자료구조 입니다. 이는 먼저 들어간 원소는 제일 마지막에 나오게 되는 자료구조를 말하며, 일반적으로 탑의 구조와 같습니다.
큐는 FIFO 방식으로 구현된 자료구조 입니다. 이는 먼저 들어간 원소는 제일 처음 나오게 되는 자료구조를 말하며, 일반적으로 파이프의 구조와 같습니다. 원소가 나오는 곳을 front 원소가 삽입되는 곳을 rear라고 합니다.
각각의 활용 예시를 들어보면,
스택의 대표적인 예시로 웹 브라우저 방문기록이 있습니다.
2개의 페이지를 열어준 뒤 순차적으로 스택A에 담아줍니다. 스택A의 가장 상위 요소가 현재 페이지를 의미합니다. 이전 페이지로 이동하기 위해서는 스택A를 pop해 준뒤 스택 B에 push 해줍니다. 그렇게 되면 이전 페이지가 스택A의 최상단에 위치하게 되는 방식으로 구현됩니다.
큐의 대표적인 활용 예시로는 대표적으로 대기열 구현입니다.
간단히 대기열 큐에 삽입 시 offer 해준 뒤 필요 개소에서 poll() 해주어 데이터를 가져옵니다.
Array와 ArrayList의 차이에 대해 설명하세요.
Array는 크기가 고정되어 있고, ArrayList는 크기가 가변적입니다.
Array는 초기화 시 메모리에 할당되어 ArrayList보다 속도가 빠르고, ArrayList는 데이터 추가 및 삭제 시 메모리를 재할당하기 때문에 속도가 Array보다 느립니다.
사용 상황을 나누어 생각해보면,
우선, 원소의 크기가 정해져 있는 경우 배열을 사용하는 것이 효율적입니다.
그다음 다차원 자료구조가 필요한 경우 배열을 사용합니다.이는 Array의 경우 지원하는 자료구조 형태가 있지만, ArrayList는 직접 구현해줘야 하기 때문입니다.
💡 ArrayList에 크기가 변경되는 과정에 대해 이해하고 계신가요?
