2-2/파이썬, 자료구조

이진 탐색 알고리즘 = 정렬된 데이터로 된 리스트에서 찾고자 하는 데이터가 있는지 알아보는 알고리즘 (리스트를 인수로 받음) if 모든 요소 순회 -> O(n) !! 노답 이진 -> O(log n) !! 굳 방식: 중간값과 타깃을 비교 -> 중간값이 크면 좌측으로이동해서 또 중간값비교 이거계속 그래서 결국 중간값=타깃 되면 그 인덱스 리턴 *리스트는 정렬되어있다고 가정 이진 탐색 트리 (데이터 삽입, 삭제, 탐색 모두 빠른거 !!) 이진트리 -> 특별한 형태의 연결리스트. 부모는 두 자식의 참조를 가지고 있고, 자식은 부모의 참조를 가지고 있음 이진탐색트리는 노드에 데이터 직접 저장 x , 데이터에 대한 참조만 저장함 중요한 것은 데이터가 아니라, 이 데이터의 참조를 저장하고 있는 노드를 나타내는 키! ..

트리 = 사이클(엣지를타고 자기자신으로 돌아오는거)이 없는 연결된 그래프 ! * 무조건 e=n-1 ! if e>n-1 -> 사이클이 생겨서 트리아님 !! -차수 = 자식노드 개수 / 트리의 차수=트리에 있는 노드의 최대 차수 이진트리 : 노드의 자식이 최대 두개인 트리 ! 여기서 *n레벨의 노드 최대 갯수 : 2의 n-1 승 *트리(높이: h) 에서 -노드 최대 갯수: (2의h승) -1 -노드 최소 갯수: h 포화 이진트리 : 다 찬거. 최대로 있는거 완전 이진 트리: 높이가 h일때, h-1까진 다채워져있고(노드(2^n-1) -1 개), 노드가 왼쪽에서 오른쪽으로 채워지는 트리 편향 이진 트리: 왼쪽이나 오른쪽 서브트리만 가진 트리(쭉쭉쭉 하나씩만) 이진트리의 순회 ! - 모든 노드 방문하기 ^.^ ->..

표현 1. 인접 리스트 점개수만큼 길이의 배열잇음 (배열의 인덱스 = 정점) 이 배열의 각 요소는 각 해당 정점의 연결리스트를 담고잇음 연결리스트 = 그 정점의 인접한 정점의 집합 예를들어 정점1이 2,3과 연결되어잇으면 배열의 인덱스1의 요소로는 [2,3]이 있는거 (각 정점이 연결된 점의리스트를 배열로담고있다. 이때 인덱스가 해당 정점이다) 모든 노드 탐색하기 ! 1. 너비 우선 탐색 BFS 출발점과 인접한 정점들 모두 방문 -> 그 정점과 인접한 정점 모두 방문 큐에 넣엇다가 하나씩 빼서쓰는 형식으로 !! 2. 깊이 우선 탐색 DFS 갈곳 없어지면 하나 전 정점으로해서 쭉 감! 시작 정점으로 돌아온 후 더이상 갈 곳 없어야만 실행 종료됨 1 ) 재귀함수 -> 스택프레임 쌓이는 걸 이용하기 함수가 하..

덱 : front, rear에서 모두 입출력이 가능함 -파이썬이 제공함 -이걸로 스택, 큐 모두 구현 가능함 -양끝 접근, 삭제 추가 = O(1) -중간에 있는 애들 접근 = O(n) ** 이중 연결 리스트를 이용해서 구현되어 있다**

큐 = 줄서기 first in, first out ! 양쪽 뚤림 ~ 앞에꺼가 날라감 구현방법 1. 동적 배열로 2. 원형큐 * 비어있는 길이 정해져있는 리스트 만들기 [None, None, None, None, None, None, None, None, None, None] = [None] * 10 [None for _ in range(10)] *파이썬이 제공 ! from queue import Queue enqueue: put() dequeue: pop()

