[TIL][240724] 자료구조(Data structure), 배열(Array), 연결 리스트(Linked list)

어떤 문제가 있었나?

자료구조 알고리즘 강의가 생각보다 어려워 스쿼드 세션을 잘 보내면 어렵지 않겠다는 생각은 완전히 오산이었다. 파이썬 세션도 내가 어느정도 알고 있었기에 따라갈 수 있었다는 것을 망각했다. 용어를 모르니 이해하지 못한 부분이 있었지만 초반이라 전반적으로 세션을 따라갈 수 있었다. 하지만 앞으로가 걱정이 되었다.

---

무엇을 시도했나?

세션에서 알고리즘 학습을 위한 접근법을 제시해 주셨는데, 기존 공부했던 방식인 Step by step이 알고리즘에선 효율적인 학습법이 아닐 수도 있다고 하셨다. 전체적으로 여러번 보는 것이 중요하고, 몰라도 한 번 훑는게 좋다고 이해했다. 그동안 Stack과 Queue 구현이 되지 않아 강의 수강이 멈춰 있었는데, 일단 무지성으로 강의 수강을 진행했다. 또한 추천하신 알고리즘 도서를 주문했다. 알고리즘 다 죽었어!

---

새로 알게 된 점은 무엇인가?

자료구조

• Data
  - (cs 적 사고로) "잘 조직화된 정보의 모음"
• Data type
  - A set of data with value having predefined characteristics.
  *(발번역 주의) 사전 정의된 특징을 가진 값을 지닌 정보 모음
  - 수집한 데이터를 컴퓨터가 처리할 수 있게 하기 위해 사전 정의를 해야한다. 
  - 더 다양한 데이터 구조를 표현하거나 직접 데이터 타입을 정의할 때 class를 이용하여 나만의 데이터 타입을 선언할 수 있다.

list_1 = [1, 2, 3]
print(list_1.pop())  # 3

list_2 = [1, 2, 3]
list_2.pop()
print(list_2)  # [1, 2]

'''
pop() 메소드를 봤으면 stack이라 생각할 수 있지만 list_1, list_2는
배열이자 리스트이자 스택이고 큐면서 선형 자료구조이다....?
파이썬 리스트 좋은거야? 나쁜거야?
'''

• Data structure
  - A paticular way to storing and organizing data in a computer so that it can be used efficiently
  *(발번역 주의) 컴퓨터에서 효율적이게 사용될 데이터를 저장하고 조직화하는 특별한 방법
  ➡️ 컴퓨터가 현실의 데이터를 잘 다룰 수 있게 해주는 방법
  - 자료 구조는 크게 2가지로 나뉜다.
  • 데이터: 속성
  • 연산: 선형 자료구조(list, stack, queue, linked list...), 비선형 자료구조(tree, graph...)
• Abstact data type = Structured Data + Operation
  - 추상 자료형 ADT: 구조화된 데이터를 필요한 연산과 함께 묶어서 표현하는 방법
  • 자료구조를 추상적(수학적)으로 정의해보는 것
  • 구체적으로 구현하는 방법은 정의하지 않고 해당 자료구조의 주요동작에 집중
  • ADT는 데이터와 연산에 대한 명세를 제공하는 것 ➡️ 자료구조의 추상화
  • 스마트폰의 자료구조 형태를 알아보자! (번호 앱, 음악 앱, 사진 앱)
    - 개별적인 특징 삭제
    - 데이터 구조의 특징을 도출 ➡️ 순서가 나열된 구조
    - 필요한 연산 정의 ➡️ 추가, 삭제, 수정, 정렬...

배열(Array)과 리스트(List)

class Person:
    pass

p1 = Person()

a_list = [1, "2", 3.5, {"key": "value"}, (5, 6), p1]

a_list.append(100)
a_list.remove(1)

• 파이썬의 리스트는 엄청나게 고차원적이다. 위와 같이 모든 자료형이 하나의 리스트 안에 들어갈 수 있다.
• 길이를 늘릴수도 줄일수도 있다. (원래는 안됨)
• 파이썬의 리스트를 구현하는데는 두가지 방법이 있다.

배열 Array

• 선형 자료구조(1차원 자료구조)이며 고정된 크기를 가진다.
• 모든 요소는 데이터 타입을 가지고, 각 요소는 하나의 인덱스로 접근해야지 사용할 수 있다.
• 연속된 메모리에 할당되고 변경이 되면 새로운 연속된 메모리에 할당된다.

