[Python] 자료구조와 알고리즘

완수·2021년 10월 14일
0
post-thumbnail

자료구조와 알고리즘

  • 어떤 자료구조와 알고리즘을 쓰느냐에 따라 성능이 크게 달라질 수 있다.

Data Structure (자료구조)

: 컴퓨터 내의 데이터들을 효율적으로 저장하고 사용(관리)하는 방법들

  • 코드 상에서 효율적으로 데이터를 처리하기 위해, 데이터 특성에 따라 구조화필요
    → 어떤 데이터 구조를 사용하느냐에 따라 코드 효율이 달라짐

대표적인 자료구조

: 배열, 스택, 큐, 링크드 리스트, 해쉬 테이블, 힙 등

Array (배열)

: 데이터를 나열하고 각 데이터를 인덱스에 대응하도록 구성한 데이터 구조

  • 장점: 빠른 접근 가능 (첫 데이터의 위치에서 상대적인 위치로 데이터 접근 가능 (인덱스)
  • 단점: 데이터의 추가/삭제가 어려움 (크기가 고정되어있음)

Queue (큐)

: FIFO(First In First Out), 선입선출 자료구조

  • Queue(): 선입선출
  • LifoQueue(): 스택 구조, 후입선출
  • PrioirtyQueue(): 우선순위가 높은 순으로 데이터 출력
    → tuple형식으로 input, 숫자가 작을수록 우선순위가 높다.
  • 운영체제에서 멀티 태스킹을 위한 프로세스 스케쥴링 방식을 구현하기 위해 많이 사용됨

Stack (스택)

: LIFO(Last In First Out), 후입선출 자료구조

  • 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조
  • 장점: 데이터 처리 속도가 빠르다
  • 단점: 저장공간의 낭비가 발생할 수 있다
    (미리 최대 갯수만큼의 저장공간 확보 필요)

Linked List

: 떨어진 곳에 존재하는 데이터를 화살표로 연결해 관리, 노드와 노드가 포인터로 연결된 형태

  • 노드: 데이터 저장 단위
    노드 = 데이터값 + 포인터
  • 포인터: 각 노드 안에서 이전이나 다음 노드와의 연결 정보를 가지고있는 공간
    컴퓨터 내부의 프로세스 구조의 함수 동작 방식에 활용

Algorythm (알고리즘)

: 어떤 문제를 풀기 위한 절차/방법

  • 어떤 문제에 대해 특정 '입력'을 넣으면 원하는 '출력'을 얻을 수 있도록 만드는 프로그래밍
  • 시간 복잡도 / 공간 복잡도가 중요

시간복잡도

: 알고리즘을 위해 필요한 연산의 횟수 (알고리즘 실행 속도)

  • 입력의 크기가 커질수록 반복문이 알고리즘의 수행 시간을 지배

공간복잡도

: 알고리즘을 위해 필요한 메모리의 양 (알고리즘이 사용하는 메모리 사이즈)

알고리즘 성능 표기법

Big O(빅-오) 표기법

  • 알고리즘 최악의 실행 시간을 표기 (아무리 최악의 상황이라도, 이정도의 성능은 보장한다는 의미)
  • 입력 n에 따라 몇번 실행 되는지 계산
  • O(1)O(1) < O(logn)O(log n) < O(n)O(n) < O(nlogn)O(nlog n) < O(n2)O(n^2) < O(2n)O(2^n) < O(n!)O(n!)
    • 반복문이 없을때는 O(1)O(1)
profile
병아리 개발자의 공부 노트 🐣

1개의 댓글

comment-user-thumbnail
2022년 8월 11일

잘읽었습니다.
오타있습니다

답글 달기