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

---

본 내용은 지식공유자 감자님의 강의를 기반으로 만들어진 글입니다. 

추후 문제가 있을시 삭제 될 수 있음을 알립니다.

 

 

 

---

 

프로그램은 자료구조와 알고리즘으로 나뉜다.

 

자료구조

자료구조는 데이터가 어떤 구조로 저장되고 어떻게 사용되는지 나타낸다.

 

 

프로그래밍을 경험했다면 우리는 이미 자료구조를 사용했다?

변수 : 숫자나 문자를 저장하기 위해 → 저장한 문자, 숫자등 변수를 사용하고 단순히 사용가능하다

배열→ 연속적으로 선언 후 인덱스를 통해 접근한다.

• 3개의 변수를 선언하고 평균을 구하는 방법

단일변수

int a = 87;
int b = 70;
int c = 100;
int avg = 0;

avg = (a+b+c) / 3;

cout << avg << endl;

 

배열

int arr[] = {87, 70, 100};
int avg = 0; 

for (int i = 0; i < size(arr); i++) {
		avg += arr[i];
}

avg /= size(arr);
cout << avg << endl;

 

데이터를 변수에 저장 또는 배열에 저장 방식에 따라 처리방법이 달라진다.

모양도 사용방법도 다르다

 

 

 

4개의 데이터의 평균을 구해보자

int a = 87;
int b = 70;
int c = 100;
int d = 55;
int avg = 0;

avg = (a+b+c+d) / 3;

cout << avg << endl;

int arr[] = {87, 70, 100, 55};
int avg = 0; 

for (int i = 0; i < size(arr); i++) {
		avg += arr[i];
}

avg /= size(arr);
cout << avg << endl;

• 이런식으로 유지보수가 어떻게 코드가 이루어 졌느냐에 따라 달라진다.

size, sizeof, length 의 차이

size, sizeof, length 의 차이 

• length()
  • 문자열 길이 반환에 쓰인다.
  • 문자열의 마지막에 널문자가 들어가는 것을 확인할 때 length의 경우 널문자까지의 길이가 아닌 실제 문자열 길이만 반환
• size()
  • 할당된 공간의 개수를 알려줌
  • 객체가 메모리에서 사용하는 크기를 반환한다.
  • 컴파일타임 연산자
• sizeof()
  • 타입 크기를 리턴해준다.
  • 피연산자의 메모리 크기를 바이트 단위로 계산, 상수, 변수, 뿐 아니라 자료형 그 자체가 피연산자가 될 수 있다.
  • 우선순위가 높기 때문에 피연산자가 단항이 아니라면 일반적으로 괄호를 묶어준다.
  • 32비트 컴파일 시 4바이트 64비트 컴파일 시 8바이트 크기
  • 객체들은 타입별로 크기가 일정, 뭔가 할당하는 행위는 동적할당되는 영역이여서 크기에 영향을 주지 않는다.

 정리

• length는 문자열 길이 반환시에만 사용되며
• size및 sizeof의 차이는 size는 해당 공간의 크기만 보내기 때문에 만약 {1, 2, 3} 이렇게 되면 3개를 반환하고, sizeof는 해당 자료형의 크기 각각의 갖고 있는 바이트 크기를 반환한다 그래서 1, 2, 3 이니까 4바이트 4바이트 4바이트 해서 12 가 반환된다.

알고리즘

• 어떤 문제를 해결하기 위한 확실한 방법

주어진 수의 평균을 구하시오

• 구체적이고 확실한 방법이 필요하다.

예를 들어 변수 3개가 있다면 3 변수를 더하고 3을 나눠라 하면 답이 나오고

배열로 주어졌을 때 배열의 모든 숫자를 더하고 원소의 개수만큼 나눠라 하는 방법으로 구하면 평균이 구해진다.

 

 

대충 더해서 구하라고 하면 알고리즘이 아니다. 모호한 방식으로 평균을 구할 수 없다.

이처럼 알고리즘은 자료구조의 영향을 많이 다르다.

 

자료구조가 바뀌면 알고리즘이 바뀐다.

 

특정한 자료구조에 대해 문제를 푸는 방식이 한 가지만 있는 것은 아니다.

 

예를 들어 위와 같이

1. 배열의 모든 숫자를 더하고 원소의 개수 만큼 나눠라
2. 배열의 첫 번째 원소와 두번째 원소 세번째 원소를 더하고 3을 나눠라

이런식으로 배열의 한가지 자료구조에 대해 여러가지가 존재하고

알고리즘은 여러가지를 쓸 수 없고,

 

가장 효율적인 것을 사용해야 한다.

알고리즘은 자료구조에 따라 달라지고, 같은 자료구조에 대해 알고리즘도 여러가지가 있을 수 있다.

 

프로그램 작성시

1. 먼저 자료구조를 선택해 데이터를 어떻게 저장하고 사용할 지 결정하고
2. 이에 맞는 알고리즘을 통해서 데이터를 가공하고 원하는 과정을 거친다.

상황에 적절한 자료구조를 택하고 이에 맞는 적절한 알고리즘을 정해야한다.

프로그램은 자료구조와 알고리즘으로 나뉜다.