해당 코드는 'Do-it 자료구조와 함께 배우는 알고리즘 입문 - 파이썬편'을 공부한 내용입니다.
각 단원별로 중요하다고 여기는 부분을 작성한 파일입니다
자료구조: 데이터 단위와 데이터 자체 사이의 물리저또는 논리적인 관계 즉, 자료구조는 데이ㅣ터가 모여 있는 구조 + 컴퓨터에서 처리해야하는많은 데이터를 모아 효율적으로 관리하고 구조화
annotations 주석과 같음, 그냥 자료형을 명시해주는 표현
1_Array
저장된 데이터에서 원하는 자료를 찾는 방법:
- 최댓값 찾기: max
- 반복문 사용: for, while (+ enumerate) 데이터 형태
- 뮤터블: 리스트(list), 딕셔너리(dict), 집합(set) - 변경가능
- 이뮤터블: 수(number - int,float .etc), 문자열(String), 튜플(tuple) - 변경불가능 linear search (number2)//(number1): 1로 2를 나눈 몫 (number2)%(number1): 1로 2를 나눈 나머지
y = x.copy() shallow copy : 리스트 x가 참조하는 곳이 다르면 y도 달라진다 (참조 복사)
import coy y = copy.deepcopy(x) deep copy: 참조값 뿐만 아니라 참조하는 객체 자체를 복사 (전체 복사)
2_Search
keyword: key, value, sorted_data, complelxity idea: 반복을 통해 값을 찾음 반복문 자체가 적거나 반복문을 끝내는 조건문이 적을 수록 효과적
- 선형 검색(linear search): 무작위로 늘어놓은 데이터 집합에서 검색을 수행 O(n)
- 이진 검색(binary search): 일정한 규칙으로 늘어놓은 데이터 집합에서 아주 빠른 검색을 수행 O(log(n))
- 해시법: 추가, 삭제가 자주 일어나는 데이터 집합에서 아주 빠른 검색을 수행 체인법: 같은 헤시값 데이터를 연결 리스트로 연결하는 방법 오픈 주소법: 데이터를 위한 해시값이 충돌할 떄 재해시하는 방법
3_stack&queue
데이터를 임시로 저장하는 자료구조
stack - LIFO(Last In Frist Out) push, pop, top, bottom, capacity, ptr top - push and pop, bottom is_empty(), is_full() list형, array형으로 쉽게 구현 가능
queue - FIFO(First In First Out) enqueue - rear, dequeue - front list형, array형으로 쉽게 구현 가능 - ring buffer 구조
4_recursive 자기 자신을 포함하여 다시자기 자신을 사용 factorial이 좋은 예시 직접 재귀: 자신과 똑같은 함수를 호출하는 방식 a() -> a() -> ... 간접재귀: a() -> b() -> a() -> ...
- 하향식 분석(top-down analysis): 가장 위쪽에 위치한 상자의 함수 호출부터 시작하여 계단식으로 자세히 조사해 나가는 분석 방법
- 상향식 분석(bottom-up analysis): 반대
5_sort 정렬: 이름,학번,학점 등의 키를 항목값의 대소 관계에 따라 일정한 순서로 바꾸어 늘어놓는 작업 쉬운 검색 가능
-
오름차순: 작은 값 -> 큰 값
-
내림차순: 큰 값 -> 작은 값
-
종류: 버블 정렬, 단순 선택 정렬, 단순 삽입 정렬, 셸 정렬, 퀵 정렬, 병합 정렬, 힙 정렬, 도수 정렬
-
내부 정렬: 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우
-
외부 정렬: 정렬할 데이터가 많아 하나의 배열에 저장할 수 없는 경우
-
버블 정렬: 이웃한 두 원소의 대소 관계를 비교하여 필요에 따라 교환을 반복, 단순 정렬
-
쎼이커 정렬: 양방향 버블 정렬
-
단순 선택 정렬: 정렬되지 않은 부분에서 최소 값을 찾아 나열
-
단순 삽입 정렬: 순차적으로 원소를 선택하여 정렬되어 있는 배열에 삽입
-
이진 삽입 정렬: 이진검색을 통해 빠른 위치 검색
-
셸 정렬: 배열의 원소를 그룹으로 나눠 각 그룹별로 정렬을 수행, 그 후 정렬된 그룹을 합치는 작업을 반복 :단순삽입 정렬의 경우 정렬이 거의 끝나는 상태에서는 매우 빠름, 삽입할 위치가 멀리 떨어져 있으면 이동 횟수가 많아짐
-
퀵 정렬: partition and sort
-
병합 정렬: 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합
-
힙 정렬: 루트의 삭제와 재구성
6_string_search 어떤 문자열 안에 다른 문자열이 포함되어 있는지 검사, 위치 파악
- 텍스트: 검색되는 문자열
- 패턴: 찾아내는 방법