전체글149 AVL 트리 AVL 트리 AVL 트리 개념 이진 탐색 트리(BST)의 한 종류 이진 트리는 모든 노드가 가지는 자식 노드를 최대 2개 가지는 형태다. 이진 탐색 트리는 이진 트리의 모든 노드가 왼쪽 서브 트리는 자기보다 작은 값이, 오른쪽 서브 트리에는 큰 값이 배치되는 특징이 있다. 스스로 균형(balancing)을 잡는 트리 balance factor를 통해 균형 유지 balance factor balance factor는 위와 같은 이진 탐색 트리가 있을 때 임의의 노드 x에 대해서 (왼쪽 서브트리의 높이 - 오른쪽 서브트리의 높이)의 값을 말한다. AVL 트리 특징 AVL 특징은 간단한다. (왼쪽 서브트리의 높이 - 오른쪽 서브트리의 높이)의 값은 balance factor라고 했다. AVL 트리의 특징을 가.. 2024. 2. 4. 덱(Deque) Deque 자바에서 Deque는 java.util.Deque를 import하여 사용할 수 있으며, 자바의 Collection 인터페이스를 상속받은 인터페이스이다. 즉, 자바 컬렉션 프레임워크 중 하나이다. 자바에서 Deque를 사용할 때는 인터페이스이기 때문에 아래 코드와 같이 구현체로 ArrayDeque, LinkedBlockingDeque, ConcurrentLinkedDeque, LinkedList 등의 클래스를 생성해서 사용한다. Deque D = new ArrayDeque(); Deque D = new LinkedBlockingDeque(); Deque D = new ConcurrentLinkedDeque(); Deque D = new LinkedList(); Deque 개념 Deque(덱 혹은.. 2024. 2. 3. 버블 정렬 Bubble Sort (버블 정렬) 버블 정렬은 정렬 알고리즘 중 하나로, 거품 정렬이라고도 한다. 또한 구현해보면 알겠지만 버블 정렬은 코드가 정말 단순하다. 그래서 자주 사용된다. 버블 정렬 개념 O(n^2)의 상당히 느린 시간복잡도를 갖느다. 코드가 단순하기 때문에 자주 사용되며, 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다. 이를 양방향으로 번갈아 수행하면 칵테일 정렬이 된다. 버블 정렬 알고리즘 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘 인접한 두 원소가 정렬이 안되어 있으면 두 원소를 swap하고, 정렬이 되어있으면 그대로둔다. 서로 인접한 두 원소를 배열의 마지막 원소까지 비교해나가다 보면 결국에 마지막 원소가 자리를 잡게 된다. 이렇게 한 사이클.. 2023. 3. 18. 병합 정렬(Merge Sort) 병합 정렬 병합 정렬 즉, Merge Sort는 퀵 정렬과 마찬가지로 분할 정복 알고리즘 중 하나이다. 병합 정렬은 평균 시간복잡도 O(N log N)으로 퀵 정렬과 동일하다. 병합 정렬은 가운데를 기준으로 파티션을 나누므로 최악의 경우에도 O(N log N)의 시간복잡도를 갖는다. 하지만 병합 정렬은 실행시에 별도의 저장 공간이 필요로하기 떄문에 별도의 공간을 사용할 수 없는 경우라면 퀵 정렬을 사용하는 것이 바람직하다. 병합 정렬 개념 합병 정렬이라고도 하며, 비교 기반 정렬 알고리즘이다. 일반적인 방법으로 구현했을 때 병합 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘 중에 하나이다. 존 폰 노이만이 개발했다. 병합 정렬 과정 배열의 길이는 최소 1보다는 커야 한다. 분할(Divide) : 정렬되.. 2023. 3. 17. 퀵 정렬, 퀵하게 알아보자. 퀵 정렬 퀵 정렬은 이름 그대로 매우 빠른 수행 속도를 가지며, 분할 정복(Divide and Conquer) 알고리즘을 사용한다. 분할 정복 알고리즘은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법을 말한다. 퀵 정렬 개념 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다. 평균적으로 O(N log N)의 시간복잡도를 가지며, 최악의 경우에는 O(N^2)의 시간복잡도를 갖는다. 매 단계마다 적어도 1개의 원소가 자기 자리를 찾게 되므로 이후에 정렬할 개수가 줄어들기 때문에 퀵 정렬(빠른 정렬)이라는 이름을 갖게 되었다. 분할 정복 알고리즘을 사용한다. 퀵 정렬 과정 현재 배열은 정렬이 되어있지 않기 때문에 임의의 숫자.. 2023. 3. 16. String vs StringBuilder vs StringBuffer String, StringBuilder, StringBuffer의 차이 Java에서 흔히 문자열을 선언할 때는 아래와 같이 String 타입을 사용한다. String str = "Hi!"; str = str + " MinSu?"; //연산 작업 또한 처음에는 Hi!만 할당했지만 추가적으로 뒤에 문자열을 추가하려면 + " MinSu?" 처럼 연산 작업을 수행해야 한다. 이게 많지 않을 때는 크게 이슈가 없어서 상관이 없지만 연산 작업이 많아지면 String 클래스는 치명적인 단점을 가지고 있다. 이 단점을 보완한 것이 바로 StringBuilder와 StringBuffer이다. String 먼저 String과 (StringBuilder, StringBuffer)의 가장 큰 차이점은 String은 불변성 특.. 2023. 3. 15. 이전 1 ··· 4 5 6 7 8 9 10 ··· 25 다음
