자료구조💡

---

• 자료구조란❓

  • 데이터 값의 모임, 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미
  • 효과적으로 설계된 자료구조는 실행시간 혹은 메모리 용량과 같은 자원을 최소한으로 사용하면서 연산을 수행하도록 해준다

• 자료구조의 목적❗
  • 자료를 더 효율적으로 저장하고, 관리하기 위해 사용.
    잘 선택된 자료구조는 실행시간을 단축시켜주거나 메모리 용량의 절약을 이끌어 냄

• 예시💡

  • 예를 들어 빈 책장과 책들이 있을 때 책장에 최대한 많은 책을 넣을 수 있으면서,
    책을 찾아서 꺼낼때도 효율적인 방법을 생각해본다.

    • 책장에 책을 ㄱ -> ㅎ 오름차순으로 정리를 한다
    • 책의 카테고리 별로 책장의 층을 나누어 사용한다

  • 책장 = 메모리 , 책 = 데이터 라고 생각했을 때
    위와 같이 가장 효율적인 방법으로 데이터(=책)를 메모리(=책장)에 저장하는 방법(=정렬규칙)을 자료구조라 할 수 있다

  • 해당 블로그 참고

---

🧡자료구조의 선택기준

💛시간복잡도

• 알고리즘을 수행하는 데 걸리는 시간
• 알고리즘의 수행시간이 짧을 수록 좋은 시간복잡도

✅빅오(BIG-O 표기법)

- 알고리즘 최악의 실행시간을 표기
- 실행 속도 : O(1) < O(log N) < O(N) < O(N log N) < O(N^2) < O(N^3) < O(2^N)

💛공간복잡도

• 알고리즘을 수행하는 데 필요한 메모리의 크기
• 데이터의 크기와 비교해 저장공간의 크기가 너무 남거나 부족하지 않아야 함

최근에는 공간복잡도 보단 시간복잡도의 중요성이 더 부각 됨

---

🧡자료구조의 종류

💛배열

• 동일한 타입의 데이터들을 저장하며, 고정된 크기를 가지고 있다.
• 인덱스값을 지니고 있어 인덱스 값으로 각 데이터에 접근이 가능
• 읽기/쓰기(참조)에 좋음
• 추가/제거(수정)에 안좋음

💛연결리스트

• 각 노드가 한 줄로(순차적으로) 연결되어있는 방식
• 비연속적인 주소값과 크기가 동적으로 변할 수 있다는 특징
• 추가/제거(수정)에 좋음
• 읽기/쓰기(참조)에 안좋음

✅ 배열과 연결리스트의 비교

/	특징	크기	읽기/쓰기(참조)	추가/제거(수정)	시간복잡도	공간복잡도
배열	동일한 데이터 타입 저장 index를 통한 데이터 접근이 용이하다	고정적	좋음	안좋음	접근하고자 하는 데이터의 인덱스 값을 알고있을 때 : O(1) , 순차적으로 데이터에 접근 할 때 : O(n)	좋음
연결리스트	각 데이터가 한 줄로 연결됨 각각의 데이터는 자신의 바로 다음 참조데이터의 값만 가지고 있음	동적	안좋음	좋음	O(n)	안좋음

💛스택

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

✅ 스택의 연산

• pop(): 스택에서 가장 위에 있는 항목을 제거한다.
• push(item): item 하나를 스택의 가장 윗 부분에 추가한다.
• peek(): 스택의 가장 위에 있는 항목을 반환한다.
• isEmpty(): 스택이 비어 있을 때에 true를 반환한다.

✅스택오버플로우

• 콜스택에 너무 많은 데이터가 쌓이면 스택오버플로우가 발생 (Error)
• 재귀함수를 호출 할 때 주로 발생

💛큐

• FIFO(First In First Out, 선입선출)의 자료구조
• 멀티스레딩에서 스레드를 관리
• 대기열 시스템

.
.
.

🧡자료구조의 사용 용도

• 배열

  • 빠른 접근이 요구되고, 데이터의 삽입과 삭제가 적을 때
  • 개인정보 등의 수정이 잦지 않은 정보(데이터)를 보관하고, 참조 할 때 사용

• 연결리스트

  • 삽입과 삭제 연산이 잦고, 검색 빈도가 적을 때
  • 음악플레이어 , 작업내역 (history)

• 스택

  • 재귀함수 호출
  • 뒤로가기, 실행취소