Java로 배우는 자료구조

부스트코드 '자바로 구현하고 배우는 자료구조'정리 1주차 - 자바 특성 및 알고리즘 기본 1.복잡성 (1) 자료구조란? 종류 - Array, Linked List, Stack&Queue, Hash Table, Tree 자료 형태 *Array *Linked List

부스트코드 '자바로 구현하고 배우는 자료구조'정리 1주차 - 자바 특성 및 알고리즘 기본 [2]Java Object Oriented Programming 1) 상속(Inheritence)과 클래스(Class) *객체의 메모리 할당 :int(4Bytes),long(8B

강의명: Java로 구현하고 배우는 자료구조 2주차-연결리스트 2-1.연결리스트란? -주 사용처: 순차적인 데이터나 많은 양의 데이터 처리 목적)많은 양의 데이터를 적은 양의 메모리를 사용하여 저장 *Node 구성요소: 'next'란 이름의 포인터 + 'data'를

2주차-연결리스트 2-4. addFirst 메소드 2-5. addLast 메소드 2-6. removeFirst 메소드 2-7. removeLast 메소드

2주차. 연결리스트2-8. remove와 findfind 메소드 - Comparable 인터페이스를 통해 노드 찾기\-> Remove에서 파생(경계조건 신경X)현재 코드가 null이 아닌지 파악 후 존재 여부를 반환한다<find 메소드>찾는 노드가 포함되는가rem

3주차. 해시3-1. 해시 소개\*메소드(&시간복잡도)add, remove, lookup/find, change, set = 데이터에 따라 달라짐all entries, all keys, all values = O(n)size, isEmpty, isFull, lo

3주차. 해시3-4. 해시 함수에서의 문자열=>Hash에 문자열을 넣는 경우, 출력이 어떻게 되는가?문자열 출력\-모든 문자(ASCII의 경우,영어에서 사용하는 문자 한정)는 숫자로 표현 가능하다(by ASCII,유니코드)\*ASCII\*유니코드문자열을 해시로 표현\-

3주차. 해시3-7. LoadFactor메소드(적재율)적재율(λ) \-테이블(해시)에 데이터가 얼만큼 있는가즉,배열의 크기에 비해 데이터는 얼만큼 찼는가 보여준다\-적재율 = 항목(data) 수 / 자료구조의 크기\+)적재율 = number of entries / to

4주차 해시23-10. 재해싱(Rehashing)\-의미: chain hash에서 해시가(배열이) 너무 많이 차면 위 사진처럼 배열의 크기를 조정해야 한다Chain hash에서 적재율이 1 이상이 될 수 있지만 그렇다고 해서 너무 커지면 안된다이유: 연결리스트 내에 무

4주차 해시3-13. 생성자\-내부 클래스인 HashElement에 알았으면, 이제 Hash 생성자를 만들어보자!생성자를 통해 사용자가 테이블의 크기를 설정한다연결리스트가 골고루 퍼지게 만들려면 테이블의 크기 조정이 빈번해야 한다=> 최대 적재율과 테이블의 크기는 테이

4주차 해시3-16. getValue 메소드\-Key의 값인 value를 얻는 메소드\-key의 index를 찾고서 해시에서 그 index를 찾은 뒤, 동일하면 그 때 key에 해당하는 value를 return한다\-getValue의 메소드에서 해당하는 key는 입력값

4주차. Heap4-1. 힙과 트리 소개트리\-트리에 있는 각각의 요소는 '노드'라 불린다\-루트(root)와 자식(leaf)으로 이루어져 있다\-루트를 통해 트리 안으로 들어간다(연결리스트의 head처럼)\-서로 연결된 것들끼리 부모-자식(parent-child) 관

4주차. 힙4-4.TrickleUp 함수완전이진트리로 노드의 위치는\-children: 2 parent + 1, 2 parent + 2\-parent: floor((child - 1) / 2)로 모든 노드가 level 순서 정렬로 위치가 잡힌다.ex)<코드>생

5주차 Tree4-7. 트리: 완전트리/정트리Complete 트리:완전이진트리 형태에서 자식 노드가 left->right 순으로 노드가 채워지는 트리로, 마지막 level은 완전히 채워지지 않은 형태Full 트리:완전이진트리 형태에서 마지막 level까지 자식 노드가

5주차 Tree 4-11. 트리: 재귀 함수 트리에 데이터 추가하는 방법: 재귀함수! 트리에 새 데이터 추가하는 방법 1.root에서 시작하여 추가할 위치 찾기 2.추가할 위치로 null인 부분을 찾았다면 그 곳에 새 노드 추가 -> 이 과정에서 재귀함수를 이용해 트리

5주차-Tree 4-14.트리:회전 '회전'이란? -균형 잡힌 트리를 만들기 위해 트리의 노드 위치를 바꾸는 과정 균형 잡힌 트리란? > 연결리스트처럼 한 방향으로 나열된 트리가 아닌 상태로, 시간복잡도는 균형잡지 않은 트리보다 빠르다 (균형잡힌 트리(O(logn))

5주차. AVL Tree & Red Black Tree5-1. AVL 트리 소개5-2. 노드5-3. add 메소드5-4. 재귀 add 메소드

5주차. AVL Tree & RB Tree5-5. 균형 확인 메소드트리의 높이 차를 확인, 균형을 맞추는 메소드: checkBalance 메소드<코드>5-6. Rebalance 메소드5-7. adding data 예제

5주차. AVL Tree & BR Tree:트리의 균형을 맞추는 방법5-8 규칙Red Black Tree \-자가 균형 이진 탐색 트리로, 스스로 균형을 잡는 트리 \-모든 노드는 빨간색 or 검은색으로 표시(현 강의에서는 색이 아닌 T/F로 표현)\-규칙에 어긋나면

5주차. RB Tree<코드 구현>5-11 add 메소드 with RB Tree:AVL Tree와 동작 방식은 동일하나 몇 가지 추가하여 이를 관리해야 한다<코드>:key-value가 있는 코드에서 비교할 경우, 보통 key만 비교:isLeftChild가 원

5주차. RB Tree5-14 좌측 회전5-15 좌측-우측 회전5-16 높이5-17 검은색 노드 갯수

6주차 정렬(Sort)현재 숫자들을 순서대로 정렬하는 경우만 다룬다. 물론 문자열이나 객체 모두 정렬 가능6-1. 정렬 소개(정렬 알고리즘)정렬: 만약 숫자 리스트가 있을 때, 어떻게 숫자를 배치할 것인가정렬 분류정렬할 때, 데이터 처리방식:out-of-place 정렬

6주차 정렬6-5. 셀 정렬Shell Sort:일정한 너비 내 요소들과 대소 비교하며 정렬하는 방식 \-점차 정렬할수록 너비의 간격이 좁아지며 마지막에는 1이 된다.\-간격이 1이 되면 삽입 정렬 시작\-마지막까지 정렬 후 합치는 방식으로 마무리\-이러한 정렬 방식으로

7주차-정렬(2)6-8. 퀵 정렬퀵 정렬(Quicksort)\-중심점(Pivot Point)를 임의로 선정 후, 이를 가지고 왼쪽: Pivot Point보다 작은 수 오른쪽: Pivot Point보다 큰 수로 분류하여 정렬하는 방법\-왼쪽과 오른쪽은 서로 비교할 필요X