[CS과목/자료구조] 01 자료구조와알고리즘

교재: C언어로 쉽게 풀어쓴 자료구조 개정 3판 (2019, 천인국 외)

 

1.1 자료구조와 알고리즘

자료구조란?
  사람들이 사물을 정리하여 저장하는 것과 마찬가지로 프로그램에서도 자료들을 정리하여 보관하는 여러 가지 구조들이 있다. 이를 자료 구조(data structure)라 부른다.

알고리즘이란?
  컴퓨터로 문제를 풀기 위한 단계적인 절차를 알고리즘(algorithm)이라고 한다. 엄밀하게 이야기하면 알고리즘이란 문제와 컴퓨터가 주어진 상태에서 문제를 해결하는 방법을 정밀하게 장치가 이해할 수 있는 언어로 기술한 것이다. 따라서 알고리즘은 특정한 일을 수행하는 명령어들의 집합이다.

 

• 입   력: 0개 이상의 입력이 존재하여야 한다.
• 출   력: 1개 이상의 출력이 존재하여야 한다.
• 명백성: 각 명렁어의 의미는 모호하지 않고 명확해야 한다.
• 유한성: 한정된 수의 단꼐 후에는 반드시 종료되어야 한다.
• 유효성: 각 명렁어들은 종이와 연필, 또는 컴퓨터로 실행 가능한 연산이어야 한다.

1.2 추상 자료형

  자료형(data type)이란 용어 그대로 "데이터의 종류"이다. 우리는 이 과목에서 스택, 큐, 리스트, 트리와 같은 새로운 자료형들을 추가할 것이다. 자료형을 작성할 때는 실행 가능한 연산에 대해서도 신경 써야 한다. 데이터의 종류가 결정되면 그 데이터와 관련된 연산도 달라진다. 복잡한 자료형을 구현할 때는 연산이 연산자가 아니고 함수(function)로 작성된다.
  추상 자료형(ADT: abstract data type)이란 추상적, 수학적으로 자료형을 정의한 것이다. 자료구조는 이러한 추상 자료형을 프로그래밍 언어로 구현한 것이라 할 수 있다. 추상화란 어떤 시스템의 간련화된 기술 또는 명세로서 시스템의 정말 핵심적인 구조나 동작에만 집중하는 것이다. ADT는 실제적인 구현으로부터 분리되어 정의된 자료형을 말한다. 즉 자료형을 추상적(수학적)으로 정의함을 의미한다. ADT 안에는 객체(objects)와 함수(functions)들이 정의된다. 객체는 주로 집합의 개념을 사용하여 정의된다. 이후에 함수들이 정의된다. 함수는 앞에서 언급한 연산을 의미한다.

1.3 알고리즘의 성능 분석

시간 복잡도 함수
  프로그램의 효율성은 중요하다. 그 이유는 최근 상용 프로그램의 규모가 이전에 비해 엄청나게 커지고 있기 때문이다. 즉 처리해야할 자료의 양이 많기 때문에 알고리즘의 효율성이 더욱 중요하게 된다. 알고리즘 분석에서는 2가지의 측면을 고려할 수 있다. 즉 알고리즘의 수행시간과 알고리즘이 필요로 하는 기억공간의 양이 그것이다. 알고리즘의 수행시간 분석을 시간 복잡도(time complexity)라고 하고 알고리즘이 사용하는 기억공간 분석을 공간 복잡도(space complecity)라고 한다. 우리가 알고리즘의 복잡도를 이야기할 때 대개는 시간 복잡도를 말한다. 시간 복잡도는 알고리즘의 절대적인 수행 시간을 나타내는 것이 아니라 알고리즘을 이루고 있는 연산들이 몇 번이나 수행되는지를 숫자로 표시한다. 연산들의 수행횟수는 보통 프로그램에서 주어지는 입력의 개수 n에 따라 변하게 된다. 따라서 일반적으로 연산의 수행횟수는 고정된 숫자가 아니라 n에 대한 함수가 된다. 이를 T(n)이라고 표기한다.

빅오 표기법
  시간 복잡도 함수에서 불필요한 정보를 제거하여 알고리즘 분석을 쉽게 할 목적으로 시간 복잡도를 표시하는 방법을 빅오 표기법이라고 한다. 이를 O(n)이라고 한다. O(n)은 "빅오 of n"이라고 읽는다. 빅오 표기버은 n의 값에 따른 함수의 상한값을 나타내는 방법이다.

• 두 개의 함수 f(n)과 g(n)이 주어졌을 때 모든 n > n_0에 대하여  |f(n)| <=c|g(n)|을 만족하는 2개의 상수 c와 n_0가 존재하면 f(n)=O(g(n))이다.

 다음은 많이 쓰이는 빅오 표기법을 순서대로 표시한 것이다.

• O(1): 상수형
• O(logn): 로그형
• O(n): 선형
• O(nlogn): 선형로그형
• O(n^2): 2차형
• O(n^3): 3차형
• O(2^n): 지수형
• O(n!): 팩토리얼형

  다음은 빅오 표기법에 의한 알고리즘의 수행시간을 비교한 것이다.

• O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(2^n)<O(n!)

https://www.bigocheatsheet.com/

최선, 평균, 최악의 경우
  최악의 경우의 수행시간이 알고리즘의 시간 복잡도 척도로 많이 씅니다. 최악의 경우란 입력 자료 집합을 알고리즘에 최대한 불리하도록 만들어서 얼마만큼의 시간이 소모되는 지를 분석하는 것이다. 최선의 경우는 알고리즘에 따라서 별 의미가 없는 경우가 많다.