출처 : 코딩테스트 [ ALL IN ONE ]
1. set 과의 차이점
set은 순서가 달라도 상관없지만 list는 순서가 매우 중요하다.
2. list의 종류
- Array list
- Array
- Dynamic array
배열을 기반으로 만들어져 있는 리스트
- Linked list
연속적은 아니지만 연결되어있는 리스트
파이썬은 Array리스트를 기본으로 한다. 만약 Linked list를 쓰려면 노드를 만들어줘야 한다. 또한 Array list는 Array Dynamic array로 나뉘지만 이것은 c언어의 영역이지만 파이썬의 list는 Dynamic Array로 구현이 되어 있다. 이 Dynamic array는 Array로 이루어져 있다. 즉 파이썬의 list를 알려면 Array부터 알아야한다
3. 배열
3-1. 배열의 특성
- 고정된 저장 공간
- 순차적인 데이터 저장
int arr[5] = {3,7,4,5,6}
이 예시에서는 배열 size를 5로 정했기 때문에 int 형 데이터 4byte 5개를 저장할 메모리 20Byte를 미리 할당 받는다.
4바이트식 할당된 상황이다. 만약 첫번째 index인 3을 찾아가고 싶으면 arr이 첫번째 주소값을 가지고 있기 때문에 각각의 index를 잘 찾아갈 수 있다.
3-2. Random access
메모리에 저장된 데이터에 접근하려면 주소값을 알아야 합니다. 배열변수는 자신이 할당받은 메모리의 첫 번째 주소값을 가리킵니다. 배열은 연속적/순차적으로 저장되어 있기 때문에 첫 주소값만 알고 있다면 어떤 index에도 즉시 접근이 가능합니다. 이를 direct access 또는 random access라고 부릅니다. 첫 번째 데이터가 저장된 주소값이 0x4AF55라면 2번 째 데이터는 0x4AF55 + 41(byte)에 저장되어 있겠죠. 3번 째 데이터는 0x4AF55 + 42(byte)에 저장되어 있을 것이고, n번 째 데이터는 0x4AF55 + 4*(n-1)에 저장되어 있을 겁니다. 아무리 긴 배열이더라도 한번의 연산으로 원하는 데이터에 바로 접근할 수 있습니다. 즉 O(1)의 시간복잡도를 갖습니다.
다음에 배울 linked list는 메모리상에서 연속적/순차적으로 저장되어 있지 않기 때문에 random access는 불가능 합니다. $n$번 째 데이터에 접근하기 위해서 array는 1번의 연산으로 되지만($O(1)$), linked list는 $n$번의 연산을 해야 하기 때문에 시간복잡도는 $O(n)$이 됩니다.
3-2-1. static array의 한계
데이터의 갯수가 정해져 있는 경우에는 static array를 사용하는 것이 매우 효율적입니다. 하지만 선언시 정한 size보다 더 많은 데이터를 저장해야하는 경우 공간이 남아있지 않아서 문제가 발생할 수 있다. 그렇다고 매번 큼 array를 선언하면 메모리 낭비가 심해진다 이것을 해결할 수있는 것이 dynamic array이다.
3-3. Dynamic array(동적배열)
- 정적배열 : 선언 후 사이즈 변경 x
- 동적배열 : size 조절 가능
3-3-1. Dynamic array 특징
동적배열은 배열의 크기를 변경할 수 있는 배열입니다. 기존에 할당된 사이즈를 초과하게 되면, size를 늘린 배열을 새로 선언하고 그곳으로 모든 데이터를 옮긴다. 그리고 기존의 배열 메모리에서 삭제한다. 이 과정을 reszie라고 한다. 기본적으로 resize를 하면 두배 더큰 크기로 하기 때문에 이것을 doubling이라고 한다.
<aside> 💡 파이썬에서는 list자료형을 통해 dynamic array를 이미 구현해놓았기 때문에 직접 구현할 필요가 없습니다. 즉 문제에서 배열을 사용해야하는 경우에는 list를 사용하면 됩니다.
</aside>
4. 파이썬 list 활용
# list 선언
a = [1, 2, 3]
print(a[0]) # 1 O(1)
a[1] = 9 # [1, 9, 3] O(1)
a.append(4)
a.append(5)
# 여기 까지 O(1) 이미 어디에 넣어야할지 알고 있음!
# 배열이 가득찼다고 가정할때 6을 넣으려고 하면 resize 과정을 거친다 O(n)의 시간 복잡도 걸림!
# 이렇게 O(n)의 상황이 가끔 발생한다면 분활상환 기법으로 인하여 O(1) 의 시간이 걸린다고 한다.
a.append(6)
# 데이터를 지우는것은 O(1) 맨 마지막 index가 어디인지 알고있기 때문에!
a.pop()
a.pop()
# 원래 요소들은 뒤로 밀고 해당 자리에 10을 넣어야한다. 그래서 O(n)
a.insert(1,10) # 1번 index에 10을 넣으려고 하는것
# 중간에 데이터를 삭제하는 것도 마찬가지!
a.pop(2)
4-1. 분활상환기법
O(n)의 상황이 가끔 발생한다면 분활상환 기법으로 인하여 O(1) 의 시간이 걸린다고 한다.
4-2. 결론
Static arrayDynamic array
| access / update | $O(1)$ | $O(1)$ |
| insert_back | $O(1)$ | amortized $O(1)$ |
| delete_back | $O(1)$ | $O(1)$ |
| insert_at | $O(n)$ | $O(n)$ |
| delete_at | $O(n)$ | $O(n)$ |
1. set 과의 차이점
set은 순서가 달라도 상관없지만 list는 순서가 매우 중요하다.
2. list의 종류
- Array list
- Array
- Dynamic array
배열을 기반으로 만들어져 있는 리스트
- Linked list
연속적은 아니지만 연결되어있는 리스트
파이썬은 Array리스트를 기본으로 한다. 만약 Linked list를 쓰려면 노드를 만들어줘야 한다. 또한 Array list는 Array Dynamic array로 나뉘지만 이것은 c언어의 영역이지만 파이썬의 list는 Dynamic Array로 구현이 되어 있다. 이 Dynamic array는 Array로 이루어져 있다. 즉 파이썬의 list를 알려면 Array부터 알아야한다
3. 배열
3-1. 배열의 특성
- 고정된 저장 공간
- 순차적인 데이터 저장
int arr[5] = {3,7,4,5,6}
이 예시에서는 배열 size를 5로 정했기 때문에 int 형 데이터 4byte 5개를 저장할 메모리 20Byte를 미리 할당 받는다.
4바이트식 할당된 상황이다. 만약 첫번째 index인 3을 찾아가고 싶으면 arr이 첫번째 주소값을 가지고 있기 때문에 각각의 index를 잘 찾아갈 수 있다.
3-2. Random access
메모리에 저장된 데이터에 접근하려면 주소값을 알아야 합니다. 배열변수는 자신이 할당받은 메모리의 첫 번째 주소값을 가리킵니다. 배열은 연속적/순차적으로 저장되어 있기 때문에 첫 주소값만 알고 있다면 어떤 index에도 즉시 접근이 가능합니다. 이를 direct access 또는 random access라고 부릅니다. 첫 번째 데이터가 저장된 주소값이 0x4AF55라면 2번 째 데이터는 0x4AF55 + 41(byte)에 저장되어 있겠죠. 3번 째 데이터는 0x4AF55 + 42(byte)에 저장되어 있을 것이고, n번 째 데이터는 0x4AF55 + 4*(n-1)에 저장되어 있을 겁니다. 아무리 긴 배열이더라도 한번의 연산으로 원하는 데이터에 바로 접근할 수 있습니다. 즉 O(1)의 시간복잡도를 갖습니다.
다음에 배울 linked list는 메모리상에서 연속적/순차적으로 저장되어 있지 않기 때문에 random access는 불가능 합니다. $n$번 째 데이터에 접근하기 위해서 array는 1번의 연산으로 되지만($O(1)$), linked list는 $n$번의 연산을 해야 하기 때문에 시간복잡도는 $O(n)$이 됩니다.
3-2-1. static array의 한계
데이터의 갯수가 정해져 있는 경우에는 static array를 사용하는 것이 매우 효율적입니다. 하지만 선언시 정한 size보다 더 많은 데이터를 저장해야하는 경우 공간이 남아있지 않아서 문제가 발생할 수 있다. 그렇다고 매번 큼 array를 선언하면 메모리 낭비가 심해진다 이것을 해결할 수있는 것이 dynamic array이다.
3-3. Dynamic array(동적배열)
- 정적배열 : 선언 후 사이즈 변경 x
- 동적배열 : size 조절 가능
3-3-1. Dynamic array 특징
동적배열은 배열의 크기를 변경할 수 있는 배열입니다. 기존에 할당된 사이즈를 초과하게 되면, size를 늘린 배열을 새로 선언하고 그곳으로 모든 데이터를 옮긴다. 그리고 기존의 배열 메모리에서 삭제한다. 이 과정을 reszie라고 한다. 기본적으로 resize를 하면 두배 더큰 크기로 하기 때문에 이것을 doubling이라고 한다.
<aside> 💡 파이썬에서는 list자료형을 통해 dynamic array를 이미 구현해놓았기 때문에 직접 구현할 필요가 없습니다. 즉 문제에서 배열을 사용해야하는 경우에는 list를 사용하면 됩니다.
</aside>
4. 파이썬 list 활용
# list 선언
a = [1, 2, 3]
print(a[0]) # 1 O(1)
a[1] = 9 # [1, 9, 3] O(1)
a.append(4)
a.append(5)
# 여기 까지 O(1) 이미 어디에 넣어야할지 알고 있음!
# 배열이 가득찼다고 가정할때 6을 넣으려고 하면 resize 과정을 거친다 O(n)의 시간 복잡도 걸림!
# 이렇게 O(n)의 상황이 가끔 발생한다면 분활상환 기법으로 인하여 O(1) 의 시간이 걸린다고 한다.
a.append(6)
# 데이터를 지우는것은 O(1) 맨 마지막 index가 어디인지 알고있기 때문에!
a.pop()
a.pop()
# 원래 요소들은 뒤로 밀고 해당 자리에 10을 넣어야한다. 그래서 O(n)
a.insert(1,10) # 1번 index에 10을 넣으려고 하는것
# 중간에 데이터를 삭제하는 것도 마찬가지!
a.pop(2)
4-1. 분활상환기법
O(n)의 상황이 가끔 발생한다면 분활상환 기법으로 인하여 O(1) 의 시간이 걸린다고 한다.
4-2. 결론
Static arrayDynamic array
| access / update | $O(1)$ | $O(1)$ |
| insert_back | $O(1)$ | amortized $O(1)$ |
| delete_back | $O(1)$ | $O(1)$ |
| insert_at | $O(n)$ | $O(n)$ |
| delete_at | $O(n)$ | $O(n)$ |
'Java 개념' 카테고리의 다른 글
| getter, setter2 (0) | 2023.07.02 |
|---|---|
| 클래스1탄(클래스, 인스턴스변수, 클래스 변수, 메소드, 오버로딩, 클래스 메소드, this, 생성자) (0) | 2023.06.29 |
| Method (0) | 2023.06.20 |
| 배열 (0) | 2023.06.19 |
| 별찍기 (0) | 2023.06.19 |
