인공지능 사관학교 - 1주차 파이썬 (3일차)

파이썬 자료구조!

시간복잡도, 리스트, 딕셔너리, 집합

시간 복잡도 - 빅 오(Big-O) 표기법

O(1) 상수 시간 복잡도

• 입력 크기와 상관없이 일정한 시간이 걸리는 알고리즘

O(log n) - 로그 시간 복잡도

입력 크기가 커질수록 실행 시간이 로그 형태로 증가하는 알고리즘입니다. 이진 탐색 알고리즘이 대표

적입니다.

O(N) 선형 시간 복잡도

입력 크기에 비례하여 실행 시간이 증가하는 알고리즘입니다.

sum_array 함수는 배열의 모든 요소를 한 번씩 순회하며 합계를 계산합니다.배열의 크기가 N일 때, 순회하는 데 걸리는 시간은 N에 비례하므로 시간 복잡도는 O(N)입니다.

O(n log n) - 로그 선형 시간 복잡도

많은 정렬 알고리즘이 이 시간 복잡도를 가집니다.

O(n^2) - 이차 시간 복잡도

입력 크기가 커질수록 실행 시간이 제곱 형태로 증가하는 알고리즘입니다. 버블 정렬이 대표적입니다.

O(N^2).

설명: selection_sort 함수는 배열의 각 요소에 대해 나머지 요소들과 비교하여 최소값을 찾습니다.

첫 번째 요소를 정렬하는 데 N번 비교하고, 

두 번째 요소는 N−1번 비교하는 식으로 총

번의 비교를 수행하므로 시간 복잡도는 N^2 입니다.

O(2^n) - 지수 시간 복잡도

입력 크기가 커질수록 실행 시간이 지수 형태로 증가하는 알고리즘입니다. 피보나치 수열을 재귀적으로 계산하는 알고리즘이 대표적입니다.

O(n!) - 팩토리얼 시간 복잡도

가장 비효율적인 시간 복잡도로, 순열 생성 알고리즘이 이 시간 복잡도를 가집니다.

요약

• O(1): 상수 시간 복잡도 (예: 배열의 첫 번째 원소 접근)
• O(log n): 로그 시간 복잡도 (예: 이진 탐색)
• O(n): 선형 시간 복잡도 (예: 배열의 모든 원소 출력)
• O(n log n): 로그 선형 시간 복잡도 (예: 병합 정렬)
• O(n^2): 이차 시간 복잡도 (예: 버블 정렬, 선택 정렬)
• O(2^n): 지수 시간 복잡도 (예: 재귀적 피보나치 수열 계산)
• O(n!): 팩토리얼 시간 복잡도 (예: 순열 생성)

리스트 (파이썬 알고리즘 인터뷰, 121p)

리스트의 주요 특징

1. 순서가 있는 데이터 구조 (Ordered) : 리스트는 항목들이 입력된 순서대로 유지
2. 가변성 (Mutable) : 리스트는 생성된 이후에도 항목을 추가, 제거, 수정 가능
3. 중복 허용 (Allow Duplicates) : 리스트는 중복된 값을 허용
4. 다양한 데이터 타입 저장 가능 (Heterogeneous) : 리스트는 문자열, 숫자, 다른 리스트 등 다양한 데이터 타입을 저장 가능

리스트 생성

• 리스트는 대괄호를 사용하여 생성할 수 있다.

리스트의 기본 연산

1. 항목 접근 (Indexing):

 

2. 항목 변경 (Modifying):

 

3. 항목 추가 (Appending):

4. 항목 삽입 (Inserting):

5. 항목 제거 (Removing):

6. 항목 팝 (Pop):

7. 항목 포함 여부 확인 (Checking Membership):¶

 

리스트의 주요 메소드

슬라이싱

 

1. extend(): 리스트에 다른 리스트나 반복 가능한 객체의 모든 항목을 추가합니다.

2. sort(): 리스트를 정렬합니다.

 

3. reverse(): 리스트의 항목 순서를 반대로 뒤집습니다.

4. index(): 특정 항목의 첫 번째 인덱스를 반환합니다.

5. count(): 리스트 내에서 특정 항목이 몇 번 등장하는지 반환합니다.

리스트 활용 예제

• 리스트는 데이터를 저장하고 조작하는 데 매우 유용하며, 파이썬의 다양한 내장 함수 및 메소드와 함께 사용할 수 있습니다. 예를 들어, 리스트 컴프리헨션을 사용하면 리스트를 간결하고 효율적으로 생성할 수 있습니다.

