알고리즘 !! 시간복잡도 & 자료 구조 & 정렬

시간복잡도

알고리즘의 로직을 코드로 구현할 때, 시간 복잡도를 고려한다는 것은 바꿔 말해 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가? 라는 말이다. 

Big-O 표기법 : 입력값의 변화에따라 연산을 실행할때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가? 를 표기하는 방법.

• Big-O(빅-오) ⇒ 상한 점근 (최악의 경우)
• Big-Ω(빅-오메가) ⇒ 하한 점근 (최선의 경우)
• Big-θ(빅-세타) ⇒ 그 둘의 평균 

가장 자주 사용되는 표기법. 최악의 경우도 고려해 대비하는 것이 바람직하다.

 

Reference

https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-time-complexity-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84/

[알고리즘] Time Complexity (시간 복잡도) - 하나몬

 

자료구조

데이터 값의 모임, 각 원소들이 논리적으로 정의된 규칙에 의해 나열되며 자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 구분하여 표현한 것.

메모리 공간을 효율적으로 사용해야 하는데 필요한 것이 자료 구조이다.

 

필수 자료구조 

1. Array(배열) - 동일타입 데이터 저장, 고정된 크기 갖음, 인덱싱 되어 인덱스 번호로 접근 가능

2. Linked List - 각 데이터 시퀀스가 순서를 가지고 연결된 순차적 구조. 동적 데이터 추가/삭제에 유리.

3. Stack 스택 - 순서 보존되는 선형 데이터 구조. 가작 마지막 요소( 가장 최근 요소 ) 부터 처리하는 LIFO

4. Queue (큐) - 가장 먼저 입력된 요소를 처리하는 (First In First Out)

5. Hash table - 해시함수를 사용해 변환한 값을 index삼아 키와 데이터를 저장하는 자료구조. 삽입, 검색에 매우 효율적

6. Graph - 소셜 미디어 네트워크, 검색 엔진에 의해 웹 페이지 및 링크를 나타내는 데 사용, GPS에서 위치, 경로 나타내는데 사용

7. Tree -  그래프가 계층적 구조를 가진 형태, 최상위 노드를 가지고 있음. 사우이 노드를 부모, 하위노드를 자식이라 한다.

8. Heap 

최소 힙: 부모 키 값이 자식 키 값보다 작거나 같다

최대 힙: 부모 키 값이 자식 키 값보다 크거나 같다.

 

Reference

https://bnzn2426.tistory.com/115 [보통의 개발자:티스토리]

자료 구조(Data Structure) 개념 및 종류 정리

 

정렬 알고리즘

1. 선택정렬 (Selection Sort) : 자리가 정해져있음. 첫번째 자리에 가장 작은 값을 넣고 오름차 순으로 정렬.

void selectionSort(int arr[], int size) {
    int minIndex;
    int i, j;
    for (i = 0; i < size - 1; i++) {
        minIndex = i;
        for (j = i + 1; j < size; j++) 
            if (arr[j] < arr
[minIndex])
                minIndex = j;
         
        swap(&arr[i], &arr[minIndex]);
    }
}

2. 버블 정렬

현재 배열 요소, 그다음 배열 요소를 비교하고 조건에 걸리면 교환하는 식. 배열의 0번째 인덱스의 요소와 1번째 인덱스의 요소를 비교, 그다음 1번과 2번을 비교하고....반복.

void bubbleSort(int arr[], int size) {
    int i, j;
    for (i = size - 1; i>0; i--) 
        for (j = 0; j<i; j++) 
            if (arr[j]<arr[j + 1]) 
                swap(&arr[j], &arr[j + 1]);
}

3. 삽입정렬

배열의 한 원소이는 key라는 값을 가지고 있고, 이 key를 알맞은 자리에 삽입하면 된다. key보다 큰 값은 하나 하나씩 밀어버리고 key보다 작은 값을 만났을 때 그 뒷자리에 삽입.

 

 

Reference

https://reakwon.tistory.com/37

[알고리즘] 기본 정렬 알고리즘( 선택정렬, 버블정렬, 삽입정렬)