[컴퓨터 공학 기본과 파이썬] DataStructure Essential

자료구조의 배경

- 프로그래밍이 생겨난 배경은 컴퓨터로 인간의 행동을 편하게 하기위한 작업

- 자료구조는 컴퓨터과학에 있어서 전체적인 관점의 기초공사 개념

- 자료구조의 시작은 파이썬이라는 프로그래밍언어와는 별개로, 실생활에서 발생하는 대용량의 다양한 데이터를 효율적으로 처리 ( 저장 ) 하기위해 자료구조라는 개념이 개발됨

자료구조의 다양한 활용

자료구조를 체계적으로 정립하기 위해 프로그래밍 언어별로 다양한 자료형이 생겨났고, 파이썬에서는 리스트와 튜플을 통해 자료구조의 기본인 배열을 구현 가능함

▶ 배열이란?

• 컴퓨터과학에서 사용되는 기본적인 용어
• 배열의 기능은 각각의 변수를 하나의 변수에 여러 개의 인덱스로 묶는 것
• 파이썬에서는 배열을 리스트와 튜플로 구현하고 활용함

▶ 파이썬의 리스트

• 자료구조의 기본으 배열이라 할 수 있고, 파이썬에서는 리스트와 튜플로 구현할 수 있음
• 리스트나 튜플의 핵심은 인덱스를 사용하는 것

# 리스트 인덱싱/슬라이싱 예시

s = [11,22,33,44,55]

print('s[0:3] 결과:', s[0:3])
print('s[:3] 결과:', s[:3])
print('s[1:] 결과:', s[1:])
print('s[::2] 결과:', s[::2])
print('s[0:1:3] 결과:', s[0:1:3])
print('s[-3] 결과:', s[-3])
print('s[-3:-1] 결과:', s[-3:-1])
print('s[1:-1] 결과:', s[1:-1])

자료구조와 효율성

▶ Big O 표기법

• 알고리즘 실행 효율성에 대해 측정할 방법이 필요함
• 빅오표기법은 해당 코드가 얼마나 수행되었는지 ( 결과값을 출력하기 위한 연산을 얼마나 반복하였는지 )에 따라 효율성을 확인함
• 알고리즘 계산 복잡도 종류
  • 시간 복잡도 : 알고리즘을 활용해 얼마나 실행시간이 걸렸는지.
  • 공간 복잡도 : 문제해결을 위해 얼마만큼 메모리 저장 공간이 필요한지.
  • 하드웨어의 성능이 증가하면서 공간 복잡도보다, 소프트웨어의 성능인 시간 복잡도가 더 중요하다.
• 실제 실행시간이 30n+1000와 같이 나왔더라도 빅오표기법으로는 O(n)으로 표현되기 때문에 실제 성능과 같을 수는 없음