연산	시간 복잡도	설명
len(a)	O(1)	전체 요소의 개수를 리턴한다.
a[i]	O(1)	인덱스 i의 요소를 가져온다.
a[i:j]	O(k)	i부터 j까지 슬라이스의 길이만큼인 k개의 요소를 가져온다. 이 경우 객체 k개에 대한 조회가 필요하므로 O(k)이다.
elem in a	O(n)	elem 요소가 존재하는지 확인한다. 처음부터 순차 탐색하므로 n만큼 시간이 소요된다.
a.count(elem)	O(n)	elem 요소의 개수를 리턴한다.
a.index(elem)	O(n)	elem 요소의 인덱스를 리턴한다.
a.append(elem)	O(1)	리스트 마지막에 elem 요소를 추가한다.
a.pop()	O(1)	리스트 마지막 요소를 추출한다. 스택의 연산이다.
a.pop(0)	O(n)	리스트 첫번째 요소를 추출한다. 큐의 연산이다. 이 경우 전체 복사가 필요하므로 O(n)이다. 나중에 다시 살펴보겠지만 큐의 연산을 주로 사용한다면 리스트보다는 O(1)이 가능한 데크(deque)를 권장한다.
del a[i]	O(n)	i에 따라 다르다. 최악의 경우 O(n)이다.
a.sort()	O(n log n)	정렬한다. 팀소트(Timsort)를 사용하며, 최선의 경우 O(n)에도 실행될 수 있다(팀소트는 6장의 156페이지 참고).
min(a), max(a)	O(n)	최소값/최댓값을 계산하기 위해서는 전체를 선형 탐색해야 한다.
a.reverse()	O(n)	뒤집는다. 리스트는 입력 순서가 유지되므로 뒤집게 되면 입력 순서가 반대로 된다.

 

딕셔너리 (파이썬 알고리즘 인터뷰, p128)

딕셔너리의 주요 특징

1. 키-값 쌍 (Key-Value Pairs): 딕셔너리는 각 항목이 고유한 키와 그에 대응하는 값으로 구성됩니다.
2. 비순차적 (Unordered): 딕셔너리는 항목들이 입력된 순서를 유지하지 않습니다. (파이썬 3.7부터는 입력된 순서를 유지합니다.)
3. 가변성 (Mutable): 딕셔너리는 생성된 이후에도 키-값 쌍을 추가, 제거, 수정할 수 있습니다.
4. 키는 유일해야 함 (Unique Keys): 딕셔너리의 키는 중복될 수 없습니다. 값은 중복될 수 있습니다.

 

딕셔너리의 기본 연산

1. 항목 접근 (Accessing Items):

 

 

2. 항목 추가 및 수정 (Adding and Modifying Items):

3. 항목 제거 (Removing Items):

 

딕셔너리의 주요 메소드

1. keys(): 딕셔너리의 모든 키를 반환합니다.

2. values(): 딕셔너리의 모든 값을 반환합니다.

 

3. items(): 딕셔너리의 모든 키-값 쌍을 반환합니다.

 

4. update(): 딕셔너리의 항목을 업데이트합니다.

 

 

딕셔너리 활용 예제

• 딕셔너리는 데이터 검색, 추가, 수정에 매우 효율적이며, 다양한 용도로 사용할 수 있습니다. 예를 들어, 특정 조건을 만족하는 항목만을 선택하거나, 데이터를 그룹화하는 데 사용할 수 있습니다.

집합 (Set)

1. 정의: 유일한 요소들의 모음입니다. 중복된 요소가 없으며, 순서가 없습니다.
2. 구문: {값1, 값2, 값3, ...} 형태로 선언합니다.
3. 특징:
   • 중복 없음: 중복된 요소가 저장되지 않습니다.
   • 순서 없음: 요소의 순서가 없습니다.
   • 빠른 멤버십 테스트: 특정 요소가 집합에 있는지 빠르게 확인할 수 있습니다.
   • 가변성: 요소를 추가, 삭제할 수 있습니다.

 

주요 차이점

1. 데이터 저장 방식:
   • 딕셔너리: 키와 값의 쌍으로 데이터를 저장.
   • 집합: 단순히 유일한 요소들만 저장.
2. 접근 방식:
   • 딕셔너리: 키를 사용하여 값에 접근.
   • 집합: 특정 요소가 집합에 있는지 여부만 확인.
3. 용도:
   • 딕셔너리: 매핑 관계를 유지할 때 유용.
   • 집합: 유일한 값들의 컬렉션을 관리할 때 유용.