[CS] 자료구조/알고리즘 관련(작성중...)

정렬 알고리즘 시간/공간 복잡도

 

Array vs LinkedList

Array은 메모리상에 순서대로 데이터 저장 => 캐시의 지역성으로 인해 상대적으로 빠른 탐색 수행

인덱스로 조회할 수 있음 => 인덱스 조회 성능 높음

 

LinkedList는 다음 데이터의 위치에 대한 포인터를 가지고  있음

중간에 데이터를 삽입, 삭제하는 것이 용이 

 

List vs Set

List는 중복된 데이터를 저장하고 순서를 유지하는 선형 자료구조

Set은 중복되지 않은 데이터를 저장하고 순서 유지X, 선형 자료구조

 

 Hash Function, Hash Table

해시 함수(특정 알고리즘)를 통해 key값을 해쉬 코드(작은 범위의 숫자)로 변환한다.

key 값 과 해쉬 코드가 1:1 매칭이 되는 경우는 해쉬를 사용하는 의미가 없어짐, array 쓰는거랑 다를게 없음

반대로 1개의 키값이 복수의 값을 가지는 경우(Collision), 이 정도가 심해지면 제대로 된 동작할 수 없음

 

 

Stack, Queue

Stack은 선형 자료구조의 일종, LIFO

Queue는 선형 자료구조의 일종, FIFO 

 

Heap, PriorityQueue 

우선순위 큐는 힙(Heap)구조로 구현

Heap은 완전 이진트리

모든 노드에 저장된 값들은 자식 노드들의 것보다 자식 노드들의 것보다 우선순위가 크거나 같음

최대 힙: 루트 노드 올라갈수록 값이 커지는 구조

최소 힙: 루트 노드 올라갈수록 값이 작아지는 구조

 

Tree, Binary Tree, BST, AVL Tree

 

 

피보나치 수열 구현 방법

1. 재귀 함수로 구하는 방법
2. 반복문으로 구하는 방법
3. 배열을 만들어 DP 방식으로 이전 값들을 활용하여 구하는 방법
4. 행렬 곱셈을 통한 방법

 

DFS, BFS

DFS: 깊이 우선 탐색

그래프에서 더 탐색할 수 있는 노드가 있다면 끝까지 탐색해보고 없으면 전 단계로 돌아오는 방식

O(V+E)

BFS: 넓이 우선 탐색 

현재 탐색하고 있는 노드에서 갈 수 있는 모든 노드로 뻗어나간다. 

BFS로 구한 경로는 최단 경로

O(V+E)

 

 

참고자료 

ksundong/backend-interview-question: 백엔드 개발자로 입사를 준비하며 받았던 질문, 예상했던 질문, 인터넷 참고한 질문(CC BY-NC) (github.com)

GitHub - ksundong/backend-interview-question: 백엔드 개발자로 입사를 준비하며 받았던 질문, 예상했던 질

+ 구글링 기타 자료들...