자료구조와 알고리즘이란?

자료구조란?

– 프로그래밍 중 처리 해야할 객체들과 그들의 속성 파악하고,

처리 연산들을 정의하고 구현하는 것에 대한 체계적이고, 효율적인 방법을 연구하는 것 이다.

 

자료구조 모델링 과정

▶논리적 자료 추상화(logical data absraction)

– 현실세계의 자료 객체를 처리 목적에 고려하여 사람들이 정확하게 인식하고 이해할 수 있는 요약된 논리이다.

– 자료 객체들의 모든 실제 속성과 연산들을 표현하는것이 아닌 필요한 속성들과 연산들을 상실하지 않는 범위에서

최대한 요약해서 표현한 것이다.

 

▶물리적 자료 추상화(physical data abstraction)

– 논리적 자료 추상화를 프로그래밍 구현을 통해 실제 컴퓨터 내부  메모리에 효율적으로 저장해서 관리하는것이다.

– 자료 객채들의 논리적 구조가 가진 의미를 상실하지 않는 범위에서 가능하면 메모리를 적게 사용하고, 필요할 때 신속하게 자료에 접근할 수 있는 방법을 고려해야 한다.

 

알고리즘이란?

– "컴퓨터를 이용한 문제 해결방법"

 

알고리즘의 구성요소

▶입력(input) – 외부에서 제공하는 정보이다.

▶출력(output) – 알고리즘을 수행한 결과이다.

▶명확성(definiteness) – 내용이 명확해야 한다.

▶유한성(finiteness) – 알고리즘은 유한개의 순서로 구성되어야 한다.

▶효율성(effectiveness) – 합리적이고 실현 가능해야 한다.

 

알고리즘의 성능분석

▶공간복잡도(space complexity)

– 프로그램을 수행하기 위하여 필요한 메모리 정도

– 가급적 적은 메모리를 사용해야 한다.

– (예) 10,000*10,000 정수형 배열을 저장하기 위해 필요한 메모리는?

 

▶시간복잡도(time complexity)

– 프로그램을 수행하는데 걸리는 시간 정도

– 가급적 빠른 시간 내에 원하는 작업을 수행해야 한다.

– (예) 2100 번 연산을 수행하기 위해 필요한 시간은?