01. 자료구조와 알고리즘

- 학습목표

• 자료구조와 알고리즘의 개념을 이해한다
• 추상 자료형 도입의 필요를 이해한다
• 시간 복잡도의 개념을 이해한다
• 빅오 표기법에 의한 알고리즘 분석 기법을 이해한다
• 자료구조 표기법을 이해한다

1.1 자료구조와 알고리즘

자료구조란?

- 사람들이 사물을 정리하여 저장하는 것과 마찬가지로 프로그램에서도 자료들을 정리하여 보관하는 여러 가지 구조들이 있다. 이러한 구조들을 자료구조라 한다.

- 예를 들면, 해야할 일들을 중요도에 따른 내용들을 컴퓨터가 이해하려면 순차적으로 진행하는 List를 사용해야한다.

일상생활	자료구조
그릇, 연탄	스택
마트 계산대의 줄	큐
버킷 리스트	리스트
영어 사전	사전
지도	그래프
컴퓨터의 디렉토리 구조	트리

알고리즘이란?

- 컴퓨터로 문제를 풀기 위한 단계적인 절차

- 특정한 일을 수행하는 명령어들의 집합

- 알고리즘의 조건

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

자료구조와 알고리즘을 배워야하는 이유?

- 프로그램 = 자료구조 + 알고리즘 

- 예를 들어, 최대 값 탐색 프로그램 은 배열(자료구조) + 순차탐색(알고리즘) 을 이용하여 구현한다.

따라서 문제를 해결하려면 적합한 자료구조를 써야할지 알고, 구현 방법을 알아야한다. 

 

1.2 추상 자료형

* 추상화? 어떤 시스템의 간략화된 기술 또는 명세로서 정말 핵심적인 구조와 동작에만 집중하는 것
예를 들면, 내 이상형은 착하고 귀여운 사람 > 김철수 (추상화) 

추상 자료형이란?

- 실제적인 구현으로부터 분리되어 정의된 자료형 

- 구체적으로 구현하기 전에 자료형에 대한 자료의 특성, 연산자, 연산자가 무엇을 수행하는지 등을 논리적으로 정의하는 것

- 보통 ADT(추상자료형)이 구현 될 때 외부와의 인터페이스만 공개된다.

즉, ADT의 사용자는 인터페이스로만 접근이 가능하기 때문에, 언제든지 안전하게 변경가능하다.

예를 들면, 고리 라는 ADT가 있고, 사용자가 이 고리를 귀걸이로 쓸지, 코걸이로 쓸지 변경이 가능한 것

추상 자료형 구현방법?

- 객체지향언어에서는 "Class"개념을 사용하여 ADT를 구현가능하다.

- ADT의 객체는 클래스의 속성으로 구현되고, ADT의 연산은 클래스의 멤버함수로 구현된다. 

 

1.3 알고리즘 성능 분석

알고리즘 성능 분석 방법

• 수행시간 측정방법
  : 직접 구현 후 수행시간을 측정해야한다는 단점이 있다.
• 알고리즘의 복잡도 분석방법
  : 구현 없이도 모든 입력을 고려하고, 실행 환경과는 관계없이 평가 가능

알고리즘 복잡도 분석 종류

• 시간 복잡도(time complexity) > 보통 많이 사용
  : 알고리즘의 수행 시간 분석
• 공간 복잡도(space complexity)
  : 알고리즘을 이루고 있는 연산들이 몇 번이나 수행되는지

 

연산들의 수행 횟수는 입력의 개수 n에 따라 변하게 된다.

따라서 연산의 수를 입력의 개수 n의 함수로 나타낸 것을 시간복잡도 함수라 하며 T(n)으로 표기한다.

 

빅오표기법?

- 시간 복잡도 함수에서 불필요한 정보를 제거하여 알고리즘 분석을 쉽게 하기 위해 시간 복잡도를 표시하는 방법

- 자료의 개수가 큰 경우에는 차수가 가장 큰 항이 전체의 값을 주도한다.

- 위와 같이, 빅오 표기법을 사용하면, 시간 복잡도를 간단하게 표시 할 수 있다.

- 주의할 점은 log n은 없애면 안된다. 

 

빅오 표기법 종류