자료구조

자료구조와 알고리즘

자료구조

• 데이터를 효율적으로 관리할 수 있는 데이터구조
• 대표적 자료구조: 배열, 스택, 큐, 링크드 리스트, 해쉬 테이블, 힙 

알고리즘

• 어떤 문제에 특정한 입력을 넣으면 기대하는 출력을 얻을 수 있도록 만드는 프로그래밍

 => 어떤 자료구조와 알고리즘을 쓰냐에 따라 성능이 차이가 남

 

배열(Array)

데이터를 나열하고 각 데이터를 인덱스에 대응시킨 데이터구조

파이썬 에서는 리스트 타입이 배열을 대체

배열의 장단점

장점

• 구현이 쉬움
• 빠른 접근이 가능 : 인덱스를 통해 데이터에 바로 접근이 가능

단점

• 데이터 추가 삭제가 어려움
• 크기가 고정 되어있음

핵심연산

• 인덱스를 통해 데이터를 읽을 수 있는것
• 데이터를 수정할수 있는것(삭제없고 덮어쓰기)

연결 리스트(Linked List)

데이터와 데이터 사이를 화살표로 연결하여 관리하는 데이터구조

linked list 구성

노드(node)

• 데이터가 저장되는 단위
• [데이터값, 포인터] 로구성

포인터(pointer)

• 다음 데이터의 주소를 담고 있는공간
• 다음노드 혹은 이전 노드의 연결 정보를 가지고 있음

연결 리스트의 장단점

장점

• 데이터 공간을 미리 할당하지 않아도됨
• 삽입과 삭제가 빠름 ( 삽입 삭제가 빈번할때 사용)

단점

• 데이터 구조표현에 소요되는 저장공간이 큼
  • 연결을위한 별도의 데이터 공간
• 데이터를 찾는데 시간이 오래걸림
  • 인덱싱이 아닌 처음 원소부터 돌면서 찾아야함
• 중간에 데이터 삭제시 앞뒤 데이터를 연결해야함

핵심연산

• 현재위치의 값을 가져오기
• 현재위치의 값 수정하기
• 현재위치의 값 삭제하기
• 현재위치에 값을 추가하기
• 다음 위치로 이동하기

큐(Queue)

• 가장 먼저 넣은 데이터를 가장 먼저 꺼낼수 있는 자료구조
• FIFO( First-In, First-Out) 방식
• head=front, tail=rear

Queue 활용

운영체제에서 멀티 태스킹을 위한 프로세스 스케줄링 방식을 구현

Queue 장단점

장점

• 데이터의 삽입과 삭제가 빠름
  • 삽입 삭제 O(1)

단점

• 정책에따라 가장 위쪽의 원소만 접근 가능
• 탐색이 비효율적(다꺼내서 탐색)

Enqueue, Dequeue

enqueue: 큐에 데이터를 넣는 기능

deque: 큐에 데이터를 꺼내는 기능

=> Queue의 핵심연산

스택(Stack)

• 스택은 한쪽 끝에서만 데이터를 넣거나 뺄 수 있는 구조
  • 데이터에 제한적으로 접근
• 가장 나중에넣은 데이터를 먼저 추출할수 있는 구조
  • LIFO(Last-In, First-Out)

스택의 활용

• 프로세스의 함수들이 동작하는 방식
• 실행취소: 최근의 작업 부터 취소
• 웹브라우저 뒤로가기 기능

스택 연산

push() : 데이터를 스택에 삽입(넣기)

pop() : 데이터를 스택에서 삭제(꺼내기)

stack underflow: 비어있는 스택에서 데이터를 꺼내려고 할 때 생기는 오류

stack overflow: 가득 차있는 스택에 데이터를 삽입하려고 할 때 생기는 오류

 

Reference

https://velog.io/@dsunni/자료구조-Array-Queue-Stack

https://lucaseo.github.io/posts/2021-01-27-python-datastructure-array-que-stack/