파이썬, 자료구조 알고리즘, array & list

 

알고리즘을 공부하면서.. 어렵고.. 힘이 빠졌다. 개념도 개념이지만..  예제문제를 보면 헛웃음이 나왔다.. '여러분 여기로 가면 됩니다' 하고 지도를 줬는데, 응?... 이게 뭐야 .. 어디로 가라는 거야..  뭘 하라는 거야.. 이런 생각 때문에..

난.. 코드 구현은 고사하고  문제를 이해하는 데만 많은 시간을 썼다.

 

근데 우재튜터님이 알고리즘은 그럴 수 있다고.. 차근차근 진도를 따라가는 과목이 아니라고. 그 말씀을 들으니 불안했던 마음이 편안하게 불안해졌다.

 

아무튼 방향성을 바로잡고 다시.. 공부해보기로..

 

먼저, 단기적으로 알아야 하는 자료구조들을 살펴보자. 적어도 여기서 선형구조와 비선형구조 안에 있는 자료구조는 꼭 알아야 한다.

자료구조를 안다는 건, 이 자료구조가 어떤 데이터를 저장하기 위한 녀석인지 그리고 어떤 연산들을 할 수 있는 녀석인지를 정확하게 알고 있어야 한다는 의미다.

 

예를 들어, stack 이면

 

stack이 선형 구조의 데이터 라는 걸 알아야 하고

이 자료구조에 쓰이는 연산에 push, pop 이 있고 어떤 기능을 하는지 알아야 한다.

• push: 스택의 top에 요소 추가
• pop: 스택의 top 요소 제거 그럼 제거만 해? 제거하면서 값을 반환까지 해? 제거하고 반환까지 해

정확하게 알고 있어야 한다. 

---

 

 

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

 

우재튜터님 말씀처럼, 난 업무자동화과정 때부터 배열만 나오면 쫄았다. 리스트랑 헷갈렸기 때문이다. 비슷한 것 같은데 언제 array 를 쓰고 언제 list 를 쓰는 걸까..🤔 궁금하고 답답했다. 근데 c언어부터 배운 사람은 이 두 개를 절대 헷갈릴 수가 없다고 한다. 

 

그치만 오늘로서 이 헷갈림이 끝났다. ㅎㅎ

---

 

배열(Array)

Indexed-based implemetation

 

array의 가장 큰 특징은 인덱스! 

 

array는 1, 2, 3, 숫자 세개를 정하면 정확히 딱 세 칸의 저장공간을 만든다. 세개의 인덱스 위치가 만들어진다는 의미다.

즉, array에는 빈자리가 없다. 4를 추가하거나 삭제하려면 리스트처럼 그냥 넣거나 뺼 수 없고, 새로운 array를 만들어야 한다.

 

이처럼 인덱스는 배열(array)에만 있는 속성값이다. 

 

• 선형 자료구조 (1차원 자료구조)
• 고정된 크기를 가진다
• 배열에는 동일한 데이터 타입만 들어갈 수 있다.
• 각 요소는 하나의 인덱스에 매핑된다.
• 연속된 메모리 블럭에 할당한다 (그렇기 때문에 인덱스 값이 존재한다) 

 

그럼, Array의 연산은 어떨까?

 

• 삽입 / 수정 / 삭제 

 

→ 만약, 초기 순서를 유지하면서 삽입을 해야 한다면?

 

하나씩 뒤적뒤적 찾아서 다 밀고, 삽입을 해줘야 할거니까 O(n)

 

→ 만약 특정 원소를 삭제한다면?

 

인덱스 값을 알고 있다 하더라도 결국 너 누구니? 너 누구니? 뒤적뒤적 찾아야하니 O(n)

 

→ 만약 특정 원소를 찾아야 한다면?

 

얘도 마찬가지로 너 맞니? 너 맞니? 너 맞니?.. 하나하나 찾아야 하니까 O(n)

 

 

이렇듯 기본적으로 O(n) 인데,

array가 정렬이 된 경우라면 이분탐색을 통해 O(n)을 O(log n)으로 바꿀 수 있다.

 

 

 

 

만약, array를 쓰는데 길이가 계속 늘어날 것 같아.. 추가도 계속 될 것 같고 수정이나 삭제도 계속 될 것 같아.. 

그럴 때 Linked List를 쓴다.

 

 

Linked List

Pointer-based implemetation

 

• 선형 자료구조 (1차원 자료구조)
• 가변 크기를 가질 수 있음
• 모든 요소는 동일한 데이터 타입을 가짐
• 비연속된 메모리 블럭에 할당

 

그럼 우리가 맨날 쓰는 파이썬의 list 는 뭔데.. 뭐가 다를까? 하는 궁금증이 생긴다.

 

 

List 리스트

• 리스트는 파이썬에서 가장 일반적으로 사용하는 동적배열(dynamic array)이다.
• 필요한 만큼 크기를 자동으로 조절한다
• 다양한 데이터 타입 저장이 가능하다. 

리스트 안에 있는 데이터 타입 예시: int, str, float, list)

mixed_list = [1, 'string', 3.14, [1, 2, 3]]

•  요소를 추가, 삭제, 변경할 수 있다.
• 인덱싱과 슬라이싱을 지원하여 특정요소에 접근하거나 부분 리스트를 추출할 수 있다.
• 다양한 내장 메서드를 제공하여 요소 추가, 삭제, 정렬, 역순으로 변경 등의 작업을 지원한다.

주요 메서드: append(), remove(), extend(), sort(), reverse() 등

 

 

 

그리고 인덱스 접근, 요소 추가, 삭제, 삽입, 길이, 정렬, 결합, 반복, 검색 등 다양한 연산에 따른.. 리스트의 빅오를 구하고싶은데 너무 졸리다.ㅠㅠ 내일.. 다시..