면접 준비] 자료구조

면접 준비] 자료구조

320x100

안녕하세요, readder입니다.

면접을 준비하여 질문과 간단한 대답들을 정리하고자 합니다.

참고로 저는 기억력이 나쁜 편이라 길게 준비하지 않았고, 무조건 이것만이라도 기억하자는 의미로 꾸미는 말 없이 주요 내용만 짧게 적었습니다.

- 자료구조란

자료구조란 데이터를 저장하는 방법을 의미하며, 상황과 목적에 맞게 자료구조를 선택하여 데이터를 저장하는 것이 중요시되고 있다.

- 알고리즘이란

어떤 문제를 해결하는 명확한 방법이며, 그 과정이 명료해야 하고, 최적화된 것이어야 좋은 알고리즘이라고 불린다.

알고리즘을 평가하기 위한 방법으로 빅오 표기법이 존재하며, 빅오 표기법은 최고차항을 기준으로 알고리즘의 시간/공간 복잡도를 평가하는 방법이다.

- 스택이란

스택은 선형 자료구조 중 하나로, 데이터가 새롭게 쌓일 때 이전 데이터의 위에 쌓이는 형식으로 데이터를 저장하며, 데이터를 추출할 경우에도 마찬가지로 가장 위에 있는 데이터를 가져온다. 따라서 스택은 가장 마지막에 들어온 데이터를 기준으로 삽입/삭제를 하는 Last-in-first-out 형식의 자료구조다.

뒤 조회, 삽입, 삭제 : O(1)

특정 위치 조회, 삽입, 삭제 : O(N)

- 큐란

큐는 선형 자료구조 중 하나로, 데이터가 새롭게 쌓일 때는 데이터의 가장 뒤에 추가하지만, 데이터를 추출하는 경우에는 가장 앞에 존재하는 데이터를 추출하는 방식으로 데이터를 관리하는 First-in-First-out 형식의 자료구조다

앞 조회, 삭제 : O(1), 뒤 삽입 : O(1)

특정 위치 조회, 삽입, 삭제 : O(N)

- 트리란

트리는 비선형 자료구조 중 하나로, 나무가 나뭇가지를 가져 뻗어나가는 형태의 알고리즘이다. 데이터 하나의 단위를 노드라고 하는데, 한 노드는 여러개의 자식 노드를 가질 수 있으며, 그 자식 노드 또한 여러개의 자식 노드들을 가질 수 있다.

- 힙이란

최댓값 또는 최솟값을 찾기 위한 자료구조로, 최댓값을 찾는 힙은 최대힙, 최솟값을 찾는 힙은 최소힙으로 불리며, 일반적으로 우선순위 큐를 이용하여 구현한다.

- 우선순위 큐란

데이터를 삽입/삭제 시에 정렬하는 자료구조로, 트리와 힙의 개념을 사용한다. 데이터를 단순히 삽입하고 추출하는 것만으로 정렬이 되는 알고리즘이며, 삽입과 삭제 시 O(Log N)의 빠른 시간복잡도를 사용하기 때문에 반드시 정렬된 데이터만을 갖고 있어야 하는 경우 우선순위 큐를 사용한다.

- 해시 테이블과 시간 복잡도

해시 테이블은 Key, Value 형식으로 값을 저장해 Key값을 해시 함수를 이용해 변환한 후, 그 값을 주소로 사용하여 해당 주소에 값을 넣는 자료구조이다. Key값을 알고 있다면 삽입, 삭제, 조회 모두 O(1)의 빠른 시간복잡도를 보장하는데, Key값을 모른다면 전체를 모두 탐색해야 하므로 O(N)의 시간 복잡도가 소요된다.

조회, 삽입, 삭제 : O(1)

(최악)조회, 삽입, 삭제 : O(N)

- 연결리스트와 배열리스트 차이

연결 리스트는 List를 이용하여 각각의 값을 노드로 보며, 노드간에 연결을 통해 자료를 저장하는 자료구조이고, 배열리스트는 배열을 이용하여 만든 자료구조인데, 어떤 것으로 구현했느냐에 따라 두 자료구조의 차이점이 발생한다.

연결리스트는 조회시 모든 노드를 조회해야 하므로 O(N), 가장 앞 또는 뒤에 있는 데이터를 삽입/삭제할 경우에는 O(1)이 걸리며, 배열리스트는 조회 시 인덱스를 통해 바로 조회하므로 O(1)이지만 데이터 삽입/삭제 시에는 O(N)이 소요된다.

320x100

from http://readerr.tistory.com/50 by ccl(A) rewrite - 2021-11-10 13:00:26