자료구조(Data Structure)

데이터를 메모리에 효율적으로 배치하고 저장하고 관리하는 방법을 의미한다. 데이터 특성에 맞는 자료구조를 선택하는 일은 효율적인 알고리즘을 위해서 필수적인 일이다.

• 목적: 서비스나 어플리케이션에 필요한 데이터를 제공하고 효율적으로 검색(접근), 삽입, 삭제할 수 있으려면 해당 기능에 적합한 자료구조를 쓰는 것이 중요하다.
• 종류: 배열, 단일 연결리스트, 이중 연결리스트, 스택, 해시 테이블 등

자료구조 공부방향

• Order 자료 구조 안에 있는 데이터들의 순서가 보장되는지
• Unique 중복된 데이터가 들어갈 수 있는지
• Search 검색할 때 얼마나 효율적인지
• Modification 수정할 때 얼마나 효율적인지
• 시간이 없다면 구현방법, 사항을 일일이 공부하는 것 보다는, 해당 자료구조는 어떤 상황에 쓰는 것이 좋고 어떤 API 들이 있는지 위주로 공부하면 좋음.

자료구조의 종류

1. 선형 자료구조

선형 자료구조는 데이터가 선처럼 길게 나열된 자료구조이다.

1. 랜덤 접근 가능: 모든 데이터에 O(1)로 접근 가능한 자료구조

• 배열(Array)
• 해시(Hash)
  • 해시 테이블(Hash Table)
  • 해시함수에 키값을 넣어 주소값을 얻고 그 주소에 위치한 버킷에 저장된 데이터를 가져오는 방식
  • 항상 O(1)이 보장되는 것은 아니다.

2. 랜덤 접근 불가능: 모든 데이터에 O(1)로 접근이 보장되지 않는 자료구조

• 스택(Stack)
• 큐(Queue)
  • 우선순위 큐
• 데크(Deque)
• 연결 리스트(Linked List)

선형 자료구조 탐색법

• 순차 탐색
• 이분 탐색

2. 비선형 자료구조

비선형 자료구조는 선형 자료구조가 아닌 모든 자료구조이다.

• 그래프(Graph)

그래프 순회 알고리즘

• 깊이 우선 탐색(DFS)
• 너비 우선 탐색(BFS)

• 트리(Tree)
  • 이진 트리(Binary Tree)
  • 이진 검색 트리(Binary Search Tree: BST)
  • 히프(Heap)
  • 우선순위 큐(Priority Queue)

트리 순회 알고리즘

• 전위 순회(preorder)
• 중위 순회(inorder)
• 후위 순회(postorder)
• 레벨 순서 순회(levelorder)

그 외

• 문자열(String)

기타

• Map & Set

Ref

• 드림코딩 엘리님의 영상
• javascript datastructure
• 신입 개발자 전공 지식 & 기술 면접 백과사전

알고리즘(Algorithm)

제한된 공간과 시간 안에서 데이터를 어떻게 처리할 것인지를 정해놓은 로직(주어진 인풋으로 정의된 계산을 수행한 뒤 아웃풋을 내는 것을 말함)

알고리즘 공부방향

• 인풋 사이즈가 커질수록 Big O가 어떻게 변화하는지
• 시간 복잡도, 공간 복잡도 고려
• 어떤 자료구조를 이용하여 알고리즘을 작성하는 것이 좋을지
• 최종적으로 작은 공간과 빠른 시간안에 효율적으로 처리하는 알고리즘을 만드는 것이 목표

• 자동완성, 복붙 사용을 최소화할 것
• 알고리즘 풀이에 사용하는 언어를 이해하려고할 것
• 충분한 고민 & 문제에 대한 이해/풀이 아이디어, 어려웠던 점 및 해결책 생각할 것

알고리즘의 종류

탐색(Search)

• 선형 탐색(Linear Search)
• 이분(이진) 탐색(Binary Search)
  • https://im-developer.tistory.com/126
• 순차 탐색(Sequential Search)
• 해시 탐색(Hash Search)
  • 해시 테이블(Using Hash Tables)

정렬(Sorting)

• 버블 정렬(Bubble Sort)
• 선택 정렬(Selection Sort)
• 삽입 정렬(Insertion Sort)
• 퀵 정렬(Quick Sort)
• 병합 정렬(Merge Sort)
• 힙 정렬(Heap Sort)
• 기수 정렬(Radix Sort)
• 계수 정렬(Count Sort)

완전 탐색(Exhaustive Search)

• 브루트 포스(Brute Force)
• 깊이 우선 탐색(DFS) & 너비 우선 탐색(BFS)
• 백트래킹(BackTracking)
• 재귀(Recursion)
• 순열과 조합(Permutation, Combination)
• 비트 마스크(Bit Mask)

분할 정복(Divide and Conquer)

동적 계획법(Dynamic Programming)

그리디(Greedy)

트리

• 이진 검색 트리(Binary Search Tree)

그래프

• 위상 정렬

최단 경로

• Floyd-Warshall
• 다익스트라(Dijkstra)
• Bellman-Ford

최소 신장 트리(MST, Minimum Spanning Tree)

• Kruskal
• Prim

기타

• 비트 연산
• 진수 변환
• 유클리드 호제법(최대공약수, 최소공배수)
• 투포인터(슬라이딩 윈도우)
• 조합, 순열
• 파라메트릭 서치
• 최장 증가 수열(LIS)
• 최소 공통 조상(LCA)
• 비트 마스크(BitMask)
• Matching Parenthesis problem
• Variables / Pointers manipulation
• reverse linked list(duplicates, removing duplicates)
• Custom data structures(Object oriented programming)

Ref

• BFS, DFS
• 안경잡이 개발자
• JS로 트리(BFS, DFS) 구현하기
• 알고리즘 풀 때 유용한 javascript 함수들