Algorithms

[Tree] 트리

트리 ( Tree ) 트리란? 부모 자식 관계를 가진 자료구조이며 나무의 뿌리? 를 연상캐하는 자료구조입니다. 트리를 구성하는 요소로 노드와 간선으로 표현되어 구성되어있다. 위의 구성 노드를 구성한 코드입니다. public class Node { private int value; private Node left; private Node right; } 데이터 표현은 int로 받기위해 int 타입으로 구성하고 왼쪽 오른쪽 노드를 구성하였습니다. 트리의 특징 및 구성요소 비선형 구조이며 계층구조를 나타낸다. 각 노드는 하나의 부모노드를 가진다. 자식 노드 개수는 0개 이상을 가진다. 노드 개수가 n일 때, 간선의 개수는 n-1개 이다. 이진트리 ( Binary Tree ) 각각의 노드는 최대 2개의 자식 노..

[Sort] 퀵 정렬 (Quick Sort)

소개 Pivot 기준으로 정렬을 진행한다. 앞서 배운 정렬들에 비해 빠른 속도를 가진다. 시간 복잡도는 평균적으로 O(nlogn) 을 가진다. 하지만 최악일 경우엔 O(n2) 을 가진다. 동작원리 배열 안에 기준이 될 원소를 선택 → Pivot Pivot을 기준으로 pivot 보다 작은 원소는 모두 왼쪽으로 옮기고 큰 원소는 모두 오른쪽으로 옮겨 분할 과정을 거친다. pivot 을 제외한 왼쪽 배열과 오른쪽 배열의 리스트를 정렬한다. 분할된 배열을 가지고 위의 순서를 더이상 분할이 안될 때 까지 반복한다. 구현코드 public static void sort(int[] arr, int left, int right) { if (left >= right) { return; } int i = left; int ..

[Sort] 병합 정렬 (Merge Sort)

소개 많은 양의 데이터가 한 개가 될 때까지 반으로 분해하고 또 분해한다. 그리고 다시 그 데이터를 정렬하고 병합하는 알고리즘을 병합정렬이라 한다. 시간복잡도는 O(nlogn)을 가진다. 동작원리 배열을 반으로 계속 나눈다. 왼쪽배열이 오른쪽배열보다 작아질 때 병합을 시켜준다. 병합할 때 정렬을 하면서 병합한다. 구현 코드 public void mergeSort(int[] arr, int left, int right) { if (left < right) { int middle = (left + right) / 2; mergeSort(arr, left, middle); mergeSort(arr, middle + 1, right); merge(arr, left, middle, right); } } priva..

[Sort] 셸 정렬 (Shell Sort)

소개 삽입정렬의 단점을 보완하고자 나온 셸 정렬이다. 간격(gap) 에 맞추어 삽입정렬을 하는 정렬이다. O(n2)의 시간복잡도를 가지지만 삽입정렬보단 효율적이다. 동작원리 배열의 길이 / 2 를 gap 으로 설정 첫번째 인덱스 부터 gap에 맞는 요소들을 삽입 정렬 진행 위의 순서 반복 구현 코드 public static int[] sort(int[] nums) { int length = nums.length; for (int gap = length / 2; gap > 0; gap /= 2) { for (int startIndex = 0; startIndex < gap; startIndex++) { insertionSort(nums, startIndex, gap); } } return nums; } p..

[Sort] 삽입 정렬 ( Insertion Sort)

소개 정렬되지 않은 부분의 자료가 정렬된 부분의 자리로 삽입되는 형태의 정렬 방법이다. 동작원리 첫번째 자리는 정렬이 되었다고 가정한다. 두번째 자리를 target 으로 정하고 왼쪽의 정렬된 원소들과 target의 값을 비교한다. 만약 target 값보다 정렬된 왼쪽 원소들이 크다면 자리를 교환해준다. 다시 오른쪽으로 이동하여 target값을 저장하고 위의 순서대로 반복한다. 구현 코드 for (int i = 1; i = 0 && arr[j] > target; j--) { arr[j + 1] = arr[j]; } arr[j + 1] = target; }

[Sort] 선택 정렬 (Selection Sort)

