자료구조

자료구조란

  사전적 의미로는 자료(Data)의 집합을 의미하며, 각 원소들이 논리적으로 정의된 규칙에 의해 나열되며

  자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 구분하여 표현한 것이다.

  

  사용 목적으로는 자료를 더 효율적으로 저장하고, 관리하기 위해 사용하며 잘 선택된 자료구조는 실행시간을 단축시켜

  주거나 메모리 용량의 절약을 이끌어 낼 수 있다.

 

  자료의 처리를 보다 효율적으로 하기 위해서 처리시간, 자료의 크기, 활용빈도, 갱신정도, 프로그램의 용이성을

  고려하여 선택, 사용해야 한다.

 

특징

  1. 효율성

    자료구조의 목적은 효율적인 데이터의 관리 및 사용이다. 따라서 적절한 자료구조를 선택하여 사용한다면

    업무의 효율이 올라갈 것이다. 예를 들자면 데이터의 양이 많을 때 순차검색을 사용하는 것 보다 이분 검색을

    활용하는 것이 더 효율적이다. 이와같이 목적에 맞는 자료구조를 사용하는 것이 효율적이다.

 

  2. 추상화

    추상화란 복잡한 자료, 모듈, 시스템등으로부터 핵심적인 개념만 간추려 내는 것이다. 자료구조를 구현할 때 중요한

    것은 어느시점에 데이터를 삽입할 것이며, 어느 시점에 이러한 데이터를 어떻게 사용할 것인지에 대해서

    초점을 맞출수 있기 때문에 구현 외적인 부분에 더 시간을 쏟을 수 있다.  알고리즘 자체에는 중점을 두지 않는다.

    마찬가지로 자료구조 내부의 구현은 중요하지 않다. 어떻게 구현했는지보다 어떻게 사용해야 하는지를 알고 있어야

    한다. 예를 들어 어느 함수 내부 구현이 어떻게 되었는지는 중요하지 않다. 사람마다 다른 코드를 작성할 것이고,

    사용언어, 개발 툴등 환경적인 변수에 의해서 다른 코드가 나올것이기 때문에 추상적인 개념에 대해서만 이해하고

    있다면 사용할 수 있다.

 

  3. 재사용성

    자료구조를 설계할 때 특정 프로그램에서만 동작하게 설계하지는 않는다. 다양한 프로그램에서 동작할 수 있도록

    범용성 있게 설계하기 때문에 해당 프로젝트가 아닌 다른 프로젝트에서도 사용할 수 있다.

  

 

선형구조

  배열(Array), 연결리스트(Linked List), 스택(Stack), 큐(Queue)

 

비선형구조

  트리(Tree), 그래프(Graph)

 

프로그램의 성능 측정 방법론

  시간복잡도(Time Complexity)란 알고리즘에 사용되는 연산 횟수를 의미한다.

  공간복잡도(Space Complexity)란 알고리즘에 사용되는 메모리의 양을 의미한다.

  효율적인 알고리즘을 사용한다고 가정했을 때 일반적으로 시간과 공간은 반비례 관계이다.

  시간복잡도를 표현할때는 최악의 경우를 나타내는 Big-o표기법을 사용한다.

 

int main(void){
  int a, b;
  cin >> a >> b;
  int sum = 1;
  for(int i = 0; i < b; i++){
    sum += a;
  }
  cout << sum;
}

  위 알고리즘은 O(N)의 시간 복잡도를 가진다.

  i가 0부터 b까지 반복을 하는데 어떠한 변수만큼 반복한다고 해서 O(N)이라고 한다.

  

#include <iostream>

using namespace std;

int main(void){
  int n;
  cin >> n;
  for(int i = 0; i < n; i++){
    for(int j = 0; j <= i; j++){
      cout << "*";
    }
    cout << '\n';
  }
}

  이 알고리즘은 O(N^2)의 시간 복잡도를 가진다.

  이렇게 이중for문을 사용하는 경우는 n의 제곱만큼 반복이 되기 때문에 O(N^2)가 되는 것이다.

 

#include <iostream>

using namespace std;

int main(void){
  int a, b;
  cin >> a >> b;
  cout << a + b;
}

  이 알고리즘의 경우는 O(1)이다.

  그냥 a와 b를 더한 값을 바로 출력하기 때문에 1이다.

 

  N 이 1,000일 때

  N = 1,000번의 연산

  NlogN = 10,000번의 연산

  N^2 = 1,000,000번의 연산

  N^3 = 1,000,000,000번의 연산

 

  보통 연산횟수가 10억을 넘어가면 1초이상의 시간이 소요되기 때문에 10억을 넘기지 않도록 하는 것이 중요하다.

  사용자 입장에서는 1초가 굉장히 긴 시간처럼 느껴질 수 있기 때문이다.

  

  시간 복잡도를 표기할 때는 항상 큰 항과 계수만 표시한다.

  O(3N^2 + N) = O(N^2)

 

  공간복잡도는 일반적으로 MB단위로 표기한다.

  int a[1000] = 4KB

  int a[1000000] = 4MB

  int a[2000][2000] = 16MB

 

 

레퍼런스

패스트캠퍼스 올인원 패키지 - 소프트웨어 베이직