전체 글

객체파이썬은 모든 데이터를 객체(object)로 다룬다.정수, 실수, 문자열, 사용자 정의 클래스의 인스턴스 등 모든 데이터는 신원(id)과 타입(객체를 만든 클래스)을 가진다.ex) a= 100이라는 코드에서 100이라는 int 타입을 갖는 객체가 생성된다. 이때 a는 int 타입의 인스턴스가 되고 이 인스턴스는 신원과 타입을 변경할 수 없다. ▶Immutable 객체파이썬의 immutable 타입: int, float, str, bool, tuple 등값의 변경이 불가능한 객체/ 값의 변경을 시도하면 새 값을 가진 객체를 새로 생성하여 이를 가리키게 한다.다만 동일한 값을 쓸 경우 객체를 새로 생성하는 것이 비효율적이기 때문에 타입마다 값이 캐시되는 기준을 정해서캐시 되어 있는 값이면 같은 값의 기존..

※파이썬을 오랜만에 쓰기 앞서 빠른 복습을 위해 책을 한번 훑고까먹거나 부족한 부분을 채워 넣은 후 파이썬으로 백준 문제풀이를 할 예정입니다. 01 파이썬 시작하기 ▶식별자파이썬은 스네이크 케이스와 캐멀 케이스를 둘 다 사용.첫글자가 소문자면 스네이크, 대문자면 캐멀 케이스 캐멀케이스면 클래스- 식별자는 숫자로 시작 x- 파이썬 주석은 # 02 자료형●02-1 자료형과 문자열type() 함수로 자료형 확인 ▶문자열("""ABCDEFGHIJ""") 결과 ABCDEFGHIJ ("""\ABCDEFGHIJ\""")위와 같이 \기호를 넣으면 첫 줄과 마지막 줄 출력 시 줄 바꿈 없음 : 슬라이싱 할 때는 마지막 숫자 포함x ex) 1:4이면 인덱스 1,2,3까지 ●02-2 숫자// 정수 나누기 연산자ex) 3/2..

14.5 개방 주소법 ● 충돌과 오버플로우 충돌: 서로 다른 키를 갖는 항목들이 같은 해시주소를 가지는 현상 오버플로우: 충돌이 발생했을 때 해당 해시 주소에 더 이상 빈 버킷이 남아있지 않아 항목을 저장할 수 없는 현상 오버플로우 해결하는 2가지 해결책 1. 개방주소법: 충돌이 일어난 항목을 해시 테이블의 다른 위치에 저장 2, 체이닝: 해시테이블의 하나의 위치가 여러 개의 항목을 저장할 수 있도록 해시테이블의 구조 변경 14.5절에서는 개방 주소법에 대해 다루고 14.6절에서 체이닝을 다룬다. ● 선형 조사법 조사(probing): 해시테이블에서 비어있는 공간 찾기 선형조사법: ht[k]에서 충돌이 발생했다면 ht[k+1]이 비어있는지 확인 후 비어있다면 삽입, 비어있지 않다면 ht[k+2] 확인 조..

14.1 해싱이란? ● 해싱: key에 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 직접 접근하는 탐색 - 해시 테이블: 키에 대한 연산에 의해 직접 접근이 가능한 구조 - 컴바일러가 사용하는 심볼 테이블, 철자 검사기, 데이터베이스 등에서 활용 - O(1)의 시간안에 탐색을 마칠 수 있음 14.2 추상 자료형 사전 ● 사전: (키, 값)의 쌍으로, 키와 관련된 값을 동시에 저장하는 자료구조. map이나 table로도 불림 키(key): 사전의 단어처럼 항목과 항목을 구별시켜주는 것 값(value): 단어의 설명에 해당 - 항목들의 위치는 상관없으며 키만 알고 있으면 항목에 접근하고 삭제할 수 있다. - 리스트는 위치에 의해 관리되는 자료구조인 반면, 사전은 오직 키에 ..

01 (3) 02 05(a) 03 (2) 04 100,00,000 경사트리일 경우, 최악의 경우는 O(n) 05(b) 06 07 생략 08 이진 탐색 트리는 정렬되어있지않은 배열을 못받기 때문에 AVL tree를 활용해 정렬시킨 후 해당 트리를 중위순회하며 arr[] 배열에 담아서 정렬한 숫자를 출력하였다. // 위는 AVL Tree code int arr[6]; int k=0; void inorder(AVLNode *root){ if(root !=NULL){ inorder(root->left); arr[k++] = root->key; inorder(root->right); } } int main(){ AVLNode *root = NULL; root = insert(root,30); root = inse..

