제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
접은 글을 통해 먼저 답변을 해보시고 제가 정리한 답을 확인해보시기 바라겠습니다!!
면접을 위한 CS 전공지식 노트(주홍철 저)을 통해 정리한 포스팅입니다.
면접 리스트
해시 테이블을 설명하세요
더보기
해시 테이블은 무한에 가까운 데이터들을 유한한 갯수의 해시 값으로 매핑한 테이블입니다.
이를 통해 작은 크기의 캐시 메모리로도 프로세스를 관리하도록 할 수 있습니다.
그래프와 트리의 차이점을 설명하세요
더보기
그래프는 정점과 간선으로 이루어진 자료구조를 말하며 트리는 그래프 중 하나로 그래프의 특징처럼 정점과 간선으로 이루어져있고 트리 구조로 배열된 일종의 계층적 데이터의 집합입니다. 트리는 그래프와 달리 사이클이 존재하지 않습니다.
이진 탐색 트리에는 어떤 문제점이 있으며 이를 해결하기 위한 트리를 설명하세요
더보기
이진 탐색 트리는 선형적으로 구성될 때 시간 복잡도가 O(N)으로 커지는 문제점이 있습니다. 선형적으로 구성되지 않고 균형 잡힌 트리로 구성하기 위해 나온 트리로 AVL트리와 레드 블랙 트리가 있습니다.
AVL트리는 스스로 균형을 잡는 이진 탐색 트리입니다. 두 자식 서브 트리의 높이는 항상 최대 1만큼 차이가 나는 특징이 있습니다. 탐색 삽입 삭제 모두 시간 복잡도가 O(logN)이며 삽입 삭제할 때마다 균형을 맞추기 위해 회전을 진행합니다.
레드 블랙 트리는 균형을 유지하기 위해 노드에 색상(빨강 또는 검정)을 부여하고 몇 가지 규칙을 따릅니다. 레드 블랙 트리는 AVL 트리보다 느슨한 균형을 유지하기 때문에 삽입과 삭제 시 회전 연산이 더 적게 발생합니다. 이로 인해 삽입과 삭제의 성능은 더 나은 경우가 많습니다. 레드 블랙 트리는 AVL 트리와 마찬가지로 탐색, 삽입, 삭제의 시간 복잡도는 O(log N)으로 보장되지만, AVL 트리만큼 탐색 속도가 빠르진 않을 수 있습니다.
정리
더보기
복잡도
시간복잡도
빅오 표기법
- 시간 복잡도: 입력 크기에 대해 어떠한 알고리즘이 실행되는데 걸리는 시간.
- 반복 횟수를 중점으로 체크하며 빅오 표기법으로 표현
- 10N^2 + 100N이면 O(N^2)으로 표현
공간복잡도
- 공간복잡도: 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양.
- 정적 변수 + 동적 변수
- 예: int[] a = new int[1000]은 1000 * 4byte
자료구조에서의 시간 복잡도
평균
| 자료구조 |
접근 |
탐색 |
삽입 |
삭제 |
| 배열 |
O(1) |
O(N) |
O(N) |
O(N) |
| 스택 |
O(N) |
O(N) |
O(1) |
O(1) |
| 큐 |
O(N) |
O(N) |
O(1) |
O(1) |
| 이중 연결 리스트 |
O(N) |
O(N) |
O(1) |
O(1) |
| 해시 테이블 |
O(1) |
O(1) |
O(1) |
O(1) |
| 이진 탐색 트리 |
O(logN) |
O(logN) |
O(logN) |
O(logN) |
| AVL 트리 |
O(logN) |
O(logN) |
O(logN) |
O(logN) |
| 레드 블랙 트리 |
O(logN) |
O(logN) |
O(logN) |
O(logN) |
worst
| 자료구조 |
접근 |
탐색 |
삽입 |
삭제 |
| 배열 |
O(1) |
O(N) |
O(N) |
O(N) |
| 스택 |
O(N) |
O(N) |
O(1) |
O(1) |
| 큐 |
O(N) |
O(N) |
O(1) |
O(1) |
| 이중 연결 리스트 |
O(N) |
O(N) |
O(1) |
O(1) |
| 해시 테이블 |
O(N) |
O(N) |
O(N) |
O(N) |
| 이진 탐색 트리 |
O(N) |
O(N) |
O(N) |
O(N) |
| AVL 트리 |
O(logN) |
O(logN) |
O(logN) |
O(logN) |
| 레드 블랙 트리 |
O(logN) |
O(logN) |
O(logN) |
O(logN) |
선형 자료구조
연결 리스트
- 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료구조
- 삽입 삭제 O(1) 탐색 O(N)
- prev 포인터와 next 포인터, 데이터를 담는 용량
- 싱글 연결 리스트
- 이중 연결 리스트
- 원형 리스트
- 이중 연결 리스트와 같지만 마지막 노드의 next가 head를 가르킴.
배열
- 같은 타입의 변수들로 이루어져있고, 크기가 정해져있으며 인접한 메모리 위치에 데이터를 모아놓은 집합.
- 중복 허용, 순서가 있음.
- 접근: O(1) 랜덤 접근 가능, 삽입, 삭제: O(N)
- 데이터 추가 + 삭제가 많을 때에는 연결리스트, 접근을 많이할 때에는 배열로.
랜덤 접근과 순차적 접근
- 랜덤 접근(직접 접근): 동일한 시간에 배열과 같은 순차적인 데이터가 있을 때 임의의 인덱스에 해당하는 데이터에 접근할 수 있는 기능.
- 데이터를 순서대로 접근하는 순차적 접근과는 정반대
- 배열 ⇒ 랜덤접근, 연결리스트 ⇒ 순차적 접근
벡터
- 동적으로 요소를 할당할 수 있는 동적 배열.
- 컴파일 시점에 갯수를 모른다면 백터를 사용
- 중복을 허용하고 랜덤접근이 가능.
- 탐색 O(1) 삭제, 삽입 O(N)
스택
- 가장 마지막에 들어간 데이터가 가장 첫번째로 나오는 LIFO(Last In First Out)
- 재귀 함수(콜스택), 알고리즘, 방문기록에 사용
- 삽입 삭제 O(1) 탐색 O(N)
큐
- 먼저 집어넣은 데이터가 먼저 나오는 성질(FIFO, First In First Out), 스택과 반대
- 삽입, 삭제 O(1) 탐색 O(N)
- CPU 작업을 기다리는 프로세스, 스레드 행렬, 네트워크 접속을 기다리는 행렬, 너비우선탐색, 캐시에 사용
비선형 자료 구조
그래프
정점과 간선
- 어떠한 곳: 정점
- 무언가: 간선
- 단방향 간선과 양방향 간선이 있음
- 정점으로 나가는 간선은 outdegree, 들어오는 간선은 indegree
- 정점과 간선으로 이루어진 집합을 그래프
가중치
트리
- 그래프의 특징처럼 정점과 간선으로 이루어져있고 사이클이 없는 구조
특징
- 루트 노드, 내부 노드, 리프 노드가 존재
- 루트 노드
- 내부 노드
- 리프 노드
이진트리
- 자식 노드 수가 두개 이하인 트리
- full binary tree
- 완전 이진 트리
- 왼쪽에서부터 채워져있는 이진 트리
- 마지막 레벨을 제외하고는 다 채워져있으며 마지막 레벨의 경우 왼쪽부터
- 변질 이진 트리
- 포화 이진 트리
- 균형 이진 트리
- 왼쪽과 오른쪽 노드의 높이 차이가 1이하인 이진 트리를 의미
- map이나 set으로 구성
- 이진탐색트리
- 왼쪽 트리에는 노드 값보다 작은 노드들만 오른쪽 트리에는 노드 값보다 큰 노드들만.
- 탐색에는 평균 O(logN) 최악은 O(N)
- AVL 트리
- 최악의 선형 트리가 되는 것을 방지하고 스스로 균형을 잡는 이진 탐색 트리.
- 두 자식 서브 트리의 높이가 항상 최대 1만큼 차이나는 특징
- 탐색 삽입 삭제 O(logN)
- 회전을 함
- 레드 블랙 트리
- 균형 이진 트리
- 탐색 삽입 삭제 O(logN)
- 모든 리프 노드와 루트노드는 블랙이며 어떤 노드가 레드면 그 노드의 자식은 블랙이다.
힙
- 완전 이진 트리 기반의 자료구조.
- 최대 힙: 루트의 키가 키 중에 가장 큰 값.
- 최소 힙: 루트의 키가 키 중에 가장 작은 값.
- 삽입
- 힙의 성질을 통해 리프 노드에 삽입
- 그 이후에 heapify
- 삭제
- 루트 노드 삭제
- 리프 노드와 교체
- heapify
우선순위 큐
- 우선순위 대기열이라고도 하며 우선순위가 높은 요소나 우선순위가 낮은 요소보다 먼저 제공되는 자료구조
- 힙을 기반으로.
맵
- 특정 순서에 따라 키와 매핑된 값의 조합으로 형성된 자료구조
- 레드블랙 트리 자료구조를 기반으로 형성
- 정렬을 보장하지 않을때 해시테이블로
셋
- 특정 순서에 따라 고유한 요소를 저장하는 컨테이너
- unique한 값만을 저장.
해시 테이블
- 무한에 가까운 데이터를 유한한 개수의 해시 값으로 매핑한 테이블
- 삽입 삭제 탐색시 평균적으로 O(1)
참조
더보기
- 면접을 위한 CS 전공지식 노트(주홍철 저) -길벗
