[자료구조&알고리즘] 0-1. 자료구조와 알고리즘

자료구조

자료 : 데이터(data)

자료구조 : 데이터를 저장하기 위한 저장공간(memory) + 읽기, 쓰기, 삽입, 삭제, 탐색 등의 연산

 

알고리즘 : 입력된 데이터를 통해 문제를 푸는 과정 (유한한 횟수의 연산들을 반복해 정답을 출력)

 

자료구조 예 :

1. 변수(variable) a = 5 (a라는 저장 공간에 값 5를 쓰는 쓰기연산), print(a) (a에 들어있는 값을 읽어와 출력하는 읽기연산)

 

※ a라는 변수가 있으면 a에 5라는 값이 실제로 저장되는 것이 아니라 5가 저장되어 있는 주소가 a에 저장됨 (5가 들어있는 객체의 주소)

 

2. 배열(array) 리스트(list)  A = [3,-1,5,7]

A[0]은 3이 들어있는 객체를 가리키고 A[1]은 -1이 들어있는 객체를 가리키는 방식으로 접근

 

접근 : 각 원소의 index

읽기,쓰기 : A[3]만으로 읽고 쓰기 가능

삽입 : A.append(9), A.insert(1,9)

삭제 : A.pop( ) (매개변수가 없다면 가장 뒤의 값을 리턴 후 삭제)

          A.pop(2) 두번째에 있는 인덱스 값이 삭제되고 그 값이 리턴됨

 

알고리즘 예 : 100개의 정수 리스트A : 입력 -> 오름차순 정렬 : 출력

 

인류 최초의 알고리즘 : 최대공약수 (GCD) 계산 알고리즘 (by Euclid)

※  페르시아 Algebra 수학자 Al-Khwarizmi -> Algorismus + Arithmos => Algorithm

 

gcd(8,12) = max{1,2,4} = 4

8 = ~~~~~~~~

12 = ~~~~~~~~~~~~   gcd(8,12)

->

8 ~~~~~~~~

4 ~~~~   gcd(8,4)

->

4 ~~~~

4 ~~~~   gcd(4,4)

->

4 ~~~~   

0

 

---

 

자료구조와 알고리즘 성능 : 가상컴퓨터 + 가상언어 + 가상코드

 

자료구조 + 알고리즘 -> 코드로 기술(C, java, python) - 컴퓨터에서 동작 - hw/sw환경 상이하면 서로 다른 성능, 다양한 크기의 입력

 

따라서 객관적인 컴퓨터 모델이 필요하기 때문에 hw/sw에 독립적인 가상의 컴퓨터를 생성

 

가상컴퓨터(virtual machine) + 가상언어(Pseudo language) + 가상코드(Pseudo Code)

누구나 다 같은 환경에서 여러 알고리즘 비교 가능

 

가상컴퓨터 : Turing Machine -> von Nenmann : RAM(Random Access Machine) ※ 우리가 일반적으로 아는 램과 비슷한 개념

RAM = cpu + memory + 기본연산 -> 단위시간에 수행되는 연산들의 모음

 

기본연산

기본연산이란,

 

배정,대입,복사연산 : A = B | B값을 읽어서 (메모리에 접근해 해당 값을 읽어와) A에쓰기 (A라는 메모리에 가서 쓰기)

산술연산 : +, -, x, / | 1시간 (RAM 모델에서 나머지 버림 올림 반올림은 기본연산이라고 하지 않지만 그렇게 가정)

비교연산 : >, >=, <, <=, ==, != | A<B -> A-B<0 뺄샘으로 보면 산술연산

논리연산 : and or not

비트연산 : bit-and or not

 

모든 연산이 한 번 수행될 때, 1단위시간이 소요된다고 가정

1단위시간내 할 수 있는 기본연산으로 정의한 가상의 컴퓨터를 RAM모델이라고 함

---

 

가상언어 (pseudo/virtual languages)

배정, 산술, 비교, 논리, bit논리 같은 기본 연산 표현 가능

 

비교 : if, if else, if elseif else

반복 : for, while

함수 : 정의 호출 리턴

 

이런 것들을 제공해야 가상언어라고 할 수 있음

 

가상코드 (pseudo code)

Algorithm ArrayMax(A,n):    ※ Input: n개의 정수를 갖는 배열 A Output: A의 수 중에서 최댓값을 찾아 리턴

    currentMax = A[0]

    for i = 1 to n-1 do

         if currentMax < A[i]:

                  currentMax = A[i]

    return currentMax

 

A = [3,-1,9,2,12], n = 5

 

currentMax 에 A[0]을 집어넣는 연산 1회

for문 실행하면 6회 총 7회의 기본 연산

만약 n이 무한으로 커지거나 입력값이 무한의 경우의 수로 들어오면 어떻게 계산할 것인가?

 

---

 

★ ★ ★ ★ ★

이 블로그는 수익창출을 목적으로 하지 않고, 제가 공부를 하기 위해 운영하고 있습니다.

따라서, 블로그 내의 모든 콘텐츠는 제 주관적인 의견과 경험을 바탕으로 작성되었으며, 모든 정보의 정확성을 보장할 수 없습니다.

만약 블로그 내의 정보에 대해 의문이 있으시거나, 정확하지 않은 정보를 발견하신다면, 언제든지 저에게 알려주시기 바랍니다.

이 블로그가 여러분의 공부에 도움이 되기를 바랍니다.

감사합니다.

★ ★ ★ ★ ★