자료구조
자료 : Data → 저장공간(memory) + 읽기, 쓰기, 삽입, 삭제, 탐색 (연산) ← 구조
자료구조 예 :
- 변수(variable)
a = 5 # a라는 저장공간에 값 5를 쓰는 쓰기연산
print(a) # 화면에 출력하는 읽기연산변수 이름으로 접근
- 배열/리스트
A = [3, -1, 5, 7]
A[2] # 5
각 원소의 index로 접근
리스트의 이름과 인덱스만으로 읽고 쓸 수 있다.
알고리즘
자료구조에 담긴 데이터를 가공해서 다양한 연산을 통해 원하는 정답을 출력하는 것
알고리즘 예 :
100개의 정수 : 리스트 A → 입력
↓
오름차순 정렬 → 출력
인류최초의 알고리즘 : 최대공약수(GCD) 계산 알고리즘 (by Euclid)
gcd(8, 12) : 8과 12를 공통으로 나눌 수 있는 수들 중 가장 큰 값
한 쪽이 0이 될 때까지 큰 수에서 작은 수를 뺀다. 0이 아닌 다른 한쪽의 값이 최대공약수가 된다.
gcd(a, b):
while a != 0 and b != 0:
if a > b : a = a - b
else: b = b - a
return a + b
gcd(2, 100) → gcd(2, 98) → ... → gcd(2, 2) → gcd(2, 0) ▶ while문 50번 반복
큰 수가 작은 수보다 작아질 때까지 반복 → 100을 2로 나눈 나머지가 나올 때까지 반복하는 것과 같다.
↓
gcd(a, b):
while a != 0 and b != 0:
if a > b : a = a % b
else: b = b % a
return a + bgcd(2, 100) → gcd(2, 0) ▶ while문 1번 반복
출처
한국외대 신찬수 교수님의 "Data Structure with Python" 강의를 참고로 정리하였습니다.
