[목차] 1. LinkedList란 무엇인가? 2. LinkedList를 구현하려면 Node가 필요하다 2.1 python Node구현하기 2.2 java Node 구현하기 3. LinkedList를 소스로 구현해보자 3.1 python LinkedList 구현해보기 3.2 java LinkedList 구현해보기 4. BigO표기 1. LinkedList란 무엇인가? 일단 LinkedList란 말 그대로 연결된 리스트라는 뜻이다. 그렇다면 리스트란 무엇인가? 리스트란 데이터를 연속적으로 저장하는 자료구조이다. 나무 위키에서 본 리스트의 정의는 아래와 같다. 추상적 자료형, 자료구조의 하나. 순열(Sequence)이라고도 불리며, 순서를 가지고[1] 일렬로 나열한 원소들의 모임으로 정의한다. 순서가 있다는..

1. 버블 정렬이란? 거품정렬 또는 버블정렬은 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복잡도가 O(n^2)으로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다. 양방향으로 번갈아 수행하면 칵테일 정렬이 된다. 출처 : https://ko.wikipedia.org/wiki/거품_정렬 거품 정렬 - 위키백과, 우리 모두의 백과사전 무작위 배열수의 거품 정렬 예 거품 정렬 또는 버블 정렬( - 整列, 영어: bubble sort, sinking sort)은 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복잡도가 O ( n 2 ) {\displaystyle O(n^{2})} 로 상당 ko.wikipedi..

삽입정렬이란? 삽입정렬(Insert Sort)은 정렬되어 있는 부분집합에 정렬할 새로운 원소의 위치를 찾아 삽입하는 방법이다. 삽입정렬에서 정렬할 자료가 두개가 있다. 먼저 S(Sorted)와 U(United)로 나누어져 있다. 앞부분 원소부터 정렬을 수행하여 정렬된 앞부분의 원소들은 부분집합 S가 되고 아직 정렬되지 않은 나머지 원소들은 부분집합 U가 된다. 정렬되지 않은 부분집합 U의 원소를 하나씩 꺼내서 이미 정렬되어 있는 부분집합 S의 마지막 원소부터 비교하면서 위치를 찾아 삽입하여 부분집합 S의 원소는 하나씩 늘리고 부분집합 U의 원소는 하나씩 줄인다. U의 원소를 모두 삽입하여 공집합이 되면 삽입 정렬이 완성된다. 위의 글처럼 책에서는 삽입정렬의 정의가 기술되어있다. 쉽게 말해서 두개 리스트로..

Kadane 알고리즘 1234567891011121314151617181920212223242526272829import java.io.*;// Java program to print largest contiguous array sumimport java.util.*; class Kadane{ public static void main (String[] args) { int [] a = {-2, -3, 4, -1, -2, 1, 5, -3}; System.out.println("Maximum contiguous sum is " + maxSubArraySum(a)); } static int maxSubArraySum(int a[]) { int size = a.length; int max_so_far = In..

기수 정렬이란? 기수 정렬(radix sort)은 낮은 자리수부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 정렬 알고리즘이다. 자릿수가 고정되어 있으니, 안정성이 있고(이때 데이터들 간의 상대적 순서는 보존되어야 한다.) 시간 복잡도는 {\displaystyle O(dn)}이다.({\displaystyle d}는 가장 큰 데이터의 자리수)기수 정렬은 비교 연산을 하지 않으며, 무엇보다도 전체 시간 복잡도 역시 {\displaystyle O(dn)}이어서, 정수와 같은 자료의 정렬 속도가 매우 빠르다. 하지만, 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요하다. 기수 정렬은 정렬 방법의 특수성 때문에, 부동소수점 실수처럼 특수한 비교 연산이 필요한 데이터에는 적용할 수 없지만, 사용 ..