Computer Science (17) 썸네일형 리스트형 전공 필기 공부 2주차 1.이진 탐색트리에 대한 공부 ( 특징, 정의, 삽입, 시간복잡도 등) 2.전위순회, 후위순회, 중위순회에 대한 개념 공부 3.오버라이딩과 오버로딩의 차이점 4.해시함수와 이중해싱 개념 공부 5,레드 블랙 트리에 대한 개념 공부 6.퀵정렬 개념 학습 [Algorithm] AVL 트리 한쪽으로 치우친 편향 이진트리가 되면 트리의 높이가 높아지기 때문에이를 방지하고자 높이 균형을 유지하는 AVL 트리를 사용한다.AVL 트리 = 자가 균형 이진 탐색 트리 특징이진 트리의 속성을 가진다왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1이다어떤 시점에서 높이 차이가 1보다 커지면 회전(rotation)을 통해 균형을 잡아 차이를 줄인다AVL 트리는 높이를 logN으로 유지하기 때문에 삽입, 검색, 삭제의 시간복잡도는 O(logN)이다균형(밸런스) 잡는 방법Balance Factor를 사용한다. 이는 왼쪽과 오른쪽의 자식(노드)의 높이 차이를 뜻하는 말이다. 균형인수라고도 한다.균형 인수의 절대 값이 클수록 트리의 균형이 무너진 것이다. 트리를 균형있게 만들어야 하는 이유트리의 높이가 h라면 이진.. [Algorithm] 삽입 정렬 삽입정렬 개념구현 코드시간 복잡도삽입 정렬 Insertion Sort 란?자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입하는 알고리즘손안의 카드를 정렬하는 방법과 유사처음 Key 값은 두 번째 자료부터 시작 구현 코드def insertion_sort(arr): for i in range(1, len(arr)): key = arr[i] j = i-1 # key가 정렬된 부분에서 적절한 위치를 찾을 때까지 비교하고 이동 while j >= 0 and key 시간 복잡도 : O(N^2) 최선의 경우이동 없이 1번의 비교만 이루어짐외부 루프 : (n-1)번Best T(n) =.. [Algorithm] 버블 정렬 버블정렬 개념구현 코드시간복잡도개념인접한 두 원소를 검사하여 정렬하는 알고리즘뒤에서부터 앞으로 정렬해나가는 구조 구현 코드def bubble_sort(arr): for i in range(len(arr)-1, 0, -1): for j in range(i): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] 시간 복잡도 : O(N*2)루프문으로 맨 뒤부터 맨 앞까지 모든 인덱스에 접근 -> O(N)하나의 루프에서는 인접한 값들의 대소 비교 및 자리 교대 -> O(N)=> O(N^2) 최적화이전 패스에서 앞뒤 자리비교(swap)이 한 번도 일어나지 않았다면 정렬되.. [Algorithm] 해시충돌 해결방법과 각각의 특징 해시 충돌이란?해시 테이블에서 서로 다른 키 값이 동일한 해시 값을 갖는 현상 주요 해결 방법체이닝 : 같은 해시 값 → 리스트에 이어 붙이기 개방 주소법 : 같은 해시 값 → 테이블 내 다른 빈칸 찾아 저장하기 체이닝 (Separate Chaining)같은 해시 주소에 여러 개의 키가 할당되면, 해당 주소에 연결리스트(Linked List)나 다른 자료구조를 두어 충돌된 키들을 저장하는 방식이다 원리해시 테이블의 각 버킷(bucket)이 연결 리스트, 동적 배열, 혹은 트리 구조를 가진다같은 해시값이 나면 그 버킷의 리스트에 추가특징삭제가 간단: 버킷 내부 자료구조에서만 제거하면 됨부하율(α = n / 버킷 수) > 1도 가능최악의 경우(모두 같은 해시값) 한 버킷에 n개가 몰려 O(n)장점구현 단순,.. [Algorithm] B Tree, B+ Tree 개념차이점삽입과 삭제 과정시간복잡도B Tree 개념B-트리(B-tree)는 데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종으로, 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다. 모든 키는 정렬돼 있고, 탐색·순차접근·삽입·삭제가 모두 O(log n)에 가능하도록 높이(h)를 매우 낮게 유지한다.이 구조는 디스크/페이지 I/O를 최소화하려고 고안됐고, DB와 파일시스템 인덱스의 표준이다. 최대 M개 자식을 가질 수 있는 B-Tree를 M차 B-Tree라고 부른다. [ DB 인덱스로 B(+)-트리를 채택하는 이유 ]메모리는 랜덤 접근이 빠르지만, 디스크/SSD는 페이지 단위 접근 비용이 크다.B-트리는 한 노드(=한 페이지)에 많은 키를 .. [Algorithm] 이진 최소 힙 (heapq) 1. 이진최소힙 개념2. 삽입과 삭제 과정3. 각 경우의 시간복잡도 정리개념완전이진트리 형태의 힙이며, 각 노드가 부모 보통 배열로 구현 (인덱스 i의 왼/오 자식 : 2i, 2i+1)* python의 heapq 모듈은 이진 최소 힙을 기반으로 동작함 삽입 과정def insert_min_heap(heap, value): heap.append(value) idx = len(heap) - 1 while idx > 0 and heap[(idx-1)//2] > heap[idx]: heap[idx], heap[(idx-1)//2] = heap[(idx-1)//2], heap[idx] idx = (idx-1)//2 heap =.. (공부중) 객체지향 디자인패턴 OOP (객체지향 프로그래밍)특성캡슐화상속추상화다형성설계원칙 (SOLID)Single Responsibility Principle (SRP) : 클래스는 하나의 역할만 해야한다Open Close Principle (OCP)The Liskov Substitution Principle (LSP)Interface Segration Principle (ISP)Dependency Inversion Principle (DIP)디자인 패턴각 패턴이 무엇이며, 어떤 경우에 사용하는지 예시 정도 알아두기생성 패턴1) Singleton객체가 하나만 만들어져야 하는 경우 사용e.g) 전체 페이지에 똑같이 적용되는 다크모드클래스 안의 static이 아닌 변수나 메소드들은 객체가 생성될 때마다 메모리 공간을 새로 차지하지만st.. 이전 1 2 3 다음