???: 숫자 3개 저장하고 싶어!
메모리: 그래 여기 연속 3칸 줄테니 여기에 저장해.
???: 하나 더 추가하고 싶은데 1칸만 더 줘!
메모리: 그건 안돼. 새로 4칸 줄테니 여기에 저장해.
???: 중간에 있는 하나를 빼고 싶어!
메모리: 그건 안된다고... 새로 3칸을 줄테니 여기에 저장해.

• 위의 예시처럼 삽입, 수정, 삭제, 탐색할 때 O(n)이라는 시간복잡도를 가지게 된다.
• 하지만 탐색에서 리스트가 정렬된 경우 이진 탐색을 사용하여 O(logn)의 시간복잡도를 가질 수 있다.

연결 리스트 Linked list

• 배열(Array)에서 DB가 계속 늘어날 경우 연결 리스트를 사용할 수 있다.
• Pointer-based implementation
  *Pointer: 특정한 데이터가 저장된 주소 값을 보관하는 변수
• 선형 자료구조(1차원 자료구조)이며 가변 크기를 가질 수 있다.
• 모든 요소는 동일한 데이터 타입을 가지고. 비연속된 메모리 블럭에 할당된다.

A singly linked list

• 하나 하나를 Node라 하며 오른쪽 칸의 주소를 새로운 Node 왼쪽 주소에 연결한다.

Insertion in a singly linked list

• a~b의 연결된 주소를 끊고 중간에 새로운 x를 삽입하여 주소를 연결할 수 있다.

Deletion in a singly linked list

• a~c의 주소를 연결하여 b를 삭제할 수 있다.
• 수정, 삽입, 삭제, 탐색 모두 O(n)의 시간복잡도를 가지고 있다.

동적 배열(Dynamic Array)

• Python에서의 array는 다른 언어와 달리 정적 배열이 아닌 동적 배열이다.
• 동적 배열은 필요에 따라 확장하거나 축소할 수 있다. (일명 마법의 가방? 도라에몽 주머니?)
• 정적 배열과 달리 런타임 중 크기가 변경 될 수 있다.
• 동일한 배열에 다양한 유형의 요소를 허용할 수 있다.
• 파이썬의 동적 배열 리스트

리스트 생성	대괄호와 요소를 사용하여 리스트 생성.	my_list = [1, 2, 3, 'a', 'b', 'c']
요소 접근	인덱싱을 사용하여 요소에 접근 (0부터 시작).	element = my_list[2]
슬라이싱	리스트에서 일부 요소 추출.	sub_list = my_list[1:4]
요소 추가	리스트 끝에 요소 추가.	my_list.append(4)
요소 삽입	리스트의 특정 인덱스에 요소 삽입.	my_list.insert(2, 'x')
리스트 확장	다른 리스트의 요소를 현재 리스트에 추가.	my_list.extend(['d', 'e', 'f'])
요소 제거	값 또는 인덱스를 기반으로 리스트에서 요소 제거.	my_list.remove('a') del my_list[1]
요소 pop	특정 인덱스에서 요소를 제거하고 반환.	popped_element = my_list.pop(2)
인덱스 찾기	값의 첫 번째 발생 위치의 인덱스 찾기.	index = my_list.index('b')
멤버십 확인	값이 리스트에 존재하는지 확인.	is_present = 'x' in my_list
카운트	값이 나타나는 횟수 세기.	occurrences = my_list.count('b')
정렬	리스트를 오름차순 또는 내림차순으로 정렬.	my_list.sort() my_list.sort(reverse=True)
뒤집기	리스트의 요소 순서 뒤집기.	my_list.reverse()
복사	리스트의 얕은 복사 생성.	copied_list = my_list.copy()
제거	리스트에서 모든 요소 제거.	my_list.clear()
리스트 컴프리헨션	간결한 표현을 사용하여 새 리스트 생성.	squared_numbers = [x**2 for x in my_list]

출처: 정적 배열, 동적 배열 : 초보자도 파이썬으로 이해하는 자료구조

---

무엇을 느꼈고 내일은 무엇을 할까?

스쿼드 세션의 이해를 높이기 위해서 최대한 빨리 알고리즘 강의를 들어야겠다.