Algorithm/Algorithm-Java

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): 키 값의 연산에 의해 직접..

Java-자료구조 (시간 복잡도)

알고리즘 성능 표기법 Big O (빅-오) 표기법: O(N) 알고리즘 최악의 실행 시간을 표기 가장 많이/일반적으로 사용함 아무리 최악의 상황이라도, 이정도의 성능은 보장한다는 의미이기 때문 Ω (오메가) 표기법: Ω(N) 오메가 표기법은 알고리즘 최상의 실행 시간을 표기 Θ (세타) 표기법: Θ(N) 세타 표기법은 알고리즘 평균 실행 시간을 표기 시간 복잡도 계산은 반복문이 핵심 요소임을 인지하고, 계산 표기는 최상, 평균, 최악 중, 최악의 시간인 Big-O표기법을 중심으로 익히면 됨 3. 대문자 O 표기법 빅 오 표기법, Big-O 표기법 이라고도 부름 O(입력) 입력 n 에 따라 결정되는 시간 복잡도 함수 O(1), O(log n), O(n), O(nlog n), O(n^2), O(2^n), O..

Java-자료구조 (Linked-List)

1. 링크드 리스트 (Linked List) 구조 연결 리스트라고도 함 배열은 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조 링크드 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조 링크드 리스트 기본 구조와 용어 노드(Node): 데이터 저장 단위(데이터 값, 포인터)로 구성 포인터(pointer): 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간 2. 간단한 링크드 리스트 예 최대한 간단한 형태로 코드를 작성해보며 링크드 리스트를 이해해보기 2-1. Node 클래스 구현 // src/com.company/Node.java package com.company; // Node 클래스 구현 public class Node { private ..