배열 Array
- 삽입/삭제 : O(N)
- 탐색: O(1)
- C++에서는 size 변경 불가
- Python은 리스트를 사용 -> 담는 요소를 다양하게 담을 수도 있고 사이즈도 다양하게 변경이 가능함
c++
int arr[4] = (10, 11, 12, 13);
arr[2] = 5;
#Python
arr = [10, 11, 12, 13]
arr[2] = 5
arr[2] 라는 코드를 쓰면 arr 의 시작 인덱스가 있을거고 + (2 * 4byte) = 메모리주소값으로 계산해서 점프하게 됨
배열의 주소 계산 공식 (주소 = 배열 시작 주소 + (인덱스 * 자료형 크기)
한번에 메모리 주소값이 어디있는지 한번에 계산할 수 있기 때문에 탐색 속도가 굉장히 빠름 그래서 O(1) 임 이걸 임의 접근 이라고 함
📌 💡 왜 O(1)인가? ✔ 배열의 시작 주소와 인덱스만 알면, 연산 한 번으로 바로 해당 요소에 접근 가능!
✔ 반복적인 탐색이 필요하지 않음 → 탐색 속도가 일정함 (O(1))
배열은 메모리 공간에 연속적으로 할당되므로 임의 접근이 가능해서 그래서 탐색 속도가 빠름
| arr[0] | 10 | 0x1000 |
| arr[1] | 20 | 0x1004 |
| arr[2] | 30 | 0x1008 |
| arr[3] | 40 | 0x100C |
| arr[4] | 50 | 0x1010 |
➡️ 각 요소가 연속된 메모리 공간을 차지하고 있음
➡️ 배열의 시작 주소(arr = 0x1000)를 알면, 원하는 위치를 바로 계산할 수 있음
✅ 만약 데이터를 삽입하려면?
✅ 1. 배열에서 삽입 연산의 시간 복잡도 (O(N))
만약 배열의 중간에 값을 삽입하면, 기존 요소들을 오른쪽으로 한 칸씩 이동해야 함.
즉, 최악의 경우 모든 요소를 이동해야 하므로 O(N)의 시간 복잡도를 가짐
✅ 예제: 인덱스 2에 6 삽입 (O(N))
arr = [1, 2, 3, 4, 5]
arr.insert(2, 6) # 2번 인덱스에 6 삽입
print(arr) # [1, 2, 6, 3, 4, 5]
✅ 동작 과정
- 3 → 3을 arr[3]으로 이동
- 4 → 4를 arr[4]으로 이동
- 5 → 5를 arr[5]으로 이동
- arr[2]에 6 삽입
📌 💡 최악의 경우 (맨 앞에 삽입하면)
✔ 모든 요소를 오른쪽으로 이동해야 하므로 O(N)
✅ 2. 배열에서 삭제 연산의 시간 복잡도 (O(N))
만약 배열의 중간 요소를 삭제하면, 나머지 요소들을 왼쪽으로 한 칸씩 당겨야 함
즉, 최악의 경우 모든 요소를 이동해야 하므로 O(N)의 시간 복잡도를 가짐
✅ 예제: 인덱스 2의 요소 삭제 (O(N))
arr = [1, 2, 6, 3, 4, 5]
arr.pop(2) # 2번 인덱스 삭제
print(arr) # [1, 2, 3, 4, 5]
✅ 동작 과정
- arr[3] → arr[2]으로 이동 (3이 arr[2]로 옴)
- arr[4] → arr[3]으로 이동
- arr[5] → arr[4]으로 이동
📌 💡 최악의 경우 (맨 앞 요소를 삭제하면)
✔ 모든 요소를 왼쪽으로 이동해야 하므로 O(N)
만약에 2번인덱스에 6을 넣고싶다면 모든 현재 인덱스에 있는 값들을 전부 오른쪽으로 이동시켜줘야함
✔ Python의 list 는 동적 배열이라 크기 변경이 가능하지만, 내부적으로 새로운 배열을 만들고 데이터를 복사하는 방식
따라서 0개부터 ~ N 개 미뤄줄 수 있음 시간복잡도를 따질 때는 최악일 때로 따지기 때문에 O(N)의 시간 복잡도를 갖게된다.
삭제도 마찬가지임 최악의 경우 N 개를 다 당겨야할 수도 있기 때문에 O(N)의 시간복잡도를 갖게 된다.
이러한 삽입 삭제를 N번만큼 하게 되면 결국 N의 제곱에 해당하는 시간복잡도를 갖게됨
✅ 3. 여러 번 삽입/삭제 연산을 수행할 경우 (O(N^2))
만약 삽입/삭제 연산을 N번 수행하면, 각 연산이 O(N)이므로 최종적으로 O(N^2)의 시간 복잡도가 됨.
✅ 예제: N개의 삽입 연산 (O(N^2))
arr = []
for i in range(1000): # 1000번 삽입
arr.insert(0, i) # 매번 맨 앞에 삽입 (최악의 경우 O(N))
✔ O(N)의 삽입을 N번 반복하므로 O(N^2)
✅ 예제: N개의 삭제 연산 (O(N^2))
arr = list(range(1000))
for _ in range(1000): # 1000번 삭제
arr.pop(0) # 매번 맨 앞 요소 삭제 (최악의 경우 O(N))
✔ O(N)의 삭제를 N번 반복하므로 O(N^2)
따라서 탐색을 많이 하는 경우는 배열을 사용하는 것이 좋은데 삽입과 삭제를 하는 경우에는 다른 자료구조를 사용하는 것이 유리하다.
v = []
v.append((123, 456))
v.append((789, 987))
print("size:", len(v))
for p in v :
print(p)
위와 같은 경우에는 무엇이 출력될까?
✅ 1. 튜플(Tuple)이란?
➡️ 튜플(Tuple) 은 여러 개의 값을 저장할 수 있는 자료구조이며, 한 번 생성하면 수정할 수 없는(immutable) 데이터 타입
➡️ 리스트(list)와 비슷하지만, 튜플은 변경이 불가능(Immutable)한 점이 차이점
📌 💡 쉽게 말하면?
✔ 리스트(list)는 수정 가능 (mutable) → 요소를 추가/삭제 가능
✔ 튜플(tuple)은 수정 불가능 (immutable) → 요소를 변경할 수 없음
✅ 튜플 예제 (소괄호 () 사용)
✅ 튜플과 리스트의 차이
✅ 2. 튜플의 특징
🔹 (1) 순서가 있는 자료형 (Ordered)
✔ 리스트처럼 튜플도 순서(order)를 유지
✔ 인덱스를 통해 요소에 접근 가능
✅ 예제: 인덱스로 접근
🔹 (2) 변경이 불가능 (Immutable)
✔ 한 번 생성된 튜플의 요소를 수정할 수 없음
✔ 요소를 변경하려면 새로운 튜플을 생성해야 함
✅ 예제: 튜플 수정 불가능
✅ 튜플을 수정하려면 새로운 튜플을 만들어야 함
🔹 (3) 여러 데이터 타입 저장 가능
✔ 튜플은 서로 다른 자료형을 함께 저장할 수 있음
✅ 예제: 다양한 데이터 타입 저장
🔹 (4) 패킹(Packing)과 언패킹(Unpacking) 가능
✔ 패킹(Packing): 여러 개의 값을 하나의 튜플로 묶기
✔ 언패킹(Unpacking): 튜플을 여러 개의 변수로 분해
✅ 예제: 패킹
✅ 예제: 언패킹
✅ 3. 튜플 vs 리스트 비교
비교 항목 리스트(list) 튜플(tuple)| 변경 가능 여부 | 가능 (mutable) | 불가능 (immutable) |
| 요소 추가/삭제 | 가능 (append(), remove()) | 불가능 |
| 인덱싱 | 지원 | 지원 |
| 반복문 사용 | 가능 | 가능 |
| 메모리 사용량 | 큼 | 작음 (최적화됨) |
| 실행 속도 | 느림 | 빠름 |
| 사용 예시 | 동적인 데이터 관리 | 고정된 데이터 저장 |
📌 💡 리스트와 튜플을 선택하는 기준
- 데이터를 변경할 필요가 있으면 list 사용
- 변경할 필요가 없고, 빠른 실행이 필요하면 tuple 사용
✅ 튜플이 더 유리한 경우
✅ 리스트가 더 유리한 경우
연결 리스트 Linked List
- 삽입/삭제: O(1)
- 탐색: O(N)
다른 자료구조들을 구현할 때 많이 쓰인다.
연결리스트는 배열과 반대임 왜 그럴까?
메모리 상에 어디에 존재하는지 확정 지을 수 없음
1이 어디있는지는 0이 알고 있고 2가 어디있는지는 1이 알고 있음 그래서 한단계 한단계 노드를 거쳐가야함
그래서 O(N)으로 느리게 됨
그러면 삽입 삭제는?
삽입하려는 위치 이전 이후에서만 관계를 맺어주면 됨
'자료구조' 카테고리의 다른 글
| [자료구조] 첫번째 공부 (0) | 2024.11.23 |
|---|