Keep going

트리 관련 용어 트리를 구성하는 요소는 노드와 가지 각각의 노드는 가지를 통해 다른 노드와 연결되어 있다. 루트 트리의 가장 윗부분에 위치하는 노드를 루트라고 한다. 하나의 트리에는 하나의 루트가 있다. 리프 트리의 가장 아랫부분에 위치하는 노드를 리프라고 한다. (가장 아래에 위치한다 = 더 이상 뻗어나갈 수 없는 마지막에 노드가 위치한다.) 안쪽 노드 리프를 제외한 노드 자식 어떤 노드로부터 가지로 연결된 아래쪽 노드 부모 어떤 노드에서 가지로 연결된 위쪽 노드 형제 같은 부모를 가지는 노드 조상 어떤 노드에서 가지로 연결된 위쪽 노드 모두 자손 어떤 노드에서 가지로 연결된 아래쪽 노드 모두 레벨 루트로부터 얼마나 떨어져 있는지에 대한 값을 레벨이라고 한다. 루트의 레벨은 0, 가지가 하나씩 아래로 ..

보호되어 있는 글입니다.

1. 퀵 정렬 퀵 정렬은 각 그룹에 대해 피벗 설정과 그룹 나눔을 반복하여 모든 그룹이 1명이 되면 정렬을 마친다. 5 (pl) 7 1 4 6 (pivot) 2 3 9 8 (pr) 1. a[pl] >= x 가 성립하는 요소를 찾을 때까지 pl을 오른쪽으로 스캔합니다. 2. a[pr]

정렬이란? 정렬은 이름, 학번, 키 등 핵심 항목의 대소 관계에 따라 데이터 집합을 일정한 순서로 줄지어 늘어서도록 바꾸는 작업을 말한다. 안정된 정렬이란? 같은 값의 키를 가진 요소의 순서가 정렬 전후에도 유지되는 것을 말한다. 내부 정렬 : 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우에 사용하는 알고리즘 외부 정렬 : 정렬할 데이터가 너무 많아서 하나의 배열에 저장할 수 없는 경우에 사용하는 알고리즘 1. 버블 정렬 버블 정렬은 이웃한 두 요소의 대소 관계를 비교하여 교환을 반복한다. static void bubbleSort(int[] a, int n) { for (int i = 0; i i; j--) { if (a[j - 1] > a[j]) { swap(a, j - 1, j); exch..

재귀란? 어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적이라고 합니다. 재귀함수를 이용하는 대표적인 알고리즘 - 팩토리얼 public class Factorial { static int factorial(int n) { if(n>0) return n*factorial(n-1); else return 1; } } cs - 유클리드 호제법 public class EuclidGCD { static int gcd(int x, int y) { if(y==0) return x; else return gcd(y,x%y); } } cs - 하노이의 탑 public class Hanoi { // no개의 원반을 x번 기둥에서 y번 기둥으로 옮김 static void move(int no, ..

큐란? 큐는 스택과 마찬가지로 데이터를 일시적으로 쌓아 두기 위한 자료구조입니다. 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO) 구조로 되어 있습니다. 인큐(enque) : 큐에 데이터를 넣는 작업 디큐(deque) : 데이터를 꺼내는 작업 프런트(front) : 데이터를 꺼내는 쪽 리어(rear) : 데이터를 넣는 쪽 배열로 큐 만들기 인 큐 할때 시간 복잡도 : O(1) 디 큐 할때 시간 복잡도 : O(n) → 첫 요소를 꺼낸 다음에 두번째 이후의 요소를 모두 맨 앞으로 옮긴다. (비효율적) 링 버퍼로 큐 만들기 링 버퍼는 배열의 처음이 끝과 연결되어있다고 보는 자료구조이다. (배열 요소를 앞쪽으로 옮기지 않아도 된다.) - 프런트 : 맨 처음 요소의 인덱스 - 리어 : 맨 끝 요소의..

보호되어 있는 글입니다.

이진 검색 알고리즘은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다. 키를 이진 검색으로 검사하는 과정을 일반적인 방법으로 표현해 보겠습니다. 검색 범위의 맨 앞 인덱스를 pl, 맨 끝 인덱스를 pr, 중앙 인덱스를 pc라고 지정하겠습니다. 검색을 시작할 때 pl은 0, pr은 n-1, pc는 (n-1)/2로 초기화 합니다. 여기서 주목할 점은 이진 검색을 한 단계씩 진행할 때마다 검색 범위가 (거의) 반으로 좁혀 진다는 것 입니다. 오름차순으로 정렬된 데..