gkss2tpt 님의 블로그

1. AVL TreeAVL 트리 : 알고리즘 개발자 이름인 Adelson-Velsky and Landis에서 따오 ㄴ이름균형 인수 BF(Balance Factor) : 왼쪽 서브트리의 높이에서 오른쪽 서브트리의 높이를 뺀 값| HL - HR | // AVLNode 클래스 정의class AVLNode { int key; int height; AVLNode left, right; AVLNode(int d) { key = d; height = 1; }}// AVLTree 클래스 정의public class AVLTree { private AVLNode root; // 유틸리티 함수: 노드의 높이를 반환 private int height(AVLN..

1. 이진 검색 트리(BST)검색을 위한 자료구조Key(유일한 값)이 트리의 자리가 됨 → 중복을 허용하지 않음왼쪽 서브트리에 있는 모든 키 값은 부모의 키 값보다 작다.오른쪽 서브트리에 있는 모든 키 값은 부모의 키 값보다 크다.키 값을 비교하는 기준은 자료의 종류에 따라 다를 수 있음키를 검색할 때 하나의 노드와 비교 후 크거나 작음에 따라 왼쪽 혹은 오른쪽 서브트리로 이동을 결정할 수 있음트리가 비교적 균형을 이루었다면 n개의 요소에서 어떤 키 값을 찾거나 찾는 데 실패하는 데 걸리는 시간은 평균적으로 O(log n)public interface SearchInterface { public T search(Comparable x); public void insert(Comparable x..

public class TreeNode { E data; TreeNode left; TreeNode right;}public class BinaryTree { private TreeNode root; public TreeNode makeBinaryTree(TreeNode rootNode) { root = rootNode; root.left = null; root.right = null; return root; } public TreeNode insertLeftChildNodeBT(TreeNode parentNode, TreeNode element) { if (parentNode != null && pare..

1. 이진 트리(Binary Tree)가장 기본적인 자료구조 리스트부모(Parent)노드자식(Child)노드선조(Ancestor)노드후손(Descendant)노드형제(Sibling)노드비선형 자료구조 - 1:1이 아닌 1:N의 관계레벨(Level) : 루트노드로 부터 거리높이(Height) : 단말 노드로부터 최대거리차수(Degree) : 자식노드의 수이진 트리최대 차수가 2인 트리, 다양한 알고리즘에 응용되는 자료구조수행시간이 O(log N)을 지향하는 자료구조완전 이진 트리 : 2의 (레벨h)승 - 1각 레벨 당 노드의 개수 : 2의 (레벨h-1)편향 트리(skewed tree)리스트와 다를바 없다.

1. 재귀 호출 분할 정복 : 문제의 타입은 같고 문제의 범위를 작게 하여 해결하는 방법 알고리즘의 특성 입력 출력 명백성 유한성 유효성 재귀 호출에서는 종료 조건이 명확해야한다. public class Factorial { public long factorial(int n) { long result; if(n == 1) return 1; result = n*factorial(n-1); return result; } public static void main(String[] args) { Factorial f = new Factorial(); Syst..

1. 큐맨 앞(front)에서 자료를 꺼내고, 맨 뒤(rear)에 자료를 추가한다. (중간의 자료를 꺼낼 수 없음)선입선출(FIFO, First In First Out) 구조이다.한 줄로 서기(먼저 추가된 자료가 먼저 꺼내짐)시스템에서 이벤트를 핸들링하기 위해 저장하는 구조Queue에서 사용하는 메서드enqueue() : rear 위치에 자료를 넣음dequeue() : front 위치에서 자료를 꺼냄isEmpty() : 큐가 비어 있는지 확인isFull() : 큐가 꽉 찼는지 확인

1. 스택맨 마지막 위치(top)에서만 자료를 추가, 삭제, 꺼내 올 수 있음 → (중간의 자료를 직접 꺼낼 수 없음)LIFO (Last In First Out, 후입선출) 구조택배 상자를 쌓아놓은 모양과 유사가장 최근의 자료를 찾아오거나, 게임에서 히스토리(undo 등)를 유지하고 되돌릴 때 사용할 수 있음함수의 메모리는 호출 순서에 따라 스택(stack) 구조로 관리됨2. 스택의 메서드push():top 위치에 새로운 자료를 넣는 연산pop():top 위치에서 자료를 꺼내오는 연산peek():top에 있는 자료를 확인하는 연산(자료를 꺼내지는 않음)public interface StackInterface { public void push(E newItem); public E pop(); ..

1. 연결 리스트(Linked List)동일한 데이터 타입을 순서에 따라 관리하는 자료 구조이다.노드(Node)는 실제 데이터를 저장하며, 다음 노드를 가리키는 링크(포인터)를 갖고 있다.자료(노드)가 추가될 때는, 필요한 만큼의 메모리를 할당받고, 이전 노드와 링크로 연결한다.→ (정해진 크기가 없으며, 동적으로 확장 가능)자료를 추가하거나 삭제할 때는, 연결되는 링크만 조정하면 되므로, 해당 연산의 복잡도는 O(1)이다.연결 리스트에서 n번째 요소를 찾기 위해서는, 순차적으로 링크를 따라가야 하므로, 탐색 시간 복잡도는 O(n)이 된다.public class ListNode { private E data; public ListNode next; public ListNode() { ..

1. 배열 리스트동일한 데이터 타입을 순서에 따라 관리하는 자료 구조정해진 크기가 있음(fixed-length)물리적으로 연속된 메모리를 사용하므로 자료의 추가와 제거시 다른 요소들의 이동이 필요함 O(n)물리적으로 연속된 메모리를 사용하므로 배열의 i 번째 자료를 찾는 연산이 빠름 : 인덱스 연산 O(1)2. 배열 리스트에 자료 추가하고 삭제하기중간에 추가 삭제 시 배열의 이동이 필요함public interface ListInterface { public void insertElement(int i, E data); public void addElement(E data); public E removeElement(int i); public E getElement(int i); ..

1. 리스트와 알고리즘리스트에 대하여자료를 순서대로 저장하는 자료구조가장 단순하면서 가장 많이 사용되는 자료구조자료의 앞/뒤 순서가 있고, 물리적이나 논리적으로 연속(sequential) 구조임대부분의 언어에서 제공되는 자료구조리스트를 구현한 자료구조들배열 리스트 (ArrayList)동일한 자료를 한꺼번에 여러 개 만들 때 사용자료의 개수를 저장하고 물리적 순서와 논리적 순서가 동일구현이 비교적 쉬움연결 리스트 (LinkedList)전체 리스트의 크기가 동적으로 변할 수 있음. 필요할 때마다 추가 가능물리적 순서와 논리적 순서가 동일하지 않을 수 있음배열 리스트보다 분할 삽입/삭제가 편함리스트를 구현하는데 필요한 메서드들리스트의 생성 (create)리스트의 끝에 자료 추가하기 (append)리스트의 특정..