본문 바로가기

IT/자료구조 & 알고리즘

 (9)
[자료구조] HashTable Source import java.util.LinkedList; public class HashTable { //링크드리스트를 저장하는 배열 private LinkedList[] data; // 데이터를 key, value로 저장하는 Node class Node { String key; String value; public Node(String key, String value) { this.key = key; this.value = value; } public String getValue() { return value; } public void setValue(String value) { this.value = value; } } //hashtable의 크기를 미리 선언해둔다 public HashTable(int s..
[자료구조] JAVA - Queue 구현 소스 연결리스트를 이용해서 Queue를 구현해보겠습니다. 1. Node.java 데이터를 저장하는 클래스입니다. 데이터를 저장할 T data 멤버변수와 다음 노드를 가리키는 Node next 멤버변수로 구성됩니다. public class Node { private T data; private Node next; public Node(T data) { this.data = data; } public T getData() { return data; } public void setData(T data) { this.data = data; } public Node getNext() { return next; } public void setNext(Node next) { this.next = next; } } 2. Q..
[알고리즘] 퀵 정렬 퀵 정렬이란 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘이다. 컴퓨터로 가장 많이 구현된 정렬 알고리즘 중 하나 이고, 평균적인 상황에서 최고의 성능을 낸다. 퀵 정렬의 특징 분할 정복 알고리즘이다. 최악 시간복잡도 O(n²), 평균 시간복잡도 O(n log n) 퀵정렬은 불안정 정렬에 속하며 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬이다. 퀵 정렬 알고리즘 리스트에서 적절한 피벗(원소) 하나를 고르고, 피벗 앞에는 피벗보다 작은 값들이 오게 하고, 피벗 뒤에는 피벗보다 큰 값들이 오게 한다. 작업이 완료되면 피벗을 기준으로 두 개의 리스트가 생기는데, 각각 리스트에도 이전에 했던 과정을 재귀적으로 반복해준다. 리스트가 더 이상 나누어지지 않는다면, 재귀반환하면서 여러 개의 정렬된 리스트를 ..
[자료구조] 트리와 그래프 1. 트리(Tree) 트리는 정점(Node)와 선분(Branch)을 이용하여 사이클이 이루어지지 않게 구성된 자료구조이다. 트리의 특징 트리는 계층 모델이다. 트리는 비순환 그래프이다. 노드가 N개인 트리는 항상 N-1개의 간선을 가진다. 순회는 Pre-order, In-order, Post-order로 이루어진다. 트리는 이진트리, 이진 탐색 트리, 균형 트리, 이진 힙 등이 있다. 트리의 용어 루트 노드(root node) : 부모가 없는 노드, 트리는 하나의 루트 노드 만을 가진다. 단말 노드(leaf node) : 자식이 없는 노드 내부(internal) 노드 : 단말 노드가 아닌 노드 간선(edge) : 노드를 연결하는 선 형제(sibling) : 같은 부모를 가지는 노드 조상 노드(ancest..
[자료구조] 배열, 연결리스트, 스택, 큐 1. 배열(Array) 배열은 특정 자료형들이 메모리 공간상에 연속적으로 이루어져 있는 자료구조이다. 배열의 특징 메모리상에 연속적으로 저장되는 특성 때문에, 데이터 접근 속도가 빠르다. 인덱스를 통해 접근하기 때문에 어떤 열에 접근하더라도 접근하는 속도가 같다. 배열의 최대크기를 변경 할 수 없다. 삽입/삭제 시 자료의 이동이 생기기 때문에 오버헤드가 발생한다. 2. 연결리스트(LinkedList) 연결리스트는 여러개의 노드들이 연결된 형태의 자료구조이다. 메모리상에 노드들이 흩어져 있으며, 각각의 노드는 다음 노드에 대한 위치 정보를 저장하고 있다. 연결리스트의 특징 노드는 자료와 링크로 구성된다. 배열 보다 삽입, 삭제 연산이 빠르다. head와 tail이 존재한다. head는 가장 첫번째 노드를 ..
[Java] 쉘 정렬 (Shell Sort) 쉘 정렬이란 배열을 특정 간격(gap)으로 묶어서 gap의 자리수 특정 자리수끼리 삽입 정렬 로직을 수행하는 정렬이다. [9, 4, 1, 7, 3, 2, 1, 5, 0, 6, 8] gap : 4 [0, 2, 1, 5, 3, 4, 1, 7, 9, 6, 8] gap : 2 [0, 2, 1, 4, 1, 5, 3, 6, 8, 7, 9] gap : 1 [0, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 import java.util.Arrays; public class ShellSort { public ..
[Java] 버블 정렬 (Bubble Sort) 버블 정렬이란 n번째 값과 n+1 번째 값을 비교하여 Swap한다. 마지막 인덱스부터 정렬된 값이 저장된다. [5, 4, 3, 2, 1] [4, 3, 2, 1, 5] (1회) [3, 2, 1, 4, 5] (2회) [2, 1, 3, 4, 5] (3회) [1, 2, 3, 4, 5] (4회) 정렬 속도 순 : 삽입정렬 > 선택정렬 > 버블정렬 속도 : O(n^2) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 import java.util.Arrays; public class BubbleSort { public static void main(String[] args) { int[] arr = {5, 4, 3, 2, 1}; int len = ar..
[Java] 삽입 정렬 (Insertion Sort) [9, 4, 1, 7, 3, 2, 1] [4, 9, 1, 7, 3, 2, 1] (1회) [1, 4, 9, 7, 3, 2, 1] (2회) [1, 4, 7, 9, 3, 2, 1] (3회) [1, 3, 4, 7, 9, 2, 1] (4회) [1, 2, 3, 4, 7, 9, 1] (5회) [1, 1, 2, 3, 4, 7, 9] (6회) 속도 : O(n^2) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 import java.util.Arrays; public class InsertionSort { public static void main(String[] args) { int[] arr = {9, 4, 1, 7, 3, 2, 1}; int le..

티스토리툴바