Algorithm 썸네일형 리스트형 [트리] Binary Search Tree 개념 트리(Tree)는 노드(Node)와 간선(Edge)의 집합으로 이루어진다. 간선은 노드들의 부모-자식 관계를 정의하며 트리의 첫 번째 노드를 루트(Root) 노드, 자식 노드가 없는 노드를 단말(Leaf) 노드라고 한다.다음은 트리를 기술하는데 사용하는 기본적인 용어들이다.레벨(Level) : 루트 노드로부터의 거리(루트노드의 레벨은 1)높이(Height) : 노드가 가질 수 있는 최대 레벨 = 깊이(Depth)차수(Degree) : 한 노드가 가지는 자식 노드의 개수서브트리(Subtree) : 트리에 속한 노드들의 부분집합포레스트(Forest) : 트리의 집합이진트리 : 자식 노드의 개수가 최대 2개인 트리이진탐색트리(Binary Search Tree)이진 탐색 트리는 기존의 이진 트리에서 몇 가.. 더보기 [수학응용] 유클리드 호제법(Euclidean algorithm) 유클리드 호제법최대공약수(Greatest Common Divisor)를 구하는 유클리드 호제법(Euclidean algorithm) 다음 두 명제를 기반으로 한다.첫째, 어떤 두 수가 배수 관계에 있을 때, 두 수 중에서 작은 수는 최대공약수가 된다.둘째, 어떤 두 수의 최대 공약수는 큰 수(피제수 : 나누어지는 수)를 작은 수(제수 : 나누는 수)로 나누었을 때, 그 나머지와 작은 수의 최대공약수와 같다.예를 들어 A, B라는 두 정수의 최대공약수를 구하는 과정은 다음과 같다.A와 B는 Q(몫), R(나머지)와 함께 아래와 같이 나타낼 수 있다.A = Q1*B + R1여기서 A와 B의 최대공약수는 나머지 R1과 B(제수)의 최대공약수와 같다. 따라서 다시 아래와 같은 식을 만들 수 있다.B = Q2*R.. 더보기 [정렬] 선택 vs 버블 vs 삽입 정렬의 종류 - 교환(Exchange) : 버블(Bubble), 퀵(Quick) 정렬 - 삽입(Insertion) : 삽입(Intsertion), 셀(Shell) 정렬 - 병합(Merging) : 2-way 병합, n-way 병합 - 분배(Distribution) : 기수(Radix) 정렬 - 선택(Selection) : 선택(Selection), 힙(Heap) 정렬 선택정렬(Selection Sort) 전체 자료 중에서 해당 위치에 맞는 자료를 선택하여 위치를 교환(Exchange)하는 정렬 방식이다. - STEP.1 - STEP.2 - STEP.3 - STEP.4 특성 : 평균 시간복잡도 O(n^2)으로 느린 알고리즘이다. 하지만 최악의 경우도 O(n^2)으로 평균(최선)과 동일하다.정렬의 안정성을 .. 더보기 알고리즘 문제풀이 주의사항 int, long(int)의 범위를 벗어나는 정수를 사용할 때 32비트를 벗어나는 범위의 값을 계산해야 할 때 64비트가 보장되는 long long(int)를 사용한다. 상수를 사용하여 대입시에는 suffix를 붙여주어야 한다.(LL, ll) // 틀린 예 int a = 1000000 * 1024; int b = 1 더보기 이전 1 다음
