Map Map key - value 쌍으로 관리하는 메서드를 구현함 검색을 위한 자료구조 key값을 이용하여 값을 지정하고, 값을 꺼내오는 방식 - hash 알고리즘으로 구현됨 객체의 유일성 비교를 위해 equals() , hashCode() 메서드를 구현해야 함. CollectionFramework의 HashMap, Hashtable의 사용법이 궁금하신 분은 목차의 "HashMap 선언" 부터 보시면 됩니다! HashMap, Hashtable의 구조 키(Key) : 해시 테이블 접근을 위한 입력 값 해시 함수(Hash Function) : 키를 해시값으로 매핑하는 연산을 수행 해시 값(Hash Value) : 해시 테이블의 인덱스 HashMap, Hashtable : key - value..
Deque Queue와 Stack의 성질을 둘다 가지고 있다. Stack : push / pop / peek - 제일 늦게 들어간 것이 제일 먼저 나온다. Queue : offer / poll / peek - 제일 먼저 들어간 것이 제일 먼저 나온다. Deque : offerFirst, offerLast 등 : 양방향 Deque의 특징 Deque는 흔히 Stack과 Queue의 특징을 둘 다 갖고 있다고 한다. Queue는 선입선출의 구조를 가지고있다. Deque에서 offerLast로 값을 넣고, pollFirst로 값을 꺼내면 뒤(왼쪽)로 값을 넣고, 앞(오른쪽)에서 꺼내는 Queue와 같다. 또한, offerFirst로 값을 넣고, pollLast로 값을 꺼내면 위와 반대로 앞으로 값을 넣고, 뒤에..
Interface Queue 공식 문서 https://docs.oracle.com/javase/8/docs/api/java/util/Queue.html Queue 선형 자료구조 First In First Out : 가장 먼저 입력된 자료를 가장 먼저 꺼낼 수 있음 맨 앞(front)에서 자료를 꺼내고, 맨 뒤(rear)에 자료를 추가함 몰랐던 영어지만, queue는 "차례를 기다리는 사람이나 승용자의 열"이라는 뜻이다. "대기줄"이라고 생각해도 될 것 같다. 먼저온 순서대로 들어가고, 먼저 온 순서대로 나간다. 변수 선언 Queue queue = new LinkedList(); 아래와 같이 new Queue로 직접 생성할 수도 있지만, Queue는 인터페이스 이기 때문에 해당 인터페이스의 메서드들을 모두..
Stack 선형 자료구조 Last In First Out : 가장 나중에 입력된 자료를 가장 먼저 꺼낼 수 있음 맨 마지막 위치(top)에서만 자료를 추가, 삭제, 꺼내올 수 있음 책을 책상 위에 쌓으면 위에서 만 꺼낼 수 있다. stack을 그대로 번역하면 "쌓다." 이기 때문에 말 그대로 아래서부터 데이터를 쌓고, 최근에 쌓은 데이터 즉, 맨 위의 데이터만 꺼낼 수 있다. 스택 생성 Stack stack = new Stack(); 데이터 처리 push(Object obj) : 데이터 추가 데이터를 맨 뒤에 추가한다. //값 추가 stack.push(1);//[1] stack.push(2);//[1,2] stack.push(3);//[1,2,3] pop() : 데이터 조회, 삭제 (꺼내기) 맨 뒤의 데..
BinarySearch : 이진탐색 (이분탐색) 이진탐색은 데이터가 정렬되어 있는 상태에서 원하는 값을 찾아내는 알고리즘이다. 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는 방식이다. 크기가 100인 배열이 있고, 우리가 찾고자 하는 값이 99번째 인덱스에 들어있는 상황을 가정해 보자. 일반적인 반복문을 사용하여 1부터 100까지 반복하면 99번째 반복에서 찾고자 하는 값을 찾을 수 있다. 물론 이 경우 찾고자 하는 데이터가 앞쪽에 있다면 같은 데이터셋에 대하여 탐색 시간이 이분탐색을 이용했을 때보다 빠를 것이다. 그런데 만약 데이터의 크기가 1억 개이고, 운이 나쁘게도 우리가 찾고자 하는 값이 99,999,999 번째의 데이터인 경우에는 시간이 매우 오래 걸릴 ..
제곱근 제곱근을 구하려면 자바에서 손쉽게 Math.sqrt() 메서드를 이용해서 구할 수 있다. 이 메서드를 이용하지 않고 제곱근을 구하는 방법을 알아보자. 바빌로니아 법(The Babylonian Method) 유도 과정 쓸땐 몰랐는데 사진을 업로드하고 보니 글씨가 개판이다... N은 7일때, N의 제곱근을 구해보자. N의 제곱근은 아마 2와 3 사이에 있을 것이다. (3에 가까울 것 같다.) 따라서 N의 제곱근을 임의의 수 Xn과 아주 작은 수 ε 의 합으로 나타낸다. 위의 식을 ε에 대해 정리 한 뒤, 다시 3번의 식에 대입한다. 4번의 식을 정리하면 위의 위키백과 캡쳐본의 공식이 나온다. 맨 처음에 Xn=2라고 놓고 시작해서 3번만 반복했는데도 실제 값과 매우 유사하게 나왔다. 임의의 값 Xn이 ..
초등학교? 중학교? 때 배운 수학 약수는 어떤 수를 나누었을 때 나누어 떨어지는 수들의 집합이다. 예를들어 12의 약수는 [1, 2, 3, 4, 6, 12]이다. 최대공약수는 두 수가 공통으로 갖는 약수 중 가장 큰 수이다. 예를들어 36과 48의 최대공약수는 12이다. 최소공배수는 두 수의 배수들 중 가장 작은 수이다. 예를들어 24과 36의 최소공배수는 72이다. 약수 약수 : Divisor 어떤 수 A의 약수 집합은 1과 A를 포함한다. 또한, 약수 중 A를 제외한 가장 큰 수는 A/2 보다 클 수 없다. 따라서 for문의 반복 범위는 1부터 A/2 까지로 한다. //약수 static List getDivisor(int num){ List result = new ArrayList(); for(int..
삽입 정렬 (insertion sort) 삽입정렬은 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식이다. 평균 시간복잡도는 O(n^2)으로 느리지만, 구현하기 쉽다. 핵심 이론 정렬 대상(선택 값)을 현재 정렬된 데이터 범위 내에서 삽입할 위치를 찾는 것이 삽입 정렬의 핵심이다. 예제 첫 번째 데이터는 이미 정렬된 데이터이므로 넘어가고 두 번째 데이터부터 시작한다. (사이클 1) 두 번째 데이터 32를 선택하고, 정렬된 데이터 범위(0-1번 인덱스) 내에서 삽입할 위치를 찾는다. (0번 인덱스) 정렬된 위치 중 삽입할 자리를 만들기 위해 정렬범위 중 삽입할 자리의 오른쪽 데이터들을 옆으로 한 칸씩 이동시킨다. 따로 저장해 둔 선택 데이터를 삽입위치에 삽입한다. (사..
