반응형
Data Structure
- 배열
임의의 사이즈를 선언 (Heap, Queue, Binary Tree, Hashing 사용) - 스택
행 특정조건에 따라 push, pop 적용 - 큐
BFS를 통해 순서대로 접근할 때 적용 - 연결 리스트
배열 구현, 포인터 구현 2가지 방법 - 삽입,삭제가 많이 일어날 때 활용하기 - 그래프
경우의 수, 연결 관계가 있을 때 적용 - 해싱
데이터 수만큼 메모리에 생성할 수 없는 상황에 적용 - 트리
Heap과 BST(이진탐색)
Algorithm
- 재귀 (Recursion)
가장 많이 활용. 중요한 건 호출 횟수를 줄여야 함 (반복 조건, 종료 조건 체크) - BFS, DFS
2차원 배열에서 확장 시, 경우의 수를 탐색할 때 구조체(class)와 visited 체크를 사용함 - 정렬
퀵소트나 머지소트가 대표적이지만, 보통 퀵소트를 사용함 - 메모이제이션 (Memoization)
이전 결과가 또 사용될 때, 반복 작업을 안하도록 저장 - 이분 탐색 (Binary Search)
logN으로 시간복잡도를 줄일 수 있는 간단하면서 핵심적인 알고리즘 - 최소신장트리 (MST)
사이클이 포함되지 않고 모든 정점이 연결된 트리에 사용 (크루스칼, 프림) - 최소공통조상 (LCA)
경우의 수에서 조건이 겹치는 경우. 최단 경로 탐색시 공통인 경우가 많을 때 적용 - Disjoint-Set
서로소 집합. 인접한 집함의 모임으로 Tree의 일종이며 시간복잡도가 낮음 - 분할 정복
머지 소트에 사용되며 범위를 나누어 확인할 때 사용 - 트라이 (Trie)
모든 String을 저장해나가며 비교하는 방법 - 비트마스킹
|는 OR, &는 AND, ^는 XOR <<를 통해 메모리를 절약할 수 있음
반응형
'Computer > Common' 카테고리의 다른 글
🎧 [개발] CS 공부 팁 (0) | 2023.05.14 |
---|---|
[Javascript] 📚 Set / Algorithm (1) | 2023.02.07 |
[VS Code] IDE / Setting / 개발 도구 / vs code 환경 설정 / 초기 설정 / 설치 / 세팅 / 기본 설정 / Extension / 익스텐션 (0) | 2022.09.27 |
[Tistory] 티스토리 인용구 닫기 / 인용구 따옴표 닫기 / 티스토리 블로그 / 인용구 / 따옴표 / quote (0) | 2022.09.26 |
Software Version Rules (버전) (0) | 2022.09.14 |