알고리즘
: 문제해결을 위한 절차나 방법을 알고리즘이라고 말합니다. 다양한 문제를 풀기 위해 다양한 방법이 있듯이 알고리즘에는 정답이 없다. 알고리즘의 성능을 표현하는 방법으로 시간복잡도(big O)로표현한다.
- 대표적인 알고리즘 : 정렬, 탐색, 재귀 등
시간복잡도
- O(1) : 단 한번의 연산
- O(n) :
- O(logn) :
- O(nlogn) :
- O(n^2) :
정렬 알고리즘
- 선택정렬 - O(n^2)
- 버블정렬 - O(n^2)
- 삽입정렬 - O(n^2)
- 병합정렬 - O(nlogn)
- 퀵정렬 - O(nlogn)
탐색 알고리즘
- 선형 탐색 - O(n)
- 이진 탐색 - O(logn) : 이진 트리를 활용한 탐색이라고 보면 된다.
자료구조
자료구조를 프로그래밍에서 어떻게 사용하는가?
- 원시구조 - 정수, 실수, 문자 ...
- 선형구조 - 배열, 연결리스트, 스택 ...
- 비선형구조 - 트리, ...
배열(Array)
- 장점 : 빠르다(인덱스를 통해 바로 데이터 접근이 가능하다)
- 단점 : 크기를 지정해주면 바꿀 수 없고, 데이터의 존재 유무 상관없이 메모리를 차지한다
연결리스트(Linked List)
- 장점 : 자료의 갯수를 마음대로 늘렸다 줄였다 할 수 있다.
- 단점 : 자료를 찾기 위해선 자료의 갯수만큼 탐색을 해야 한다.
스택(Stack)
프링글스 통을 생각하면 편하다. 먼저 들어간 자료가 가장 나중에 나온다.
큐(Queue)
대기열을 생각하면 편하다. 먼저 들어간 자료가 먼저 나간다.
덱(Dequeue)
큐와 스택을 합쳐놓은 것,
