💾 data structure basics

2021/05/13-14
S5-Week 2 : Data Structure and Algorithm Core

keyword : 자료 구조, 추상자료형(ADT), 할당과 참조

• 효율성
• 소프트웨어와 하드웨어 성능, 속도, 협업 모두 포함

intro

• OOP의 목적은 재사용과 유지보수, 그리고 효율성
• 자료구조는 컴퓨터 과학에 있어서 전체적인 관점의 기초공사 개념이다.
• 자료구조의 시작 : 실생활에서 발생하는 대용량의 다양한 데이터를 효율적으로 처리, 저장하기 위해 자료구조라는 개념이 개발되었다.
• 효율적 처리란?
  - 자동화, 빠른 계산, 반복 내용 처리, 값이 빠르게 변경되는 경우..

자료구조

• 배열

  • 파이썬에서는 리스트와 튜플을 통해 자료구조의 기본인 배열을 구현할 수 있다
  • 배열의 기능) 하나의 변수에 여러 개의 인덱스로 묶는 것
  • 특) 인덱스 사용하여 노드에 접근 가능

• 파이썬은 리스트 자료형이 자료구조의 연결 리스트로 기능 지원 (자료구조의 배열과 연결리스트의 특징 모두 갖고 있음)

  • 연결 리스트 >> 동적으로 처리 가능 >> 고정으로 값을 할당하는 것은 정적 처리라고 함 (인덱스로 값 할당하는 등)
  • 인덱스 크기를 자유롭게 확장 가능, 서로 다른 자료형을 노드로 갖을 수 있음

외장 함수보다 내장 함수가 더 메모리를 많이 쓴다

컴퓨터 과학의 자료 구조

• 스택
• 큐
• 리스트 (연결 리스트 기반)
• 트리
• 그래프 ..

파이썬의 시퀀스(연속) 자료형

• 리스트(배열)
• 튜플(배열)
• range(반복)
• string(문자열)...

자료구조의 기본은 배열(고정된 길이)이다.

• 리스트나 튜플의 핵심은 인덱스를 사용하는 것
• [0:4] 등으로 인덱싱 가능
• 다양한 문자열 메소드 사용
  • 문자열 뒤집기의 3가지 예시
    • reverse() : 리스트 제공 메소드
    • reversed: 내장 함수
    • 반복문과 조건문, 대입개념 활용

자료구조와 효율성

• 시간 복잡성, Big O 표기법
• 복잡도를 판단할 수 있는 기준이 있지만 100% 효율성을 맞출 순 없다
• 시간 복잡도 : 얼마나 실행시간이 걸렸는지 (알고리즘) (소프트웨어) (더 중요해짐)
• 공간 복잡도 : 얼마나 메모리 저장 공간이 필요한지 (하드웨어)

Big O 표기법(notation)

• 알고리즘 실행 효율성에 대해 측정할 수 있다

• 과거에는 안드, ios app 중심이었을때 알고리즘 성능이 되게 중요했음.

• 요즘엔 머신러닝, 딥러닝 알고리즘이 중심이 되면서 효율 보다는 정확성이 더 중요해짐

• 빅오표기법은 데이터 입력값 크기에 따라 알고리즘 실행 속도의 변화 설명하는 방법

  • 입력값 증가 기준 실행시간이 얼마나 길어지는가?

• 빅오표기법은 해당 코드가 얼마나 수행되었는지(결과값을 출력하기 위한 연산을 얼마나 반복하였는지)에 따라 효율성 확인

• 특정 방법론 하나만으로는 성능을 예측할 수 없다

  • O(n) (읽을땐 빅오엔)

• Pop 메쏘드

  • O(n) : 내부적으로 반복문을 돌음

• 선형 시간이 상수 시간보다 우선시 되므로 상수시간은 무시되고, 반복문이 독립적으로 수행되기 때문에 해당 코드에 대한 런타임은 선형시간 linear time (O(n))이 된다.

• 최악의 경우

  • 로직에 따라 Big O 복잡도가 바뀌는 경우
  • 반복문을 통해 첫 아이템은 O(1), 마지막 아이템을 찾을 때까지 검색하므로 O(n)이 걸리는 경우
  • 최악의 경우 판단 가능 >> 알고리즘의 효율성을 상한선 기준으로 표기

• 반복문의 결과 범위 테스트

• n의 값(입력값)에 따라 while의 반복수가 달라지기 때문에 빅오 표기가 달라진다

  • 입력값과 출력값이 동일하지 않으므로 선형시간(O(n))이 될 수 없다

• 반복문, 내부 로직을 보고 효율성을 판단해야 한다

• 코드 실행 시간에 대한 예측

  • 시간복잡도를 확인할 때 우선적으로 고려할 것은 반복문으로서,
  • 반복문이 2개가 존재하고, 중첩 반복문이니까 O(n^2)이겠다 >> 먼저 예측
  • 근데 두번째 반복문을 보면 반환하는 경우가 1번이기 때문에 O(n) 시간이 소요됨

• 특징 정리

  • 알고리즘의 효율성을 상한선 기준으로 표기함
    • O(n), O(n^2) 둘다 나온다면 O(n)으로 표시한다는 것?
    • 그런데 최선보다 최악을 더 많이 고려해야 한다는 뜻은?
      • 만약 알고리즘이 1. 최선 n, 최악 n 이 있고 2. 최선 logn, 최악 n! 이 있다면 1을 선택한다는 것
  • 상수항 무시
    • (O(5n)이 아니라 O(n))
  • 가장 큰 데이터 입력값(N)에 따라 복잡도 판단
    • O(N^2 + 2N + 10) => O(N^2)