[Panda] 01. 자료구조와 시간복잡도

01. 자료구조란?

자료구조: 데이터(자료)에 효율적으로 접근하고 수정할 수 있도록 저장, 조직, 관리하는 방법에 관한 이론

알고리즘: 문제 해결 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어내는 과정을 기술한 것

 

자료구조는 문제 해결에 사용할 부품

자료구조는 알고리즘에서 부품 같은 역할을 한다.

자료구조를 몰라도 프로그램을 작성할 수 있다. 그러나 자료 구조를 모르고 프로그램을 작성하는 것은 재료의 속성이나 구조물의 구성 방법을 모르고 건축물을 만드는 것이다.

자료구조에 대해 잘 이해하고 있어야 적절한 곳에 적절한 코드 사용 및 조합하고 내구성 있는 프로그램을 만들 수 있다.

 

자료구조를 구현, 사용, 결합하는 과정에서 수학적 사고(특히 이산수학)도 크게 도움된다. 사고가 체계적일 수록 자료구조를 사용한 결과물은 간명하고 관리하기 쉬워진다.

자료구조는 운영체제, 컴퓨터 네트워크, 인공지능, 시스템 프로그래밍, 컴파일러 등 컴퓨터 고하ㅏㄱ의 거의 모든 주제를 구현하기 위한 사고의 빌딩 블록을 제공한다.

 

 

자료구조는 생각하는 방법을 훈련하는 도구

자료구조는 그 자체를 공부하는 것도 중요하지만 자료구조를 다른 과정에 포함된 생각하는 방법도 매우 중요하다.

자료구조를 구현하는 과정, 자료구조들을 이용해서 문제를 해결하는 과정, 문제를 해결하는 과정에서 논리의 골격이 구성되는 방법 또는 스타일 등이 이에 해당한다.

 

문제해결을 위한 생각과정에서 의미 단위를 잡는 일(=의미의 매듭을 만드는 일)은 매우 중요하다.

큰 프로젝트를 여러 모듈로 분해하면 각 모듈이 의미의 매듭이 되고 각 모듈은 더 작은 모듈로 나뉠 수 있다.

프로그래밍에서 어떤 작업을 함수로 만드는 것도 모듈화의 일종이다. 함수를 분리하면 강한 의미 단위가 된다.

 

의미의 매듭을 만드느 과정(=모듈화 과정)에서 여러 가지 생각의 구조가 개입될 수 있는데 가장 중요한 구조 중 하나가 재귀이다. 재귀는 컴퓨터 과학 전반에 걸쳐 가장 중요한 사고 체계 중 하나다.

재귀: 어떤 문제가 자신과 성격이 똑같고 크기만 더 작은 문제를 포함하고 있는 구조

 

 

자료구조에는 여러 가지 종류가 있고 상황과 목적에 맞는 적절한 자료구조를 선택함으로써 효율적인 데이터 관리가 가능하다. 자바의 경우 클래스 종류별 패키지로 분류되어있는데 그 중 컬랙션 패키지에 자료구조 관련 클래스들을 모아 두었다.

효율적인 코딩을 위해 직접 자료구조를 만든 것이 나을 때도 있고 이미 만들어져있는 것을 활용해야할 때도 있다.

자료구조 내부 작동원리를 잘 이해하고 있어야 두 경우 중 잘 선택하여 코딩할 수 있다.

 

 

02. 자료구조와 알고리즘

알고리즘: 문제 해결 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어내는 과정을 기술한 것

자료구조는 알고리즘의 직전 단계이기도 하고 자료구조 자체로 여러 알고리즘을 포함하기도 한다.

 

알고리즘을 만들 때는 명시된 입력으로부터 워하는 출력을 만들어내는 과정을 애매하지 않게 기술해야한다.

알고리즘은 아래와 같이 다양한 방법으로 표현할 수 있다.

• 자연어를 이용한 서술적 표현: 자연어는 쓰는 사람에 따라 일관성이나 명확성을 유지하기 어려움
• 순서도를 이영한 도식화: 명령의 흐름을 쉽게 파악할 수 있지만 복잡한 알고리즘을 표현하는데는 한계가 있음
• 프로그래밍 언어를 이용한 구체화: 추가로 구체화해야할 필요가 없지만 해당 언어를 모르면 이해하기 어려우며 다른 프로그래밍 언어로 개발 시 범용성이 떨어짐
• 가상코드를 이용한 구체화: 일반적인 프로그래밍 언어와 형태가 유사해 원하는 특정 프로그래밍 언어로 구체화하기 쉬움

 

03. 자료구조의 추상 데이터 타입

추상

미술에서 추상화: 사물의 사실적 재혆이 아니라 순수하게 점, 선, 면, 색체의 순수한 조형적 요소로 구성한 그림

음악에서 추상음악: 특정한 이미지나 상징적인 의미를 표출하려하지 않고 오직 음과 음의 관계와 조합을 통해 순수한 예술성을 추구하는 음악

 

