자료구조

자료 = 데이터

저장공간에 데이터가 들어있고 그 데이터에 대한 읽기,쓰기,삽입,삭제,탐색하는 연산을 제공하는 것을 자료구조 라고 한다.

입력데이터를 이용하여 문제를 푸는 논리적인 절차를 알고리즘이라고 한다.

자료구조

1. 변수(variable)

a=5 #쓰기연산(a라는 주소에 5가 들어있음)
print(a) #읽기연산(a를 읽어옴)

2. 배열(array),리스트(list)

A=[3,-1,5,7] # 쓰기
#각 원소의 index를 이용한 읽기
#A[0]-> 3 
#A[1]-> -1
#A[2]-> 5
#A[3]-> 7
#삽입:A.append(9)
#삭제:A.pop()

최대공약수(GCD)계산 알고리즘

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

gcd_sub

a=8
b=12

while a!=0 and b!=0:
  if a>b : a=a-b
  else : b=b-a
print(a+b)

gcd_mod

a=8
b=12

while a!=0 and b!=0:
  if a>b : a=a%b
  else : b=b%a
print(a+b)

gcd_rec

gcd(a,b) = gcd(a,b%a) or gcd(a%b,b)

자료구조와 알고리리즘

성능1 : 가상컴퓨터 + 가상언어 + 가상코드

자료구조,알고리즘 -> 코드(C,JAVA,Python)컴퓨터

여기서, 문제점

• HW/SW 환경 상이
• 다양한 크리 입력

<해결>
가상컴퓨터 + 가상언어 + 가상코드

🎇가상컴퓨터

튜닝머신 -> 폰 노이만 : RAM(Random Access Machine)
RAM = CPU + Memory + 기본 연산(단위시간에 수행되는 연산들의 모임)

기본연산

-배정,대입,복사연산
a=b : b에서 읽어서 a에 쓴다 -> 1시간
-산술연산 : +,-,*,/ -> 1시간
-비교연산 : >,<=,>,>=,==,!=-> 1시간
-논리연산 : AND,OR,NOT ->1시간
-비트연산 : bit-and,or,not ->1시간

🎇가상언어

• 배정,산술,비교,논리,비트논리 와 같은 기본연산을 표현
• 비교 : if,elif,else...
• 반복 : for,while
• 함수 정의 및 호출,return

🎇가상코드

가상언어를 이용하여 코드구현

algorithm ArrayMax(A,n):
	# input: n개의 정수를 갖는 배열 A
    # ouput: A의 수 중에서 최대값을 리턴
    currentMax = A[0]
    for i in ragne(1,n):
    	if currentMax<A[i]:
        	currentMax=A[i]
    return currentMax

만약 n 이 100,1000,10000 일 때 소요되는 시간을 알아야 효율적인 코드를 구현할 수 있다.