13.4 이진 탐색 트리 이진 탐색은 자료들이 배열에 저장되어 있어 삽입과 삭제가 힘들다는 단점 존재 이진 탐색 트리는 삽입, 삭제가 빈번한 상황에서 사용 - 이진 탐색 트리는 트리가 균형 트리 일 때 O(log2n)의 시간 복잡도를, 균형 트리가 아닐 때는 최악의 경우 O(n)의 시간복잡도를 가짐 알고리즘 최악 평균 탐색 삽입 탐색 삽입 순차 탐색(정렬x) N N N/2 N 이진 탐색(정렬o) logN N logN N/2 이진 탐색 트리 N N logN logN 모든 항목이 균일하게 탐색된다는 가정 하에 평균 비교 횟수를 비교 좌측 트리와 같은 편향된 경사 트리는 (1+2+3+4+5+6+7)/7 = 4 우측 트리와 같은 균형트리는 (1+2+2+3+3+3+3)/7 = 2.4 따라서 이진 탐색 트리에서는 ..

13.1 탐색이란? ● 탐색: 탐색키와 데이터로 이루어진 여러 개의 항목 중에서 원하는 탐색키를 가지고 있는 항목을 찾는 것 - 탐색을 위해 사용되는 자료구조: 배열, 연결 리스트, 트리, 그래프 등 - 탐색 성능 향상을 위해 이진 탐색 트리와 같은 보다 진보된 방법으로 자료를 저장 및 탐색 항목: 탐색의 단위 (ex. 숫자, 구조체 ..) 탐색키: 항목과 항목을 구별시켜 주는 키 13.2 정렬되지 않은 배열에서의 탐색 ● 순차 탐색(sequential search): 하아목의 처음부터 마지막까지 하나씩 검사하여 원하는 항목을 찾아가는 방법 - 탐색 방법 중 가장 간단하고 직접적임 - 탐색의 범위는 low에서 high까지 함수의 매개변수로 주어짐 - 탐색에 성공하면 그 항목이 발견된 위치의 인덱스를 반환..

01 4 02 2 03 3 04 3 05 (1) 7 4 9 6 3 8 7 5 3 4 9 6 7 8 7 5 3 4 5 6 7 8 7 9 3 4 5 6 7 7 8 9 (2) 7 4 9 6 3 8 7 5 4 7 9 6 3 8 7 5 4 6 7 9 3 8 7 5 3 4 6 7 9 8 7 5 3 4 6 7 8 9 7 5 3 4 6 7 7 8 9 5 3 4 5 6 7 7 8 9 (3) 7 4 9 6 3 8 7 5 4 7 6 3 8 7 5 9 4 6 3 7 7 5 8 9 4 3 6 7 5 7 8 9 3 4 6 5 7 7 8 9 3 4 5 6 7 7 8 9 (4) 7 4 9 6 3 8 7 5 3 4 7 5 7 8 9 6 3 4 7 5 7 6 9 8 3 4 5 6 7 7 8 9 06 (1) 71 49 92 55 38 8..

12.6 합병 정렬 ● 합병 정렬의 개념 분할정복: 문제를 작은 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략 문제가 충분히 작지 않아 해결이 어렵다면 분할 정복 방법을 연속으로 재적용하여 더 작게 만들어 해결 합병 정렬의 단계 1. 분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할 2. 정복(Conquer): 부분 배열 정렬. 부분 배열의 크기가 충분히 작지 않으면 순환 호출로 분할 정복 재적용 3. 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 통합 작은 문제인 부분 배열에 대해서도 다시 합병 정렬을 순환적으로 적용하면 부분 배열을 정렬할 수 있다. ● 합병 정렬의 알고리즘 void merge_sort(int list[],int le..

12.1 정렬이란? ● 정렬: 대상을 크기순으로 오름차순이나 내림차순으로 나열하는 것(키 값을 기준으로) - 레코드: 정렬시켜야 할 대상 - 필드: 레코드의 구성단위 ex) 학생이라는 레코드의 필드는 이름, 학번, 주소, 등 - 키(key): 레코드와 레코드를 식별해 주는 역할을 하는 필드 ex) 학번 각 상황에서 가장 효율적인 정렬 알고리즘을 선택하여야 함 효율성의 기준 = 비교 연산의 횟수 + 이동 연산의 횟수 ● 효율성과 복잡성 단순하지만 비효율적인 정렬 알고리즘 (자료 개수가 적을 때 사용) - 삽입 정렬, 선택 정렬, 버블 정렬 등 복잡하지만 효율적인 정렬 알고리즘 - 퀵 정렬, 히프 정렬, 합병 정렬, 기수 정렬, 권정열 등 ● 내부와 외부 정렬 내부 정렬 - 정렬 전 모든 데이터가 메인 메모..