자료 구조 - 시작
‘c++로 쉽게 풀어쓴 자료구조 1판 - 천인국, 최영규’ 책을 참고하여 작성한 포스트입니다.
자료구조
자료구조란?
- 자료들을 편리하고 효율적으로 처리하기 위해 정리하고 조직화하는 구조이다.
자료구조의 분류
자료구조는 단순 자료구조와 여러 가지 자료들이 복합적으로 구성된 복합 자료구조로 나눌 수 있다.
- 단순 자료구조 : 정수, 실수, 문자, 문자열, 포인터 같이 많은 프로그래밍 언어에서 기본적으로 제공하는 단순 자료구조
- 복합 자료구조 : 여러 가지 자료들이 복합적으로 구성된 자료구조이며, 선형 구조와 비선형 구조로 나눌 수 있다.
선형 자료구조(linear data structure)
- 선형 자료구조는 기본적으로 자료들이 순서적으로 나열된다. 배열, 연결 리스트, 스택, 큐, 덱 등이 이에 해당한다. 접근하는 방법으로 순서 접근(sequential access)과 직접 접근(direct access) 방법으로 나눌 수 있다. 대표적인 직접 접근 방법으로 배열이 있으며, 순서 접근 방법으로는 연결 리스트가 있다
비선형 자료구조(non-linear data structure)
- 자료들 간에 선형적인 순서가 있는 것이 아니라 보다 복잡한 연결을 갖는 형태로 트리와 그래프 등이 여기에 속한다.
자료구조의 활용
- 컴퓨터에서 다양한 자료구조를 활용하는 대표적인 사례가 정렬과 탐색이다. 정렬은 주어진 자료들을 어떤 기준을 바탕으로 순서대로 나열한다. 효율적인 정렬을 위해 다양한 자료구조의 활용이 필요하다. 적절한 자료구조와 그에 따른 알고리즘을 사용하는 경우 효율적인 탐색이 가능하다.
알고리즘(algorithm)
어떤 문제를 해결하는 절차. 컴퓨터에선 주어진 상태에서 문제를 해결하는 방법을 장치가 이해할 수 있는 언어로 정밀하게 기술한 것이다. 즉, 특정한 일을 수행하는 명령어들의 집합이다.
알고리즘의 조건
- 입 력 : 0개의 이상의 입력이 존재해야 한다.
- 출 력 : 1개 이상의 출력이 존재해야 한다.
- 명백성: 각 명령어의 의미는 모호하지 않고 명확해야 한다.
- 유한성: 한정된 수의 단계 후에는 반드시 종료되어야 한다.
- 유효성: 각 명령어들은 실행 가능한 연산이어야 한다.
추상 자료형
추상화란?
복잡한 자료, 모듈, 시스템 등으로부터 핵심적인 개념이나 기능을 간추려 내는 것을 말한다. 시스템의 핵심적인 구조나 동작에만 집중하는 것이다.
좋은 추상화는 사용자에게 중요한 정보는 강조되고 그렇지 않은 세부 사항은 제거되는 것이다.
추상 자료형(ADT: Abstract Data Type)
자료의 집합과 자료에 가해지는 연산들을 정의하는 것이다. 자료의 구체적인 표현을 숨겨 프로그래머가 자료의 구조와 연산에만 집중할 수 있도록 하여 프로그램의 구조를 단순화하고 이해하기 쉽게 한다.
추상 자료형을 표현할 때는 먼저 데이터를 정의하고, 다음으로 연산들을 정의한다. 데이터는 주로 집합의 개념을 사용하여 표현하고, 연산의 정의에는 연산의 이름, 매개변수, 연산의 결과, 연산이 수행하는 기능 등을 기술한다.
간단한 인터페이스(interface)만 제공함으로써 구현에 관한 세부사항들은 외부에서 모르게 한다. 추후에 구현 방법이 변경되더라도 인터페이스만 정확하게 지켜진다면 사용자는 변경된 내용을 알 필요도 없고 사용하는데 문제도 없다.
‘구현으로부터 명세의 분리’가 추상 자료형의 중심 아이디어다.
추상자료형과 c++
- 추상 자료형에서의 데이터는 클래스의 속성(멤버 변수)으로 구현되고 연산은 클래스의 메소드(멤버 함수)로 구현된다.
private나protected키워드를 통해 접근을 제한할 수 있다.
알고리즘의 성능 분석
- 효율적인 알고리즘이란 전체 실행 시간이 짧으면서 메모리와 같은 컴퓨터의 자원들을 적게 사용하는 알고리즘이다. 일반적으로 실행 시간이 메모리 공간보다 더 중요하게 생각된다. 시간 복잡도가 알고리즘의 성능에 더 큰 영향을 미치기 때문이다.
알고리즘의 복잡도 분석 방법
알고리즘을 직접 구현하지 않고 대략적인 효율성을 분석하는 방법이다. 실행 하드웨어나 소프트웨어 환경과는 관계없이 알고리즘의 효율성을 평가할 수 있다.
알고리즘의 실행 시간 분석을 시간 복잡도(time complexity)라고 하고, 알고리즘이 사용하는 기억 공간 분석을 공간 복잡도라고 한다.
일반적으로 알고리즘의 복잡도는 대개 시간 복잡도를 얘기하므로 시간 복잡도에 집중하여 정리하겠다.
빅오 표기법
일반적으로 시간 복잡도 함수 $T(n)$은 입력의 개수 $ n$ 에 대한 상당한 복잡한 수식으로 나타날 수 있다. 그러나 n이 커질수록 차수가 가장 큰 영향이 절대적이 되고 다른 항들은 무시될 수 있을 정도로 작아진다.
시간 복잡도 함수에서 중요한 것은 $ n$이 증가함에 따라 무엇에 비례하는 수의 연산이 필요한가 이다.
시간 복잡도 함수에서 불필요한 정보를 제거하여 알고리즘 분석을 쉽게 할 목적으로 시간 복잡도를 표시하는 방법을 빅오 표기법이라 한다.
빅오표기법
두 개의 함수 $ f(n) $과 $ g(n) $이 주어졌을 때 모든 $ n > n_0 $ 대하여 $ |f(n)|<=c|g(n)|$을 만족하는 상수$ c$와 $ n_0$가 존재하면 $ f(n) = O(g(n))$이다.
빅오 표기법은 상한을 표기한 것이므로 상한은 여러 개가 존재할 수 있다. 그래서 빅오 표기법은 최소 차수 함수로 표기되었을 때 의미가 있다.
빅오 표기법을 얻는 간단한 방법은 다항식의 최고차항만을 남기고 다른 항들과 상수항을 버리는 것이다. 최고차항의 계수도 버리면 된다.
빅세타, 빅오메가도 있다. 빅세타는 알고리즘의 평균적인 경우 시간 복잡도이며, 빅오메가는 최선의 경우 시간 복잡도이다.
평균적인 실행시간이 가장 좋아 보이지만 계산하기 어려운 경우가 많으며, 최악의 상황에 대한 시간을 보장하지 못한다는 점에서 문제가 있어 빅오 표기법을 주로 사용한다.
# 문제
Leave a comment