소개 리스트 안의 자료중 가장 작은수 또는 가장 큰수를 찾아 첫 번째 위치 또는 가장 마지막 위치의 수와 교환해주는 정렬이다. 교환 횟수를 최소화하는 반면 비교하는 횟수는 증가한다. 동작원리 배열의 순서와 상관 없이 선택 정렬되는 배열은 n -1 의 교환이 이루어진다. 버블 정렬 보다 교환 횟수는 적어지지만 비교를 모든 원소를 해야하기 때문에 n2의 비교가 이루어진다. for (int i = 0; i < arr.length; i++) { int minIndex = i; for (int j = i; j < arr.length; j++) { if (arr[minIndex] < arr[j]) { continue; } minIndex = j; } int temp = arr[i]; arr[i] = arr[minI..

[Sort] 버블 정렬 (Bubble Sort)

소개 탐색의 효율적인 방법중 하나가 정렬이다. 정렬한 뒤 탐색을 하면 탐색의 효율성이 높아진다. 정렬 알고리즘 중 하나가 버블 정렬이다. 특징 버블 정렬은 단 두개의 요소만 정렬해주는 좁은 범위의 정렬이다. 하나의 요소를 정렬하기 위해 너무 많이 교환하는 낭비가 발생 될 수 있다. 동작원리 리스트 안에 들어있는 두 개의 인접한 수를 비교 만약 순서에 맞지 않는다면 교환 예시 배열 [5, 1, 6, 2, 4, 3] 이 있다고 가정 5와 1을 비교, 1이 5보다 작기 때문에 교환이 됨 5와 6을 비교, 5가 6보다 작기 때문에 그 다음 요소로 넘어감 6과 2를 비교. 2가 6보다 작기 때문에 교환이 됨 6과 3 비교, 3이 6보다 작기 때문에 교환 위의 단계별로 배열결과를 써보자. [5, 1, 6, 2, 4..

[Sort] 선형 탐색 (Linear Search)

소개 원하는 자료를 찾을때 까지 처음부터 마지막 자료까지 순서대로 탐색한다. 단점 자료를 찾을때 까지 모든 자료를 확인해야하는 부담감이 있다. 즉, 효율적이지 않다. 리스트의 길이를 n이라 가정 찾을 자료가 마지막에 있을 시 처음부터 마지막 자리까지 확인해야한다. 결국엔 n 번 확인해야한다. 정렬 리스트 vs 무작위 리스트 대규모 데이터와 정렬된 리스트를 탐색할 땐 선형 탐색의 효율성이 떨어지지만 정렬되지 않은 무작위 리스트를 탐색할 땐 효율성이 좋다.

[JAVA] 해싱 동작 방식

학습 내용 해시 코드의 동작 방식을 이해합니다. 불변 객체 public class Book { private final String name; public Book(String name) { this.name = name; } public String getName() { return name; } @Override public String toString() { return "Book{" + "name='" + name + '\'' + '}'; } @Override public boolean equals(Object o) { return this.name.toString().equals(o.toString()); } @Override public int hashCode() { int sum = 0; f..

[JAVA] 성능을 개선한 Map 구현 (해싱)

학습 내용 MyMap 을 좀 더 개선하여 구현 해싱 내장된 맵에 따라 키를 나누므로 각 맵의 엔트리 개수는 줄어듭니다. 그러므로 메서드의 속도는 향상됩니다. private List maps; public MyBetterMap(int k) { makeMaps(k); } protected void makeMaps(int k) { maps = new ArrayList(k); for (int i = 0; i < k; i++) { maps.add(new MyMap()); } } k 를 인자로 받아 k 개의 엔트리를 ArrayList 에 저장합니다. 핵심 키를 살펴보고 어느 내장 맵에 투입할지를 결정하는 방법입니다. 새로운 키를 추가하면 맵 중에서 하나를 고르고, 같은 키가 있다면 그키를 어느 맵에 넣었는지 기억해..

[JAVA] Map 구현

학습 내용 Map의 구조를 알수 있습니다. 추가 key, value 추가 조회 key 에 해당하는 value 값 조회 삭제 key 에 해당하는 entry 값 삭제 MyEntry.class private K key; private V value; public MyEntry(K key, V value) { this.key = key; this.value = value; } @Override public K getKey() { return key; } @Override public V getValue() { return value; } @Override public V setValue(V value) { return this.value = value; } } Entry 인터페이스를 구현하였습니다. MyMap ..

[JAVA] Stack 구현

학습 내용 스택의 대표적인 3가지 기능을 구현 할 수 있습니다. 시간 복잡도 분류를 할 수 있습니다. 추가 요소 추가 삭제 요소 삭제 조회 최상단 요소 반환 필드 private E[] array; private int top; private int capacity; public MyStack(int size) { array = (E[]) new Object[size]; capacity = size; top = -1; } 추가 1. 요소 추가 public void push(E element) { if (isFull()) { E[] bigger = (E[]) new Object[array.length * 2]; System.arraycopy(array, 0, bigger, 0, array.length); a..

[JAVA] LinkedList 구현

학습 내용 추가 요소 추가 지정 인덱스에 요소 추가 조회 인덱스의 값 조회 인덱스의 값을 비교 수정 지정 인덱스에 요소 수정 삭제 요소 삭제 초기화 ( size, node clear ) Node.Class public class Node { public E data; public Node next; public Node() { this.data = null; this.next = null; } public Node(E data) { this.data = data; this.next = null; } public Node(E data, Node next) { this.data = data; this.next = next; } } data 는 요소를 뜻하고 next 는 다음 node 를 참조하는 뜻을 가집니..

[JAVA] ArrayList 구현

개인 정리 내용이니 틀린 부분이 있을 수도 있습니다. 피드백 해주시면 감사드리겠습니다. 학습 내용 기능 구현을 하며 시간 복잡도를 구별 해보자. 1. 구현 상세 내용 추가 요소 추가 인덱스 지정하여 요소 추가 수정 인덱스 지정하여 요소 수정 조회 해당 인덱스의 값 조회 해당 인덱스의 값과 target 값을 비교하여 인덱스 값 반환 삭제 인덱스를 설정하여 값 삭제 요소 전체 삭제 필드 int size; private E[] array; public MyArrayList() { size = 0; array = (E[]) new Object[10]; } ArrayList 와 비슷하게 기본 Size 를 10으로 설정 하였습니다. 추가 1. 요소 추가 public boolean add(E e) { if (size..

[JAVA] 선택 정렬 ( Selection Sort )

학습 내용 Big-O 선택 정렬 구현 Big-O O(1) : 입력 데이터의 크기에 상관없이 일정한 연산 시간이 걸리는 알고리즘. O(n) : 입력 데이터의 크기에 비례하여 연산 시간이 걸리는 알고리즘. O(n^2) : 입력 데이터의 크기에 제곱하여 연산 시간이 걸리는 알고리즘. 이외의 여러 종류들이 있습니다. 선택 정렬 구현 1. 자리 바꿈 public static void swapElement(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; // test 성공 } 입력받은 배열의 요소를 자리 바꿈을 하는 로직입니다. 입력 받은 데이터의 크기에 상관없이 일정한 연산 시간을 갖는 로직이여서 O(1) 의 시간 복잡도를..