Algorithm

Java-알고리즘 ( 공간 복잡도 )

공간 복잡도 알고리즘 계산 복잡도는 다음 두 가지 척도로 표현될 수 있음 시간 복잡도: 얼마나 빠르게 실행되는지 공간 복잡도: 얼마나 많은 저장 공간이 필요한지 좋은 알고리즘은 시행 시간도 짧고, 저장 공간도 적게 쓰는 알고리즘이다. 통상 둘 다를 만족시키기는 어려움 시간과 공간은 반비례적 경향이 있음 최근 대용량 시스템이 보편화되면서, 공간 복잡도보다는 시간 복잡도가 우선 그래서! 알고리즘은 시간 복잡도가 중심 1. 공간 복잡도 ( Space Complexity ) 프로그램을 실행 및 완료하는데 필요한 저장공간의 양을 뜻함 총 필요 저장 공간 고정 공간 ( 알고리즘과 무관한 공간 ): 코드 저장 공간, 단순 변수 및 상수 가변 공간 ( 알고리즘 실행과 관련있는 공간 ): 실행 중 동적으로 필요한 공간..

JAVA-자료구조 (Heap)

1. 힙 (Heap) 이란? 힙: 데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진 트리 (Complete Binary Tree) 완전 이진 트리: 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 - 힙을 사용하는 이유 - 배열에 데이터를 넣고, 최댓값과 최솟값을 찾으려면 O(n)이 걸림 - 이에 반해, 힙에 데이터를 넣고, 최댓값과 최솟값을 찾으면 O(log n)이 걸림 - 우선순위 큐와 같이 최댓값 또는 최솟값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용됨 2. 힙 (Heap) 구조 힙은 최댓값을 구하기 위한 구조 (최대 힙, Max Heap)와, 최솟값을 구하기 위한 구조 (최소 힙, Min Heap) 로 분류할 수 있음 힙은 다음과 같이 두 가지 조건을 ..

Java-자료구조 (Tree)

1. 트리 (Tree) 구조 트리: Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조 실제로 어디에 많이 사용되나? 트리 중 이진 트리 (Binary Tree) 형태의 구조로, 탐색(검색) 알고리즘 구현을 위해 많이 사용됨 2. 알아둘 용어 Node: 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 Branch 정보 포함) Root Node: 트리 맨 위에 노드 Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄 Parent Node: 어떤 노드의 다음 레벨에 연결된 노드 Child Node: 어떤 노드의 상위 레벨에 연결도니 노드 Leaf Node (Terminal Node): Child Node..

Java-자료구조 (Hash Table)

1. 해쉬 테이블 키(Key)에 데이터(Value)를 매핑할 수 있는 구조 해싱 함수를 통해, 배열에 키에 대한 데이터를 저장할 수 있는 주소(인덱스 번호)를 계산 Key를 통해 바로 데이터가 저장되어 있는 주소를 알 수 있으므로, 저장 및 탐색 속도가 획기적으로 빨라짐 미리 해쉬 함수가 생성할 수 있는 주소(인덱스 번호)에 대한 공간을 배열로 할당한 후, 키에 따른 데이터 저장 및 탐색을 지원한다. 2. 알아둘 용어 해쉬 함수(Hash Function): 임의의 데이터를 고정된 길이의 값으로 리턴해주는 함수 해쉬(Hash), 해쉬 값(Hash Value), 또는 해쉬 주소(hash Address): 해싱 함수를 통해 리턴된 고정된 길이의 값 해쉬 테이블(Hash Table): 키 값의 연산에 의해 직접..