자료구조

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

알고리즘

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

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

배열(Array)

• 데이터를 나열하고 각 데이터를 인덱스에 대응시킨 데이터구조
• 파이썬 에서는 리스트 타입이 배열을 대체

같은종류의 데이터를 순차적으로 정리하고 효율적으로 관리가 가능

파이썬은 다양한 데이터를 저장할 수 있음

배열의 장단점

• 배열의 장점
  • 구현이 쉬움
  • 빠른 접근이 가능 : 인덱스를 통해 데이터에 바로 접근이 가능
• 배열의 단점
  • 데이터 추가 삭제가 어려움
  • 크기가 고정 되어있음

핵심연산

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

연결 리스트(Linked List)

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

Array vs Linked List

• 배열: 번호가 붙여진 칸에 원소들을 채워 관리
• 연결 리스트: 각 원소를 줄줄이 엮어서 관리

→ 메모리에 하나의 구역을 만들어 번호를 붙여서 관리하면 배열

→ 여기저기 저장된 데이터에 주소를 붙여서 이어지게 하면 연결 리스트

linked list 용어

• 노드(node):
  • 데이터가 저장되는 단위
  • [데이터값, 포인터] 로구성
• 포인터(pointer):
  • 다음 데이터의 주소를 담고 있는공간
  • 다음노드 혹은 이전 노드의 연결 정보를 가지고 있음

연결 리스트의 장단점

• 장점:

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

• 단점:

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

핵심연산

1. 현재위치의 값을 가져오기
2. 현재위치의 값 수정하기
3. 현재위치의 값 삭제하기
4. 현재위치에 값을 추가하기
5. 다음 위치로 이동하기

큐(Queue)

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

Queue 활용

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

💡 스케줄링 프로세스가 생성되어 실행될때 필요한 여러자원을 해당 프로세스에 할당하는 작업 대기시간은 최소화 하고 최대한 공평하게 처리 선점 스케줄링, 비선점 스케줄링으로 나뉨

Queue 장단점

• 장점
  • 데이터의 삽입과 삭제가 빠름
    • 삽입 삭제 O(1)
• 단점:
  • 정책에따라 가장 위쪽의 원소만 접근 가능
  • 탐색이 비효율적(다꺼내서 탐색)

Enqueue, Dequeue

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

→ 핵심 연산

스택(Stack)

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

스택의 활용

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

스택 용어

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

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

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

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

스택 구현하기

1. 배열로 구현하기

   • 장점:
     • 단순한 구조 → 구현이 쉬움
     • 데이터의 저장과 읽기 속도가 빠름
   • 단점:
     • 데이터의 최대 개수를 미리정해야함
     • 데이터 삽입 삭제시 비효율적

2. 연결리스트로 구현하기

   • 장점:
     • 데이터 최대 개수 제한 없음
     • 데이터 삽입 삭제 용이
   • 단점:
     • 데이터 접근이 복잡함
     • 시간이 걸림

Reference
[운영체제] 프로세스 스케줄링 종류와 기법

[자료구조] Array, Queue, Stack

[KR] 자료구조 & 알고리즘 : 배열(array), 큐(queue), 스택(stack)

[KR] 자료구조 & 알고리즘 : 링크드 리스트(Linked List)