CS 간단 정리

1. 자료구조

어레이(Array), 어레이리스트(ArrayList), 연결리스트 (Linked List)

• Array는 index로 빠르게 값을 찾는 것이 가능함
  • 어레이(배열, Array)는 선언할 때 크기와 데이터 타입을 지정해야 함
• LinkedList는 데이터의 삽입 및 삭제가 빠름
  • 연결리스트는 한 노드에 연결될 노드의 포인터 위치를 가리키는 방식
  • 인덱스가 없는 대신에 주소값만 수정해주면 쉽게 데이터를 삽입하고 삭제할 수 있음
  • 다만 인덱스가 없기 때문에, k번째 요소 찾기 등의 검색에서는 시간이 더 오래 걸릴 수 있음
• ArrayList는 데이터를 찾는데 빠르지만, 삽입 및 삭제가 느림
  • 어레이와 달리 크기를 정해줄 필요가 없고, 순서가 중요하다
  • 중간에 데이터를 삭제하거나 추가하려면 그 외 데이터들을 줄줄이 밀거나 당겨야 해서 느리다

스택 & 큐

트리 & 트라이(Tries)

그래프

힙

벡터

해시테이블

2. 알고리즘

1. BFS (너비 우선 탐색)
2. DFS (깊이 우선 탐색)
3. 이진 탐색
4. 병합 정렬 (Merge Sort)
5. 퀵 정렬

3. 개념

1. 비트 조작 (Bit Manipulation)
2. 메모리 (스택 vs 힙)
3. 재귀
4. DP (다이나믹 프로그래밍)
5. big-O (시간과 공간 개념)