1. 버블 정렬인접한 원소를 비교한 다음, 내가 원하는 정렬이 아니다! 하면 교환.처음부터 마지막까지 쌍 비교.이렇게.. n-1개의 쌍을 비교하면, 가장 큰 애는 가장 끝으로 이동하게 됨.그 후, n-2개의 쌍(젤 큰 애는 비교 안 함. 이미 제자리임.)을 비교하면, 두 번째로 큰 애가 가장 큰 애의 옆으로 위치하게 됨.즉, (n-1)+(n-2)+...+(1) = n(n-1)/2 번 비교. 2. 선택 정렬우선, 주어진 배열에서 최댓값 찾아서 맨 뒤로 보냄.최댓값 뺀 나머지 배열에서 최댓값 찾아서 맨 뒤에서 한 칸 앞으로 보냄.이런 식으로 진행되는 건데, 계속 교체하진 않으므로 버블 정렬보단 효율적. 3. 삽입 정렬얘는 우선 1번째 원소부터 비교를 시작한다.0번째 원소와 비교해서, 1번째 원소의 위치를 정..
AI/자료구조
히프보통 힙(최대힙) : 리프-루트 경로를 따르는 모든 키가 오름차순으로 되어있는 완전 이진 트리어떤 키도 부모보다 크지 않음. * 최소힙 : 부모키가 자식키보다 작 히프화 연산히프 특성 만족하도록 시퀀스 원소들 재배열하는 것.리프-루트 경로 따라 인접한 두 개 이상의 원소를 회전 우선순위 큐원소의 우선순위에 삭제 연산이 수행되는 큐어떤 것이 높은 우선순위를 가지는지 결정하기 위해 원소들 간의 비교가 가능하다는 것을 가정하고 있음.일반적 큐 : 선입선출(FIFO), 우선순위 큐 : 최적입선출(BIFO)어떤 것을 먼저 넣느냐가 중요한 게 아니라, 그냥 우선순위인 것이 먼저 나감.따라서 힙을 이용하는 것이 편함! 즉, 연산이 어떻게 진행되냐면,삽입 : 주어진 원소를 넣으면, 트리의 말단에 넣어짐. 여기서 히..
Binary Search Tree각각의 노드가 BST 특성을 만족하는 키-주소 쌍을 가진 이진 트리각 키에 대해,왼쪽 서브트리의 모든 키는 이보다 작고,오른쪽 서브트리의 모든 키는 이보다 크다.모든 요소는 키를 가지고 있는데, 이 키는 유일하다.만약, 이 BST를 중위순회(왼-루트-오)한다면 오름차순 방문하는 것. BST 검색(삽입)검색 : 만일 BST가 공백이면 null 반환. 삽입 : 만일 BST가 공백이면 단독 트리 만들고 true 반환 검색(삽입)하려는 key가 root.key보다 작으면 왼쪽 서브트리 순환 탐색, 아니면 오른쪽 서브트리 순환 탐색 해서 검색이면 그 값을 찾고,삽입이면 들어갈 자리를 찾음 검색 : 값 없으면 false 반환삽입 : 이미 BST에 있는 키면 false 반환 * BS..
이진트리란?공집합이거나, x가 루트이고 L/R 중 어느것도 x를 포함하지 않는 분리된 이진트리일 때, 삼원소 쌍(x, L, R)두 서브트리 L/R이 "왼쪽"과 "오른쪽"이라는 이름으로 구분이진트리의 모든 공백이 아닌 노드는 반드시 왼쪽 서브트리와 오른쪽 서브트리를 가져야 함.서브트리는 모두 공백 가능특성포화 이진트리 크기 = 2^(h+1) - 1이진트리 크기 범위 : h+1 이진트리 높이 : floor(lg(n)) 크기가 2인 2개의 이진 트리 : 노드 2개로 나타낼 수 있는 두가지크기 3인 5개 이진트리카탈로니아 수 : 이진 트리 개수 세는 데 사용되는 폐쇄형 공식 (2n)!/n!(n+1)! 수식 트리수식트리 표현법!수식트리를 표현한 후, 이 수식트리를..
트리란?공집합이거나 r이 노드이고, S가 서로 분리된 트리의 집합일 때, 어떤 트리도 r을 포함하지 않는 쌍 (r, S) 이다.노드 r : 트리의 루트 degree : subtree 집합의 크기. 즉, 자식노드 개수. degree가 0인 노드 == leaf node루트경로 : 루트로부터 해당 노드까지 유일한 경로루트-리프경로 : 루트에서 리프에 이르는 경로경로의 길이 : 부모자식 쌍의 개수. 즉, 노드개수 -1트리 경로길이 : 모든 노드의 깊이의 합공백트리 : 유일하게 크기 0인 트리단독트리 : 크기가 1인트리트리 높이 : 최장 루트경로 길이노드 깊이 : 노드까지의 루트경로 길이트리 너비 : 최대 레벨 크기레벨 : 주어진 깊이에서의 모든 노드노드 차수 : 자식들 개수트리 차수 : 최대 노드 차수포화 트리..
원소 접근법1. 순차접근- 연결리스트에 의한.- 선형시간2. 직접접근- 배열에 의한- 상수시간- 인덱스 관련 사전지식 필요 해시테이블인덱스 관련 사전지식 없이, 직접접근 가능!How?원소 내용을 입력, 인덱스를 출력으로 하는 해시함수 이용 레코드- 여러 컴포넌트(이름+타입) 가진 자료구조- 일부 언어에서는 레코드가 배열같은 표준 타입으로 사용 테이블 - 동일 타입의 레코드 집합(순서 x) 키 테이블- 기본키 역할의 "키필드"를 레코드 타입이 포함하는 테이블 맵- 보유 레코드의 컬렉션 각 ADT의 연산키 레코드맵Initialize키 보유 레코드 생성(초기화)공백 맵 생성(초기화)key레코드 키 객체 반환 value레코드 값 객체 반환 update레코드 값 객체 대체레코드 있으면 updatesearch 테이..
java에서 Iterator가 뭘까?Iterator (반복자)반복적인 작업을 수행하는 것. - Main.javapublic class Main{ public static void main(String[] args){ ArrayList numbers = new ArrayList(); numbers.addLast(10); numbers.addLast(20); numbers.addLast(30); numbers.addLast(40); for(int i=0;i - ArrayList.javapublic Object removeFirst(){ return remove(0);}public Object removeLast(){ return remove(size-1);}public Object ..
리스트 : 선형적 컬렉션 (선형구조). 중복참조, null 가짐 리스트 클래스 List ClassArrayListLinkedList원소저장법배열연결리스트탐색상수시간선형시간삽입/삭제선형시간상수시간 List IteratorㄴㅇㄹWrapper Class"객체"가 요구되는 자리에 기본형 데이터를 쓰고 싶을 때.ex) 객체가 요구되는 자리인데, int를 쓰고 싶음. 근데 int는 객체가 아니다. 그래서 이의 wrapper class인 Integer를 사용하면 됨.boxing : 기본형을 wrapper class 객체로 변환unboxing : wrapper class 객체를 기본형으로 변환 ex) Term, Polynomial 객체
