[알고리즘] 배열

배열

 

배열은 차원과 무관하게  컴퓨터 메모리 구조에 따라 1차원 공간에 연속 할당된다. 배열은 임의 접근이라는 방법으로 배열의 모든 위치에 있는 데이터에 단 한 번에 접근할 수 있다. 따라서 데이터에 접근하기 위한 시간 복잡도는 O(1)이다.

 

• 맨 뒤에 삽입할 경우: O(1)
• 맨 앞/중간에 삽입할 경우: O(N)(N은 밀어야하는 데이터 개수)

 

배열 선택 시 주의사항: 시간 복잡도 뿐만이 아니라 메모리 크기도 확인하자.

1. 할당할 수 있는 메모리 크기를 확인해야 한다. 데이터가 너무 많으면 런타임에서 배열 할당에 실패할 수 있다. 보통 정수형 1차원 배열은 1000만 개, 2차원 배열은 3000 * 3000 크기를 최대로 생각.
2. 중간에 데이터 삽입이 많은지 확인해야 한다. 맨 앞/중간에 데이터를 빈번하게 삽입하면 시간 복잡도가 높아져 시간 초과가 발생할 수 있다.

 

리스트에 데이터 추가

1. my_list.append(4): 맨 끝에 데이터 추가
2. my_list = my_list + [4, 5]: 맨 끝에 다른 리스트의 데이터 추가
3. my_list.insert(2, 9999): 특정 위치에 데이터를 삽입: 첫 번째 인수에 데이터를 삽입할 위치를 받고, 두 번째 인수에 삽일할 데이터를 받는다.

 

리스트에 데이터 삭제

1. popped_element = my_list.pop(2): pop() 메서드는 팝할 데이터의 인덱스를 인수로 받아 삭제하고, 삭제할 데이터의 값을 반환.
2. my_list.remove(2): remove() 메서드는 특정 데이터 자체를 삭제. 인수로 받은 값이 처음 등장하는 위치의 데이터를 삭제.
3. square = [num**2 for num in numbers]: 리스트 컴프리헨션, 연산 대상 리스트 자체를 바꾸지 않고 연산이 끝난 리스트를 반환한다.

 

Tip.

1. 리스트 전체 데이터 개수를 반환하는 len()함수: len(fruits)
2. 특정 데이터가 처음 등장한 인덱스를 반환하는 index() 메서드, 없으면 -1 반환: fruits.index(“banana”) (그런데 이 경우 문자열에서는 불가능하다.)
3. 사용자가 정한 기준에 따라 리스트 데이터를 정렬하는 sort() 메서드: fruits.sort(), 제자리 정렬로 원본 리스트를 정렬한다. 아무런 인수가 없으면 오름차순, fruits.sort(reverse=True)이면 내림차순이다.  sorted(fruits)의 경우는 원본 리스트 그대로 두고 정렬한 새로운 리스트를 반환한다. 시간 복잡도는 O(NlogN). 제자리 정렬은 원본을 직접 정렬하고 반환값이 None, 비제자리 정렬은 새로운 리스트를 반환하고 원본 리스트는 변경되지 않음.
4. 특정 데이터 개수를 반환하는 fruits.count(“apple”) 메서드

 

시간복잡도: O(1) < O(log N) < O(N) < O(N log N) < O(N²) < O(2^N) < O(N!) 

 

O(1) → 상수 시간 (가장 빠름)

O(log N) → 로그 시간 (예: 이진 탐색)

O(N) → 선형 시간 (예: 단순 반복문)

O(N log N) → 선형 로그 시간 (예: 병합 정렬, 퀵 정렬 평균)

O(N²) → 이차 시간 (예: 중첩 반복문, 버블 정렬)

O(2^N) → 지수 시간 (예: 피보나치 재귀)

O(N!) → 팩토리얼 시간 (예: 순열 완전 탐색)

 

🚀 정렬 알고리즘(O(N log N))보다 중첩 반복문(O(N²))이 느리고, 지수적 증가(O(2^N))는 매우 비효율적! 따라서, 가능하면 O(N) 또는 O(N log N) 알고리즘을 선택하는 것이 좋다.