이진 트리에서는 하나의 Node 가 1개의 key(data) 와 2개의 자식 node 를 가리키는 link(left,right) 를 가지고있습니다. BST(이진 탐색 트리)는 검색, 삽입, 삭제은 평균 O(log n) 의 시간 복잡도를 가집니다. 하지만 최악의 경우 편향이진트리(구글 이미지 검색) 생성되면 최악의 효율O(n)이 발생합니다. 이를 보완하고 좌우 균형을 맞추어 탐색 효율을 목적으로 B tree라는 것을 사용합니다. 아래의 java 소스코드는 해외 블로그를 참고하였습니다. 탐색,삽입 하는 코드는 비교적 간결하고, 트리의 node 를 삭제하는 logic 은 3가지로 분류 됩니다. 삭제 node 의 자식이 없는 경우 - node 를 바로 삭제 합니다. 삭제 node 의 자식이 1개 인 경우 - 자..
유클리드 호제법 2개의 수의 최소 공약수를 계산할 때 큰 수(a)를 작은 수(b)로 나누고, 나머지(r)가 0이 아니면 나누었던 수(b)를 나머지(r)로 다시 나누고 나머지가 0이 될때까지 반복합니다. 반복 하다가 나머지가 0이 될때 나눈 수가 최소 공약수가 됩니다. 예를 들어 78696과 19332의 최대공약수를 구하면, 78696 = 19332×4 + 1368 19332 = 1368×14 + 180 1368 = 180×7 + 108 180 = 108×1 + 72 108 = 72×1 + 36 72 = 36×2 36이 최소 공배수입니다. 최대 공약수(gcd, greatest common divisor) 최대 공약수를 계산하는 여러가지 방법이 있겠지만 유클리드 호제법 을 사용하여 계산하는 것이 코드도 간결..
선형 자료구조(list)는 배열로 구현하는 방법과 여러 객체(Node) 생성하고, 포인터로 연결하여 구현하는 방법이 있습니다. 신속한 삽입과 삭제를 허용하는 순서 리스트를 유지해야 할 경우에는 후자의 방법으로 리스트를 구현하고, 이것을 연결리스트라 합니다. Node class(list의 각 항목) class Node { public int data; public Node next; Node (int data){ // 생성자 this.data = data; } Node (int data,Node next){ // 2번째 생성자 this.data = data; this.next = next; } } Node 클래스는 자기 참조(self) 형태입니다. 하나의 node 는 data 와 Node 객체를 참조하는 ..
Tree(트리) 트리는 어떤 속성을 만족하는 node(노드)와 방향 간선의 집합입니다. 또한, 하나의 노드가 root 노드를 가리키는 사이클 없는 그래프로 정의할 수 있습니다. 위키피디아 Tree Terminology(전문 용어) Root : 부모가 없는 노드(트리의 가장 상위 노드) Leaf : 차수가 0인 노드 Root-to-leaf path(루트 경로) : 루트로부터 해당 노드까지의 유일한 경로 Size of tree (트리의 크기) : 연결된 모든 node의 개수 Subtree(서브 트리) : 자식 node 가 있을 때 이 노드를 root로 하는 tree (level 이 1 줄어듭니다.) Height of tree : 최장 루트 경로의 길이 단독트리 : 노드가 1개이고 높이는 0인 트리 (NIL)..
Heap(히프) Heap 은 root 가 최대값인 max-heap, 최소값인 min-heap이 있는데 다른 언급이 없으면 max-heap 을 의미합니다. heap은 아래에서 위로 순서를 가지고 있는 이진 트리이므로 모든 leaf-root path 를 따라 가는 순회는 오름차순으로 key 를 방문합니다. 이것은 어떠한 key도 부모보다 크지 않다고 말하는 것과 같습니다. 히프화 알고리즘은 2 * log n 번 이상의 비교를 하지 않습니다. 히프화 알고리즘은 특정 노드를 root로 하는 서브트리에 대해 heap 특성이 만족됩니다. 가장 하위 내부 노드 부터 시작하여 root 에 이르기까지 각각의 x 에 대한 이 연산을 반복함에 의해 전체 트리를 히프화할 수 있습니다. 이러한 과정을 히프 구축(Heap Bui..
비트마스크란 정수의 이진수 표현을 자료구조로 사용하는 기법입니다. 부호없는 N비트 정수형 변수는 N자리의 이진수로 사용할 수 있습니다. 이때 각 비트가 표현하는 값은 2^0 부터 2^k-1 까지입니다. 2^k-1 에 해당하는 비트를 최상위 비트(most significant bit)라고 부르고, 2^0를 나타내는 비트를 최하위 비트(least significant bit) 라고합니다. 어떤 정수를 이진수로 표현했을 때 어떤 비트의 위치가 1이라면 해당비트가 "켜져있다"라고 말하고, 0이라면 꺼져있다고 말합니다. 비트 관련 연산 정의 비트별 AND 연산(&) 두 정수에 해당 비트가 모두 켜져있을때만 결과의 비트를 켭니다. (같의 위치에 있는 두 비트가 전부 1인 경우 결과가 1이고 그 이외에는 0입니다.)..
여러 가지 데이터 타입 및 자료구조가 있지만, 알고리즘에 집중하기 위해 정수(int) 배열을 오름차순으로 정렬하는 형식으로 진행하겠습니다. 각각의 정렬 알고리즘은 특정 환경에 에서 최적의 성능을 발휘합니다. 메모리 공간을 적게 쓴다든지, 배열의 길이가 얼마 이하이면 제일 빠르다든지, 이미 정렬된 경우 제일 빠르다든지.... 참고로 알고리즘의 성능은 비교 횟수와 교환횟수, 추가로 사용하는 저장 공간, 초기 정렬 상태 등 에 따라 결정됩니다. swap 함수 Bubble Sort(버블 정렬) 가장 단순한 정렬 알고리즘입니다. 비교하는 과정이 탄산음료를 담은 컵에 두개의 거품(크기가 서로 다른)이 수면 위로 상승하는 과정과 비슷합니다. 두 거품이 상승중에 충돌 하였을 때 큰 거품이 작은 거품보다 먼저 상승하게 ..
알고리즘 문제 해결 전략 책에서 앞부분 개인적으로 요약 정리해 보았습니다. 접근 방법 무식하게 풀 수 있는지 확인합니다. (문제를 일단 푸는게 우선이고, 나중에 회고를 통해서 더 좋은 알고리즘을 찾습니다.) 문제를 수식화가 가능한지 확인합니다. 문제를 부분 문제로 여러개 나누어 계산이 가능한지 확인합니다. (예 : 팩토리얼) 문제에서 주어진 순서에서 반대로 풀수 있는지 계산이 가능한 문제인지 확인합니다. (예 : 사다리타기) 실수 줄이기 1. 일관된 표현방식 사용 반 열린 구간 을 사용하여 실수를 예방습니다. (열린구간, 닫힌구간 등은 사용을 자제합니다.) low