스택: 데이터를 차곡차곡 쌓는다 ! 차곡차곡 위로 쌓고, 나갈때는 맨 위에잇는(마지막에들어온)애부터 나간다 따로 모듈 제공x. 리스트그냥 쓰면 돼서 (pop(), append() 사용하면 그대로임) -> 그치만 헷갈림 어떤 의미로 리스트를 썻는지 알수없음 (동적배열 / 스택) -> 따로 추상화를 해줍니다 *비어잇는 리스트 생성방법 a=list() *a[-1]은 문자열에서와 마찬가지로 리스트 a의 마지막 요솟값을 말한다.

*사실 파이썬은 캡슐화를 지원하는 언어는 아님 ! (private x) 클래스 없어도 괜찮은 언어 *클래스에서 self 파라미터엔 아무것도 안넣어도되는거임 캡슐화 =인스턴스를 생성했을 때 일부 구현 내용에 대한 외부로부터의 직접적인 엑세스를 차단하는것입니다. = 캡슐처럼 객체 내부를 숨겨 외부로부터의 엑세스를 차단하는 것 ways 맹글링 -> 완벽은 x _변수 -> 개발자들 사이의 약속 @property 데코레이터 사용내부 보호하기 위해 데이터 접근 메서드를 따로 만들어 주는 것! property ? = 어떤 처리를 해준 속성 @property라는 키워드를 이용해서 클래스 변수를 속성으로 선언하고 하나의 메소드를 통해서 쉽게 get / set 할 수 있습니다 *메서드를 통해서 값을 가져오는 것 =gett..

데코레이터 https://dojang.io/mod/page/view.php?id=2427 파이썬 코딩 도장: 42.1 데코레이터 만들기 Unit 42. 데코레이터 사용하기 파이썬은 데코레이터(decorator)라는 기능을 제공합니다. 데코레이터는 장식하다, 꾸미다라는 뜻의 decorate에 er(or)을 붙인 말인데 장식하는 도구 정도로 설명할 수 있습 dojang.io 데코레이터는 기존 함수를 수정하지 않으면서 추가 기능을 구현할 때 사용함. 그리고 그 추가기능 함수 = 데코레이터 함수안에 함수가있는 형태고 return 안의함수 해야함 @데코레이터함수이름 은 아무변수이름=데코레이터(기존함수) 와 같음 데코레이터 = 메소드를 매개변수로 받아서 기존함수에 부가적인 기능을 추가하여 사용할 수 있도록 함 _ ..

연결리스트 중간에 삽입, 삭제 good ! O(1) -> 요소들이 다음꺼를 가리키고 있다 ! (포인터를 담고잇다) *중간요소 삭제시 : 해당 객체를 가리키는 객체가 0개면 그 객체 자동으로 지워짐 ! 탐색 bad -> 하나하나씩 다 탐색해야함 ! 인덱싱같은 연산 x -> O(n) 더미 이중 연결 리스트 직접 구현

*stack, heap heap 영역이 동적 ! 동적 배열 = 리스트 (파이썬의 배열) (파이썬의 배열은 동적이다 !!) 탐색 기능이 막강(인덱싱->한번에 찾음) & 마지막에서 삽입, 연산 good ! * 중간에 삽입/삭제시 원소들 옮겨야됨 ㅜㅜ ADT operation .is_empty()기능 -> [] 빈 리스트 자체가 false임 .insert(index, n) [] .pop() ->마지막 원소 삭제 후 그 원소 반환 .pop(index) -> 인덱스 원소 삭제 후 반환 .append(n) :맨뒤에 추가 .remove(아이템) -> 배열안에 그 아이템 있으면 그거 삭제 특징 -> 선형적으로 이어져있다 -> 캐시히트가 발생시 시간 매우 절약 ! (캐시로가져올때 주변 데이터까지 같이 가져오므로, 배열은..