일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 |
- dp
- 동적 프로그래밍
- 순열
- 코딩테스트
- BFS
- linux
- OS
- 그래프
- 파이썬
- AI
- 운영체제
- 코딩
- 프로그래밍
- PYTHON
- 코딩 테스트
- DFS
- 킥스타트
- 네트워크
- 리눅스
- 동적프로그래밍
- 백준
- nlp
- 프로그래머스
- 구글 킥스타트
- 브루트포스
- kick start
- 알고리즘
- 딥러닝
- google coding competition
- CSS
- Today
- Total
목록CS 기초/자료구조 및 알고리즘 (18)
오뚝이개발자
Sorting Bubble sort Selection sort Insertion sort Shell sort Quick sort Merge sort(분할->병합정렬) Heap sort 각 sorting 알고리즘의 시간복잡도는? Bubble - O(n^2) Selection - O(n^2) Insertion - O(n^2) Shell sort Quick sort worst : O(n^2) best : O(nlogn) avg : O(nlogn) Merge sort Heap sort Searching Linear search는 언제 쓰면 좋은가? item이 sorted 되어있지 않거나 unsortable할 때 Linear search의 단점? 찾는 아이템이 없거나 뒤쪽에 있는 경우 비효율적 Binary sea..
알고리즘의 효율성 측정 방법 basic operation(dominant operation)을 기준으로 하여 input size n에 따른 함수 T(n)으로 실행시간을 나타낸다.(Asymptotic algorithm analysis) Growth rate란? input size가 증가함에 따라 algorithm의 cost가 증가하는 비율 Linear Growth T(n) = n, Quadratic Growth T(n) = n^2 Big-O란? lowest upper bound
그래프란? finite set of vertex(V)와 edge(E)로 이루어진 것 - graph G : (V,E) Edge(간선)란? 집합 E는 VxV의 subset이다. 일종의 relation이라 볼 수 있다. directed graph(digraph) vs. undirected graph 그래프에서 방향성이 중요한지의 여부에 따라 구분 path란? 그래프에서 node의 sequence다. 단, 각 노드를 연결하는 edge가 있어야 함 Connected graph vs. Disconnected graph connected graph : 모든 노드 사이에 path가 존재(disconnected는 그 반대) disconnected graph는 여러 개의 connected component로 구성 그래프에..
Tree란? Connected, Acyclis, Undirected graph Tree는 Graph에 포함된다. Rooted tree란? 하나의 node가 root로 지정된 tree Tree에서 depth란? root 노드로부터 해당 노드까지의 edge 수 트리의 depth : lowest leaf의 depth(이것을 트리의 height라고도 한다.) Tree에서 level이란? depth와 비슷하지만 기준이 edge가 아닌 node 아래 그림에서 B, D는 각각 레벨이 2, 3인 노드이다. Binary tree란? 모든 node가 최대 2개의 child를 갖는 트리 Binary search tree(BST)란? x라는 key value를 갖는 노드의 left subtree에는 x보다 작은 값이, rig..
Map(Dictinary)이란? value와 unique key가 mapping되는 자료구조 Ordered map vs. Unordered map ordered map : key값이 정렬된 것 - balanced tree로 구현 unordered map : key값이 정렬되지 않은 것 - hash table로 구현 Hashing이란? hash function을 통해 key value(hash key)를 table의 position으로 mapping시키는 것 Hash function을 고를 때 유의사항 계산에 드는 cost가 낮은 것(easy to compute) collision을 최소화하는 것 hash table slot에 데이터를 균등하게 분포시키는 것(evenly distributed) Hash에서..
Stack이란? LIFO(Last In First Out) order를 따르는 자료구조 예) 쌓여있는 책더미 Stack 구현의 두 가지 방법(item container로 어떤 것을 선택할지) Linked list로 구현(head에만 삽입하고 head만 지워 이를 stack의 top처럼 활용) Dynamic array로 구현(head를 포인터가 아닌 index 값으로 사용) Queue란? FIFO(First In First Out) order를 따르는 자료구조 예) 줄서기(waiting line) Queue 구현의 두 가지 방법 Linked list로 구현 Dynamic array로 구현 이 때, false-overflow 문제 발생 : 실제로는 빈 공간이 있는데 다 찬 것처럼 보이는 현상 그래서 나온 해..
Array란? 선형자료구조 + 모든 item 같은 자료형 + item들이 메모리 상의 countinuous하게 저장 Array의 문제점 특정 위치 insert, delete가 불편(모든 item 위치 재배치해야함) 만약 얼마나 많은 item을 저장해야 하는지 모르는 상황이면 최대한 많은 메모리를 할당해야 함(waste) Linked list란? data part + link part(다음 item의 주소 가리킴)로 구성 모든 item이 다음 item과 연결되어있는 item sequence array와 달리 메모리 상에 꼭 continuous하게 저장되지 않음(consecutive일수도 있고 아닐수도 있다) Linked list의 장단점 장점 삽입, 삭제가 array에 비해 쉽다 메모리 낭비 최소화(필요한..
클래스란? 데이터와 함수를 하나로 묶어둔 것 부연설명) C에서 구조체(struct)는 오로지 데이터만 가지고 있고 함수(기능)는 구조체의 외부에 정의된다. 하지만 C++ 같은 OOL에서는 이 둘을 한 데 묶어 class라는 것으로 정의한다. 더불어, class로 생성된 object의 자료형이 바로 해당 class이다. Object(=Instance)란? 클래스에 의해 정의된 variable 예컨대, stack S라 하면 S가 stack class의 object(instance)이다. Encapsulation(캡슐화)이란? data와 function을 class로 묶는 것 클래스에서 private member와 public member란? private member : class의 밖에서 access 불가..