1.이진탐색
*단순탐색: n개의 리스트에 대해서 n번의 탐색이 필요
*이진탐색: n개의 리스트에 대해서 log2 n번의 탐색이 필요
- 정렬된 리스트에 대해서
- 찾고자 하는 값과 리스트의 중간에 있는 값을 비교, 중간값 보다 찾고자하는 값이 크다면 중간값보다 작은 수들을 탐색범위에서 제외시킨다.
- 각 단계를 반복할 때 마다 탐색 범위가 반으로 줄어든다.
2.빅오표기법
- 알고리즘의 속도는 시간이 아니라 연산 횟수가 어떻게 증가하는지로 측정한다.
- 빅오 표기법은 알고리즘이 동작하기 위해 필요한 연산 횟수를 나타낸다.
- 빅오 표기법을 사용하면 입력데이터의 크기가 늘어날 때 알고리즘에 걸리는 시간이 어떤 식으로 증가하는지 알 수 있다.
- 빅오 표기법은 최악의 경우를 나타낸다.
ex) 이진탐색은 크기가 n인 리스트를 확인하기 위해 log n번의 연산이 필요하다 -> O(log n)
3.메모리가 동작하는 방법
-메모리에 무언가 저장해야 할 때 마다 컴퓨터에 공간을 요청하면 컴퓨터는 무언가를 저장할 수 있는 주소를 알려준다.
4.배열과 연결리스트
*배열:
- 메모리에 연속적으로 저장된다.
- 크기가 고정되어 있어 원소 추가에 제약이 있다.
- 처음부터 배열의 크기를 너무 크게 설정하면 메모리 낭비가 발생한다.
*연결리스트:
- 메모리에 불연속적으로 저장된다. 각 원소에는 다음원소에 대한 주소가 저장되어있다.
- 크기가 고정되어 있지 않다. (메모리 공간만 남아있다면) 언제든 원소 추가가 가능하다.
*배열 VS 연결리스트:
배열은
특정 원소에 대해 임의 접근 방식 (원소가 이웃하고 있어서 간단한 산수로 주소를 계산해 접근함.) O(1)
삽입/삭제시 원소의 이동이 많이 필요함 O(n)
연결리스트는
특정 원소에 대해 순차 접근 방식 (원소를 첫 번째부터 하나씩 읽어야함.) O(n)
삽입/삭제시 다음 원소의 주소만 변경하면 됨 O(1)
배열은 특정 원소에 접근이 쉽다.
연결리스트는 삽입/삭제가 쉽다.
5. 선택정렬
- [ N개의 원소에서 가장 작은 값을, N-1개 에서, ... ,2개 에서, 1개 에서 가장 작은 값을 찾음 ] => N번
- 총 N번 N개의 항목에서 가장 작은값을 찾는다
- O(n²)
void selection_sort(int[] arr,int len){
for(int i=0; i<len-1; i++){
int min_index = i;
for(int j=i+1; j<len; j++) //정렬되지 않은 항목에서 가장 작은 값 찾기
if(arr[min_index]>arr[j])
min_index = j;
if(arr[min_index] != arr[i]){ //제일 작은 값과 현재 값 교체
int tmp= arr[min_index];
arr[min_index] = arr[i];
arr[i] = tmp;
}
}
}
참고: Hello Coding 그림으로 개념을 이해하는 알고리즘