파이썬6 이진 탐색 트리 (binary search tree) → 딕셔너리, 세트를 구현할 때 쓸수있다. 그 이유는 뒤에서 살펴 보겠다. 이진탐색트리속성 부모 노드 왼쪽에는 무조건 부모노드보다 작은 자식노드가 들어가고 부모노드 오른쪽에는 부모노드보다 무조건 큰 자식 노드가 들어간다. 배열이나 파이썬리스트로 구현하지 않고 노드 인스턴스를 연결해서 구현 모든 자식노드가 부모의 레퍼런스를 저장하고 있다. InOrder 순회를 하면 데이터의 값이 순서대로 출력된다. ⇒ ABCDEFGHI 삽입연산 새로운 노드 생성 루트 노드부터 비교하면서 저장할 위치 찾음 찾은 위치에 새롭게 만든 노드 연결 시간복잡도 : O(h) h=높이 탐색연산 주어진 노드의 데이터와 탐색하려는 데이터 비교 탐색하려는 데이터가 더 크면 노드의 오른쪽 자식으로간다. 탐색하려는 데이터가 더 작으면 노드의 왼.. 2024. 1. 19. 객체 지향 프로그래밍 (OOP) _ 상속 & 다형성 파이썬을 기반으로 작성되었습니다 상속 부모의 메소드와 변수를 그대로 받아 사용할수있다. 이를 활용하면 코드 중복을 줄일 수있다. 상속은 아래와 같이 가능하다. class Cashier(Employee): pass help 함수를 통해 calss를 자세히 볼 수있다. 파이썬에서 모든 class는 자동으로 Builtins.object Class를 상속받는다. mro 메소드 해당 인스턴스의 클래스가 어떤 부모 클래스를 가지는 지 보여준다. ⇒ 클래스가 상속받는 부모 클래스들이 순서대로 담긴 리스트를 리턴 들여쓰기 에러인 IndetationError를 출력하면 다음과 같이 나온다 print(IndentationError.mro()) [, , , , ] isinstance 함수 어떤 인스턴스가 주어진 클래스의 인.. 2024. 1. 17. 객체 지향 프로그래밍 (OOP) _ 추상화 & 캡슐화 파이썬을 기반으로 작성되었습니다. 추상화 프로그래머들이 특정코드를 사용할때 필수적인 정보를 제외한 세부사항을 가리는 것 추상화 팁 추상화를 할 때는 클래스 변수 메소드 이름을 잘 지어야한다. 추상화는 문서화를 잘해야한다. help(class)를 하면 Docstring 내용을 확인 할수있다. 타입 힌팅을 적어서 개발자들에게 어떤 타입을 사용하는지 알려준다. type hinting : 변수뒤에 “:” 을쓰고 타입을 작성한다. 함수는 “→” 을 쓰고 타입을 작성한다. 타입 힌팅은 작동하는데 문제는 없지만 개발자들에게 어떤 타입을 사용해야하는지 도움을 준다. 캡슐화 객체의 일부 구현 내용에 대한 외부로 부터의 직접적인 액세스를 차단하는 것 객체의 속성과 그것을 사용하는 행동을 하나로 묶는것 클래스에서 숨기고 싶.. 2024. 1. 16. 힙 형태 속성 : 힙은 완전 이진 트리 (완전 이진 트리의 높이 O(lg(n))) 힙 속성 : 모든 노드의 데이터는 자식 노드들의 데이터 보다 크거나 같다. 정렬 알고리즘 : 데이터를 재배치하는 구체적인 방법 힙 구현하기 완전 이진 트리이기 때문에 동적 배열로 구현 ⇒ 파이썬에서는 동적 배열을 활용한 리스트로 구현 왼쪽 자식 인덱스 : 인덱스 * 2 오른쪽 자식 인덱스 : 인덱스*2+1 Heapify 원하는 노드를 힙속성에 맞는 위치로 재배치 시키는 알고리즘 시간 복잡도 O(lg(n)) 주어진 리스트를 힙으로 만들기 ⇒ 가장 맨마지막 노드부터 루트 노드까지 heapify를 호출해준다. → 역순으로 heapify를 호출해주면 부분트리마다 힙속성을 만족시키고 올라가기 때문에 모든 노드를 힙속성에 맞출수있고 힙이.. 2024. 1. 12. 추상 자료형 기능과 구현 기능 : 연산이 무엇을 하는지 구현 : 연산의 기능을 어떻게 하는지 추상 자료형 자료구조를 추상화 한 것 -> 데이터를 저장, 사용할 때 기능만 생각 추상화 구현을 몰라도 기능만 알면 프로그래밍을 할수있게 해주는 개념 자료구조는 구현까지 알아야해서 생각할 부분이 기능 뿐만 아니라 구현까지 해서 복잡해지지만 추상 자료형은 기능에만 집중 할 수있기 때문에 조금더 생각을 줄일 수있다. ⇒ 추상 자료형을 생각하면 코드의 흐름에 집중 할 수있다. 파이썬 추상화가 많이된 고수준 언어 많은 자료형 이름이 추상 자료형 리스트 데이터간 순서 관계를 유지 할 수있다. 접근 연산 : 특정 위치에 있는 데이터를 가지고 오거나 수정한다. 탐색 연산 : 특정 조건을 만족하는 데이터를 찾는다. 삽입 연산 : 특정 위치.. 2024. 1. 11. 이전 1 2 다음
