오늘의 나는 무엇을 새롭게 배웠나요?

기본 자료구조 강의 중 일부

[1] 컴퓨터가 데이터를 저장하는 방법

스토리지 vs 메모리

스토리지

• 데이터가 영구적으로 저장되는 곳
• 데이터를 저장하고 받아오는 데 오래 걸린다.

메모리

• 데이터를 임시로 저장하는 곳
• RAM (Random Access Memory)
  • 동일한 크기의 칸으로 나눠진 굉장히 긴 띠라고 생각하면 편하다.
    • RAM의 한 칸에 저장되는 데이터의 용량은 1 바이트
  • 임의 접근 : 저장 위치만 알면 접근할 때 항상 일정한 시간이 걸림
    • 순차 접근은 저장된 위치까지 가는데 한 단계씩 거쳐야하는 것
  • 메모리에 저장된 데이터 접근 시간 복잡도 : O(1)
• 자료구조에서 주로 다루는 곳

레퍼런스

• 데이터에 접근할 수 있게 해주는 값
• ‘주소’ 보다는 조금 더 포괄적인 표현
  • 파이썬의 id 함수를 사용해 데이터가 저장되어있는 주소를 알 수 있음
• 자료 구조를 배울 때는 “주소 = 레퍼런트”라고 생각해도 됨

[2] 배열

C의 배열

• 메모리에 값들이 4바이트씩 차지하면서 연속적으로 저장되어있다.
• 크기가 고정되어있고, 같은 타입의 데이터만 담을 수 있다.

파이썬의 리스트에 값이 저장되는 방법

• 값들은 메모리에 흩어져있다. 이런 값들의 레퍼런스를 연속적으로 저장한 것이 리스트! 즉, 값을 가리키고 있기 때문에 값들의 자료형(타입)이 상관없다.

1. 배열 인덱스 접근 : O(1)
   • (배열의 시작 주소) + (인덱스) * (데이터크기)
2. 배열 탐색
   • 조건에 만족하는 값 찾기
   • n * O(1) = O(n) - 선형탐색

정적 배열과 동적배열

배열의 크기가 어떻게 결정되는가

정적 배열

• 보통 “배열”이라고 하면 정적 배열을 말한다.
• 배열의 크기가 선언 시 고정
• 새로운 엔트리를 추가하고 기존 엔트리를 삭제하는 것이 불가능
• C언어의 배열/Java의 Array타입 변수
• 데이터 접근, 저장 시에는 O(1), 데이터 탐색에는 O(n)이 소요

동적 배열

• 배열의 크기가 동적으로 변한다. 보통 값을 추가할 때 칸이 부족하면 기존 칸의 2배만큼 늘리는 식으로 크기를 조절한다.
• 새로운 엔트리를 추가할 수 있고, 삭제할 수 있다.
• 파이썬의 배열/Java의 ArrayList 타입 변수/C++의 vector
• 자바스크립트 Array 객체
• 동적 배열 역시 내부적으로는 정적배열이다. (정적배열로 만들어진 자료구조)
• 데이터 접근, 저장 시에는 O(1), 데이터 탐색에는 O(n)이 소요된다.
• 추가의 경우 배열에 아직 데이터를 저장할 수 있는 공간이 있어 배열 길이를 늘려줄 필요가 없으면 O(1), 더 긴 배열을 만들어야할 때는 O(n)
  • 분할 상환 분석 (Amortized Analysis)
    • 분할 상환 분석의 관점에서는 추가(append) 연산이 최악의 경우 O(1)이 걸린다.
      • 분석법은 [기본자료구조 3-9]
    • 일반적으로 최악의 경우보다 분할 상환 분석을 한 시간복잡도가 더 적다면, 분할 상환 분석을 한 시간 복잡도를 사용한다고 한다.
• insert의 경우 여유가 있을 때도, 꽉찼을 경우에도 O(n)
• 삭제의 경우에도 맨 뒤의 값을 삭제할 때는 O(1), 중간에 삽입된 값을 삭제할 때는 다른 뒷 데이터들을 앞으로 이동 (사실상 덮어쓰기)해야하기 때문에 O(n)
  • 이때, 맨 뒤 값을 삭제할 때도 동적 배열의 크기를 줄여야할 경우 (배열의 요소 개수가 원래보다 1/3 줄었다던가 등..) 남은 데이터를 새로운 작은 배열로 이동 → 따라서 최악의 경우 O(n)이 걸린다.
    • 맨 끝 데이터를 삭제하는 연산은 최악의 경우 O(n)이 걸리지만, 분할 상환 분석을 적용하면 O(1)이라고 할 수 있다.

공부하면서 어떤 어려움이 있었나요?

어려움은 없었다. 다만, C언어에서 Linked list를 사용했던 법과 달라서 신기했고, 더 쉬워서 좋았다.

• 강의가 조금 밀렸는데, 다음주 부터 React를 들어가기 때문에 틈틈히 들을 예정이다.

내일의 나는 무엇을 공부해야 할까요?

• 기본 자료구조 강의 듣기
• Weekly Mission PR 올리기