AIB 섹션 5 컴퓨터공학 N514 Data Structure essentials

• 프로그래밍의 효율성 판단 방법
  • 목적에 알맞은 코드/자료구조 사용, 디자인 잘 된 코드
• 데이터 관련 소스코드에서 사용하는 알고리즘들을 찾아본 적이 있는가?
• 컴퓨터가 자료구저의 어떤 영향을 받는가
• 컴퓨터가 느려지는 이유와 알고리즘의 연관성

키워드: 참조와 할당, 성능, 빅오표기법(시간, 공간)

read, search, insert, delete를 생각하면서 각 상황에 따라 자료형의 효율성 생각해볼 수 있음

알고리즘: 어떤 기능을 하기 위한 동작들의 모음. 문제 해결을 위해

자료구조의 기본적인 부분 배워보자

자료구조가 왜 필요한가?

프로그래밍은 인간이 컴퓨터를 사용할 때 도와주기 위한 작업. 이를 효율적으로 진행하고 싶다. 컴퓨터는 자료구조에 따라 작업을 수행하는 효율이 다르다.

배열: 리스트와 튜플. 여러 변수를 하나의 변수에 인덱스로 묶는다.

리스트: 임의의 메모리에 자료를 동적으로 처리할 수 있다. 각각이 분산되어 있다는 뜻.

• 파이썬에서의 리스트는 배열과 연결리스트의 특징을 모두 가지고 있다.
  • 배열: 인덱스를 사용해서 각 노드(아이템)에 접근
  • 연결리스트: 인덱스를 자유롭게 확장하고, 서로 다른 자료형을 노드로 가질 수 있다.

자료구조의 효율성

특정 자료구조에 대해 작업을 실행할 때 효율성을 판단하는 방법: 빅 오 Big O

코드가 얼마나 수행되었는지, 즉 연산을 얼마나 반복하였는지에 따라 효율성을 확인한다. 당연히 입력 데이터의 크기에 따라 시간이 달라지겠다.

• 시간복잡도: 얼마나 시간이 걸리는지
• 공간복잡도: 얼마만큼의 메모리가 필요한지.

하지만 Big O 만으로 성능을 예측할 수 없다. 실제 시간이 30n + 1000이라고 나와도 빅오는 O(n)이다. 1000이 더 큰지, 30n이 더 큰지 모른다. 다만 무한정으로 n이 커진다면 30n에 비례.

자료구조 사례

• 어떤 웹사이트에서 상품을 조회할 때 보여줄 순서대로 표기할 때 자료구조의 역할이 있다.

데이터 관리 사례

• https://bespinglobal.com/download/2022pdf/ecommerce.pdf
• https://mixpanel.mfitlab.com/blog/introduce-product-data-analysis-for-beginner

best / worst cases

• list에서는 맨 뒤 제거 시간복잡도 O(1), 맨 앞 제거는 O(n)