자료구조와 알고리즘을 해야하는 이유
- 취업
- 코딩테스트
- 면접
--arraylist와 linkedlist의 차이를 내부 구현관점에서 설명하시오
--merge sort의 시간복잡도를 증명하시오 (O(nlogn))
- 컴퓨팅적 사고 능력
현업에서
- 알고리즘과 자료구조르르 모르면 해결할 수 없는 문제들이 존재
- 자료구조의 내부 구현을 모르면 잘못 사용하기 쉽다.
- 수억개의 데이터 중 내가 원하는 결과를 빠르게 찾으려면?
- 한정된 자원(시간, 공간)으로 최적의 결과를 내려면?
자료와 자료 구조
- 자료를 어디에 어떻게 관리할까
--검색, 순회, 저장, 삭제, 변경, 스왑
- 자료를 담는 추상적인 틀
Data Data Structre
- 컴퓨터의 자원은 한정적
- 제한된 제약조건 내에 정확한 결과를 도출해야 함
- 데이터의 형태와 쓰임에 가장 적합한 자료구조를 쓰는 것은 매우 중요하다.
모든 병목의 시작점
- 잘못 쓴 자료구조 하나로 진짜 느린 시스템...
- 트래픽이 몰려서 서버가 터진다면?..
- 너무나 큰 Big O?
- 최악의 상황?
자료구조의 특징
- 자료구조의 장점
- 자료구조의 한계
알고리즘
- 어떤 문제가 주어질때 문제를 풀기 위한 동작의 절차
- 입력을 통해 결과를 내는 과정 , 절차
빅오 Big O
점근 표기법
- 빅오 표기법
- 세타 표기법
- 오메가 표기법
상한과 하한
상한 : 최상의 상태
하한 : 최악의 상태
점근 표기법 특징
- 가장 큰 영향력이 있는 항만 표시한다.
- 상수항은 무시한다.
- O(N^3+N^2+N) -> O(N^3)
공간복잡도
- 데이터 관리에 필요한 공간
- 데이터 양의 변화에 따른 공간의 변화
- 예상 소요 공간 측정
시간 복잡도
- 데이터 처리에 소요되는 시간
- 데이터 양의 변화에 따른 소요 시간의 변화
- 예상 처리 시간을 측정
- 지연 장애가 발생했을 때 왜 발생했는지를 찾을 수 있는 근거가 된다.
이진탐색
- 숫자를 절반씩 잘라나가면서 그 범위를 좁혀나가는것
- k는 시행횟수
- logn의 시간 복잡도
merge sort
- 데이터를 절반씩 나눠서 정렬
- n번만큼 데이터를 비교해서 정렬
- 따라서 n * log n
'자료구조&알고리즘' 카테고리의 다른 글
| HASH와 HASH Collision 그리고 Chaining (해시 자료구조) (0) | 2022.04.07 |
|---|---|
| 스택과 큐에 대하여 (0) | 2022.04.07 |
| Double Linked List (이중 연결 리스트) (0) | 2022.04.07 |
| 리스트 - LinkedList (0) | 2022.04.07 |
| 알고리즘은 뭘까? (0) | 2022.04.06 |