(22.08.06)자료구조 1 - 도입

교재 : 윤성우의 열혈 자료구조

언어 : C

장소 : 중앙도서관 스터디룸

멤버 : 이준표, 최이섭

 

• 자료구조를 배워야 하는 이유
• 자료구조의 종류
• 시간 복잡도

 

자료구조를 배워야 하는 이유

 

자료구조란 '데이터의 표현 및 저장 방법' 을 의미한다면,

알고리즘은 자료구조를 대상으로 하는 '문제의 해결 방법'을 의미한다.

    int arr[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

위와 같은 배열 선언은 '자료구조'적 측면의 코드라고 할 수 있다.

반면, 다음과 같은 코드는 '알고리즘'적 측면의 코드다. (데이터의 합을 구하는)

    for (int i = 0; i < n; ++i) {
        sum += arr[i];
    }

보다시피 알고리즘에는 자료구조가 필연적으로 사용된다.

위의 알고리즘은 배열을 사용한 알고리즘이다.

만약, 배열이 아니었다면 인덱스를 이용한 순차적 접근을 이용하지 않았을 수도 있다.

 

예를 들어서, 큐를 이용한다면

    while (!q.empty()){
        sum += q.front();
        q.pop();
    }

합을 구하기 위해서 다음 알고리즘을 짤 수도 있다.

 

즉, 알고리즘은 자료구조에 의존적이기 때문에 알고리즘 학습을 위해서는 자료구조의 학습이 선행되어야한다.

 

자료구조의 종류

자료구조는 크게 선형, 비선형으로 나뉜다.

• 선형자료구조
  • 리스트
  • 스택
  • 큐
• 비선형자료구조
  • 트리
  • 그래프

 

 

시간 복잡도

알고리즘을 실행하는데 걸리는 시간을 대략적으로 표기한 것으로 시간적인 효율성을 판단, 평가하는 척도로서 사용되는 것

시간 복잡도의 대표적인 표기법이 바로 Big-Oh Notation이다.

시간 복잡도 그래프 (출처: https://www.bigocheatsheet.com/)

시간 복잡도는 n^2 -> nlogn 까지만 낮춰도 매우 효율적으로 동작한다.

또한, 자료구조마다도 접근, 검색, 삽입, 삭제의 시간복잡도가 각각 다르다.

자료구조의 시간복잡도 (출처: 상동)

• Red-Black Tree는 모든 연산에 대해 logn의 시간복잡도를 가진다. (map, set이 red-black tree 구조를 사용한다.)

*참고로 위 링크에서 배열을 정렬하는 알고리즘의 시간복잡도도 확인할 수 있다.