프로그래밍에서 추상

관점이 계층화되면서 상승한 것, 하위의 개념들을 결합하여 상위의 고급 개념을 만들어나가는 지적 발전의 단계

계층화의 단계가 높으면 추상화의 레벨이 높은 것

프로젝트나 문제 해결 과정에서는 새로운 의미 단위를 분리하고 계층화하는 작업이 반복된다.(예: 객체지향 언어의 클래스)

 

의미의 단위를 흔히 모듈이라한다.

모듈은 먼저 추상적인 레벨에서 설계되고, 후에 구체화 된다. 모듈을 추상화한다는 것은 세부 사항을 생략하고 가장 주요한 기능만 드러내는 것을 말한다. 추상화는 위에서-아래로 이루어질 수 도 있고, 아래에서-위로 이루어질 수도 있다.

• 위에서-아래로: 큰 그림을 먼저 그리고 점차 작은 모듈로 나누어가는 과정
• 아래에서-위로: 최하부 단위들을 준비하고 거기서부터 선택과 조합, 새로움을 가미하여 상위레벨의 그림을 만들어내는 과정

 

추상 데이터 타입: ADT

자바는 byte, short, int, long, float, double, boolean, char 이렇게 총 8가지의 기초 데이터 타입을 제공한다.

이런 기초 데이터 타입이 아닌 데이터 타입에는 대부분 추상적 성격이 있다. 어떤 성질을 공유하는 객체들의 집합은 하나의 데이터 타입을 이루기 좋은 후보이다.

 

추상 데이터 타입(Abstract Data Type): 세부사항에서 벗어나 추상적으로 정의한 데이터 타입

• 추상적으로 표현한다:어떤 대상이 지원하는 작업을 나열해 표현
• 추상 데이터 타입: 어떤 데이터 타입이 어떤 작업으로 이루어지는지만 표현한 것

자바에서 8가지 기초 데이터 타입을 제외한 나머지는 추상데이터 타입이고 추상 데이터 타입은 대략 하나의 클래스에 대응된다. 클래스는 자신의 규칙을 따르는 객체를 만들기 위한 틀이다. 클래스는 암묵적으로 그런 객체들의 집합을 의미하기도 해서 하나의 데이터 타입이라 부르기도 한다. 한의 ADT 아래에 여러 ADT가 포함될 수 도 있다. 인터페잇가 ADT에 가장 잘 대응되는 개념이다.

 

ADT를 사용하므로써 자료구조 내부의 세세한 사항에 신경을 쓰지 않고 효율적이고 고급스럽게 프로그래밍 작업을 할 수 있도록 한다. 즉 자료구조가 하는 일만 생각하며 작업할 수 있고 이로 인해 협업도 원활해진다.

ADT는 내부에서 작업을 '어떻게' 하는지 신경쓰지 않게 하며 '무엇을' 하는지만 신경쓰게 해준다.

 

 

04. 알고리즘 수행시간이란?

알고리즘의 효율성은 자원을 얼마나 효율적으로 사용하는가로 판단한다.

자원: 시간, 저장 공간, 네트워크 대역 등

대표적인 자원은 시간이며 알고리즘의 성능 즉 복잡도는 대부분 수행시간과 관련되어 있다.

 

알고리즘의 수행 시간은 입력의 크기에 대해 시간이 얼마나 걸리는지로 표현한다.

예시)

입력 배열의 크기 n에 상관없이 일정한 시간(상수 시간이 소요)

for루프를 제외한 나머지 부분은 상수시간이 소요, for루프가 시간을 지배

for루프에서는 단순 덧셈만 수행하믈 상수시간이 소요되므로 for루프 과련수행시간은 n에 비례

for루프가 중첩되어 n^2번 반복되고 각 루프에서는 덧셈과 곱셈, 즉 상수 시간 작업이 수행된다.

알고리즘의 총 수행시간은 n^2에 비례

 

 

05. 알고리즘 복잡도

점근적 복잡도: 입력의 크기가 충분히 클 때의 복잡도

알고리즘의 복잡도를 나타낼 때는 점근적 표기를 쓴다. 입력이 크기가 작으면 복잡한 알고리즘이든 효율적인 알고리즘이든 실제 수행시간은 별 차이가 나지 않는다.

따라서 점근적 복잡도 분석에서는 최고차항의 차수만 중요하고 나머지는 다 무시한다.

n이 충분히 크면 그 앞에 상수를 곱하든 곱하지 않든 그 차이는 차수의 차이에 비하면 미미하기 때문이다.

 

 

점근적 복잡도 중 다음 세 가지 표기법이 대표적이다.

 

 

• O- 표기: 점근적 상한, 프로그램이 실행될 때 최악의 경우
• Ω- 표기: 점근적 하한, 프로그램이 실행될 때 최선의 경우
• ⊖- 표기: 점근적 동일, 두 표기의 교집합 평균적인 연산 횟수