공부기록

이진탐색'정렬된 리스트'에서 특정 값을 빠르게 찾는 알고리즘.리스트를 반으로 나눠서 목표값이 어느 쪽 절반에 속하는지 결정하고, 나머지 절반은 버리면서 목푯값이 포함될 가능성이 있는 절반을 탐색한다.값을 찾을 때까지 이 과정을 반복한다. 어느 쪽에 속해야하는 지 결정해야하기 때문에 기본적으로 정렬된 리스트여야한다.배열 A 에서 i A[i] 문제 정의다음과 같은 오름차순으로 정렬된 배열 A 가 있다.[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]이 배열 A 에서 숫자 10을 찾아보자.문제 해결앞서 말한 것처럼 이진 탐색은 리스트를 반으로 나누어 탐색하기 때문에 탐색공간의 중앙값을 선택하며 시작해야한다. 이를 코드로 나타내면 다음과 같다.var indexHigh = list.size - 1 // 탐..

개요 HashTable 은 Key - Value 로 이루어진 자료구조다. HashTable.get(Object key)를 쓰면 해당 key와 맞는 value를 반환한다. 이름에서 알 수 있듯이 HashCode를 이용한다. Key를 HashFunction를 통해 정수 Hash를 만들어내고, 그 Hash를 이용해 데이터에 접근하기 때문에 속도가 매우 빠르다.( O(1) ) 정수 Hash를 통해 데이터에 접근해서 속도가 빠르다는데.. 그렇다면 동일한 Hash를 반환해서 동일 인덱스에 데이터가 중복될 수 있다. 이를 Hash Colliision(해시 충돌)이라 부른다. 최악의 경우 데이터 검색에 O(n) 이 걸린다. 때문에 Hash를 만들어내는 HashFunction에 쓰이는 Hash Algorithm을 잘 만..

스택 한 쪽 끝에서만 자료를 넣고, 뺄 수 있는 자료구조다. Push로 데이터를 집어넣고, Pop으로 데이터를 빼낸다. 그림 상으로는 스택의 각 인덱스에 있는 데이터를 알 수 있지만, 사실상 제일 위에 있는 데이터만 알 수 있는 자료구조다. 보통 제일 위에 있는 데이터를 top라고 한다. 스택의 구현 일차원 배열 하나로 구현이 가능하다. public class Stack { private T[] data; private int size; @SuppressWarnings("unchecked") public Stack(int capacity) { data = (T[])new Object[capacity]; size = 0; } public Stack() { this(10); } public void push..

합병정렬(merge sort) 분할정복법을 이용한 정렬이다. 분할정복법 ? 분할 : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할 정복 : 각각의 작은 문제를 순환적으로 해결 합병 : 작은 문제의 해를 합하여(merge) 원래문제에 대한 해를 구함. 데이터가 저장된 배열을 절반으로 나눔 각각을 순환적으로 정렬 정렬된 두 개의 배열을 합쳐 전체를 정 {'A','L','G','O','R','O','T','H','M','S'} {'A','L','G','O','R'} , {'O&#..