출처 : Programmers(https://programmers.co.kr/learn/courses/30/lessons/42627) 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러는 여러 가지 방법으로 구현할 수 있습니다. 먼저, CPU 프로세스 스케줄링의 여러 가지 방법을 알아보려면 -> https://junboom.tistory.com/13 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 방법(FIFO: First In First Out, A -> B -> C)입니다. 이때, 각 작업의 요청으로부터 종료까지 걸린 시간의 평균은 (3 + 11 + 16) / 3 = 10ms입니다. 하지만 하드디스크 작업이 끝난 후 가장 짧은 작업 먼저 처리할 경우(SJF: Short Jo..

BST(Binary Search Tree)에서 높이를 log n으로 지향해 조금 더 균형 잡힌 트리로 만드는 기법입니다. - BST 조건을 만족하는 트리 구조 - 시간복잡도 O(log n) 1. Red-black Tree의 활용 자바 Collection에서 ArrayList의 내부적인 알고리즘이 RBT로 이루어져 있습니다. Map에서 HashMap의 Separate Chaining(충돌 처리 기법 중 하나, LinkedList로 Hash 충돌을 해결하는 방법)에서 사용됩니다. (Hash 충돌 기법에 대해서 더 알아보기 -> https://junboom.tistory.com/27) 2. Red-black Tree의 조건 - 모든 root 노드와 leaf 노드는 black의 색을 가집니다. - red의 색을..

1. OOP(Object Oriented Programming) : 객체지향 프로그래밍 OOP란? 캡슐화, 다형성, 상속성, 추상화 4가지 특징을 이용해 코드의 재사용을 증가시키고 유지보수 빈도를 감소시키는 장점을 얻기 위해 객체들을 연결시켜 프로그래밍하는 것입니다. 캡슐화(Encapsulation) : 객체의 필드, 메서드를 하나로 묶고 실제 구현 내용을 감추는 것 다형성(Polymorphism) : 같은 이름으로 실행 결과가 다양한 객체를 이용하는 것 ex) 오버로딩(Overloading) : 이름은 같지만 다른 매개변수와 다른 리턴 타입을 갖는 것 오버라이딩(Overriding) : 부모의 함수를 상속받아 메서드를 재정의하는 것 상속성(Inheritance) : 상위 개념의 특징을 하위 개념이 물려..

QuickSort는 주어진 array를 분할 정복하고, pivot을 설정해 pivot과 비교하며 정렬하는 방법입니다. pivot 설정은 개발자에 따라 다르게 설정할 수 있지만, 보통은 중앙값을 pivot으로 설정합니다. 분할 정복을 하기 때문에 최소, 평균 시간복잡도가 O(n*log n)이지만, pivot과 비교되는 값이 항상 조건에 충족되어 pivot을 지속해서 바꿔주어야 하는 경우(최악의 경우) O(n^2)이 됩니다. 기존의 array에서 값을 변경하기 때문에 공간복잡도는 1입니다. 자바와 벡터를 이용해 QuickSort를 구현해 보겠습니다. Java 코드 import java.util.Vector; public class QuickSort { static void quickSort(Vector v,..

합병 정렬은 주어진 array를 지속적으로 쪼개어 최소 array에서 값을 비교해 다시 합치고 정렬하는 방식으로 최소, 최대, 평균 시간 복잡도가 O(n*log n)으로 비교적 가장 빠른 정렬 방법입니다. 쪼개진 array를 정렬하여 저장하기 위한 별도의 copy array가 필요하기 때문에 공간복잡도는 n입니다. 자바와 벡터를 이용해 합병 정렬을 구현해 보겠습니다. Java 코드 package sort; import java.util.Vector; public class MergeSort { static void merge(Vector v, int s, int e, int m) { Vector ret = new Vector(); int i = s; int j = m + 1; while (i