아래 내용은 부스트코스 강의를 들으며 정리한 것입니다. 합병 정렬 (Merge sort) 합병 정렬은 요소가 하나만 남을 때가지 리스트를 쪼개고, 다시 합치는 과정에서 대소를 비교하여 정렬하는 방법이다. 비교해야할 요소가 n이 있으면 그 중 반을 비교하면 되기 때문에 합병 정렬의 평균적인 시간 복잡도는 O(n logn)이다. 합병 정렬은 리스트를 쪼개어서 다른 공간에 저장한 뒤에 다시 merge 하므로 out-of-place 정렬이며, 중복된 숫자가 정렬 이전에 놓여있던 순서를 유지한 상태로 정렬되는 안정 정렬이다. 합병 정렬 코드 구현 합병 정렬에서는 배열의 요소를 직접 건드리는 것이 아닌 배열의 index를 다룬다. int[] array, temp;// temp배열: array의 임시 복사본 publ..
아래 내용은 부스트코스 강의를 들으며 정리한 것입니다. 셸 정렬 (Shell sort) 삽입 정렬을 약간 변형한 정렬. 일정한 너비만큼 떨어진 요소를 가져와서 그 둘을 대소비교한 후 바꾸는 방법이다. (일정 너비만큼 모두 바꾸면 1round) 간격의 크기를 점점 줄이며 정렬하다 간격 크기가 1이 되면 삽입 정렬을 한다. 요소의 이동 횟수를 줄이는 데 의의가 있다. 즉, 거의 정렬된 상태로 만들어 삽입 정렬을 하는 경우 시간 복잡도가 크게 줄어드는 것을 활용하는 방식이다. 셸 정렬은 리스트 안에서 순서만 바꾸기 때문에 in-place 정렬이며, 중복된 숫자의 순서가 보장되지 않는 불안정 정렬이다. 셸 정렬의 평균적인 시간 복잡도는 사용하는 간격의 크기에 따라 바뀌는데, O(n^5/4) 혹은 O(n^3/2)..
아래 내용은 부스트코스 강의를 들으며 정리한 것입니다. 삽입 정렬 (Insert sort) 삽입 정렬은 요소를 하나씩 꺼내서 요소 앞에 있는 것들과 비교하며 교체하는 방법이다. 자료구조를 그대로 두고 안에서 순서만 바꾸기 때문에 in-place 정렬이며 중복된 숫자가 정렬 이전에 놓여있던 순서를 유지한 상태로 정렬되는 안정 정렬이다. 선택 정렬의 시간 복잡도는 (n-1) + (n-2) + (n-3) ... 이므로 역시 Worst와 Average 모두 O(n^2)이다. 그러나 이미 순서에 맞게 정렬되어 있는 Best case에서는, 숫자를 꺼내어 앞 숫자와 한 번씩만 비교하면 되기 때문에 O(n)이다. 선택 정렬이 사용되는 경우는 주로 잘 정렬되어 있는 데이터베이스 혹은 딕셔너리에 잘 정렬된 몇 개의 요소..
아래 내용은 부스트코스 강의를 들으며 정리한 것입니다. 정렬 (sort) 컴퓨터 분야에서는 데이터를 정렬해야 하는 경우가 많이 발생하는데, 이를 효과적으로 해결하기 위한 알고리즘과 이 알고리즘을 비교하는 다양한 기준이 있다. (*강의에서는 숫자를 정렬하는 경우만을 다룬다.) out-of-place 정렬 모든 데이터를 자료 구조의 복사본에 옮긴 후(저장공간) 순서대로 배열하여 정렬하는 방법이다. 책을 정리할 때 모든 책을 다 꺼내어 바닥에 두고 다시 순서대로 꽂아 정리하는 방법에 비유할 수 있다. in-place 정렬 out-of-place와 달리 자료 구조를 그대로 둔 채 그 안에서 요소의 위치만 shuffle하여 정렬하는 방법이다. 책꽂이에서 책을 하나 꺼내어 원하는 위치에 다시 꽂는 작업을 순서대로 ..
아래 내용은 부스트코스 강의를 들으며 정리한 것입니다. rotate (회전) 메소드 현재 노드와 부모 노드가 각각 오른쪽 자식인지 왼쪽 자식인지에 따라 필요한 회전이 달라진다. public void rotate(Node node){ // 현재 노드가 왼쪽 자식 if (node.isLeftChild) { // 부모 노드가 왼쪽 자식 if (node.parent.isLeftChild) // 조부모 노드를 우측회전 rightRotate(node.parent.parent); node.black = false; node.parent.black = true; if(node.parent.right != null) node.parent.right.black = false; return; } // 부모 노드가 오른쪽 자..
아래 내용은 부스트코스 강의를 들으며 정리한 것입니다. RB의 규칙 레드 블랙 트리는 자가 균형 이진 탐색 트리로서, AVL 트리처럼 스스로 균형을 잡는 트리이다. Boolean으로 노드를 빨간색 혹은 검은색으로 설정한다. 규칙 1. 모든 노드는 빨간색이나 검은색 2. 루트는 항상 검은색 3. 새로 추가되는 노드는 항상 빨간색 4. 루트에서 잎 노드로 가는 모든 경로에는 같은 수의 검은색 노드가 있어야 함 (빨간 노드 개수는 다를 수 있음) 5. 어떤 경로에서도 빨간색 노드 2개가 연속으로 있어서는 안 됨 (연속된 두 블랙 노드는 가능) 6. 모든 null 노드는 검은색이라고 가정 균형을 맞추는 방법 1) 이모 노드가 검은색일 경우 회전한다. 회전을 하고 나면 부모 노드는 검은색, 두 자식 노드는 빨간색..
아래 내용은 부스트코스 강의를 들으며 정리한 것입니다. checkBalance 메소드 AVL 트리에서는 왼쪽과 오른쪽의 높이 차이가 항상 1보다 작거나 같아야 하므로, 노드를 추가하였을 때 높이의 차이가 1보다 커지면 회전으로 트리의 균형을 맞춰줘야 한다. checkBalance 메소드를 통해 트리의 높이 차이를 확인하고 균형을 맞춘다. 1보다 크지 않으면 계속해서 올라가서 루트까지 확인한다. public void checkBalance(Node node){ // 높이 차이가 1 초과 혹은 -1 미만 (AVL 트리 규칙 위반) if ((height(node.left) - height(node.right)>1) || (height(node.left) - height(node.right) 오른쪽 자식 if ..
