(알고리즘이해 -1) 자료구조와 알고리즘이란 무엇인가?

• 알고리즘 -> 프로그램을 어떻게 작성하면 “좋은 프로그램”을 만들 수 있을까?

1. 자료구조와 알고리즘이란 무엇인가?

 

❓ 프로그램이란?

- 컴퓨터를 다양한 용도로 사용할 수 있도록 해주는 것

- 게임 프로그램, 문서 작업 프로그램, 그림 그리기 프로그램 등

- 컴퓨터라는 하드웨어 에서 우리가 원하는 일을 하도록 해주는 것

 

❓ 좋은 프로그램이란?

- 주어진 문제가 다루어야 할 자료들을 효과적으로 보관할 적합한 자료구조를 선택하고, 자료구조에 보관된 자료들을 효율적으로 처리하는 알고리즘을 반영하여 작성된 프로그램

- 결론적으로 실행 속도가 빠르고 컴퓨터 메모리 사용도 효율적인 프로그램

 

❓ 일반적인 프로그램 개발 과정

문제 정의 -> 자료정의(자료 처리 방식 정의) -> 자료구조(알고리즘) -> 프로그램 작성

 

❓ 자료구조란?

- 프로그램이 다루어야 하는 자료를 프로그램 상에서 표현하는 형태를 말한다.

- 주어진 문제에 가장 효과적인 자료구조를 선택해야 프로그램의 실행 속도도 빨라지는 좋은 프로그램을 작성할 수 있게 되는 것이다.

 

❓ 알고리즘이란?

- 주어진 문제에 적합한 자료구조가 결정되고 나면 자료구조에 보관된 자료들을 효율적으로 처리하는 방법들을 생각하게 되는데, 이를 알고리즘이라고 한다.

- 더 넓게 생각하면 "좋은 프로그램을 만드는 아이디어"

 

❗️ 일상생활에서의 자료구조와 알고리즘의 예

- 도서관의 예

수많은 책들을 아무런 원칙 없이 서가에 꽂아 두었다면, 내가 원하는 책을 찾기가 정말 어려울 것이다.보통의 도서관에서는 책들을 크게 종류별로 분류하여 따로 보관하고 그 종류 내에서도 도서명 순서와 같은 어떤 원칙하에 서가에 분류, 보관해 둠으로써 원하는 책을 쉽고 빠르게 찾을 수 있도록 하고 있다

 

❓ 공간복잡도와 시간복잡도

- 좋은 알고리즘이라는 것은 어떻게 객관적으로 평가할 수 있을까?

- 일반적으로 프로그램이 상요한 알고리즘의 메모리 사용량과 비교와 수행 시간의 비교를 가장 기본적으로 보게 된다

- 이를 각각 공간복잡도(space complexity), 시간 복잡도(time complexity)라고 한다.

 

❓ 공간복잡도

- 알고리즘이 사용하게 될 메모리 용량의 크기

 

❓  시간복잡도

- 알고리즘이 수행되어 작업을 완료하는 데 걸리는 시간

- 처리해야 할 자료의 양 혹은 개수(n이라고 하자,)가 많으면, 그에 비례해서 알고리즘의 수행시간은 당연히 늘어나게 될 것이다.

- 따라서, 시간복잡도라는 개념이 "정확히 얼마만큼의 시간이 걸린다." 를 측정하는 것이 아니라 처리해야 할 자료의 양(혹은 갯수 n)과 관련해서 얼마만큼의 알고리즘의 수행시간 비례관계를 가지느냐를 살펴보는 개념이다.

 

❓  빅-오(BIG-OH)표기법

- O(n)이라고 표현한다.

- 빅-오 표기법의 의미는 그 알고리즘의 수행 시간 상한을 뜻한다.

- 최악의 경우에도 그 만큼의 시간 비례 내에는 수행이 완료된다는 것을 의미한다.

- 보통 알고리즘의 시간복잡도를 표현할 때 가장 많이 사용하는 표기 법이다.

tip) 세타 표현과 오메가 표현도 사용하기도 한다.

 

❓  일반적인 자료구조의 종류

- 개발해야 할 프로그램의 종류는 무수히 많지만, 그런 수많은 프로그램에서 사용할 수 있는 기본적 자료구조의 종류는 대체적으로 분류하여 공부할 수 있다.

(사진첨부)