정글에서 온 개발자

알고리즘을 풀다 보면 알고리즘의 유형을 정리하고 싶을 때가 많다. 이 문제를 어떤 알고리즘으로 풀면 좋을지, 내가 쓰고 싶은 알고리즘(동적 프로그래밍, 그리디)로 풀 수는 있는지, 아니면 아예 풀 수 없는 문제인지 그런 문제 분류를 좀 더 큰 그림에서 연구하는 학문을 계산 복잡도 이론이라 한다. 계산 복잡도 이론 각 문제를 해결하는 얼마나 빠른 알고리즘이 존재하는지를 기준으로 문제를 분류하고, 각 분류의 특성을 연구하는 학문이다. 여기서 말하는 복잡도는 시간 복잡도랑은 조금 다르다. 시간 복잡도는 알고리즘의 특성이다. 계산 복잡도는 해당 문제 특성이다.(문제를 풀 수 있는 빠른 알고리즘의 시간복잡도) 어려운 문제, 쉬운 문제 다항시간에 풀 수 있는 문제는 “쉽다”고 하고, 다항시간 알고리즘은 “빠르다” ..

이진 탐색 트리(BST; Binary Search Tree) 이진 트리 : 각 노드가 왼쪽, 오른쪽. 최대 두개의 자식 노드만 가질 수 있는 트리 왼쪽 가지를 따라 내려가면 더 작은 수 오른쪽 가지를 따라 내려가면 더 큰 수를 만남 이진 검색트리를 중위 순회하면 크기 순서로 정렬된 원소를 얻을 수 있다. 정렬된 배열의 특징 루트부터 왼쪽으로 쭉 내려가면 최소 값이 나온다. 루트부터 오른쪽으로 쭉 내려가면 최대값이 나온다. 루트가 배열의 중앙값은 아니다(트리가 불균형하게 생길수도 있다.) 이걸 원하면 다른 트리 써야 함 부모 노드가 항상 나보다 한 등수 높은 것도 아니다. (오른쪽 리프를 생각해보자) 정렬된 배열보다 뛰어난 점 특정 원소가 존재 하는지 빠르게 확인할 수 있다 노드의 값을 기준으로 다음 검색..

계층 관계를 갖는 객체를 표현하기 위해 만들어진 자료구조 계층 관계가 없는 자료를 트리로 표현해서 같은 연산을 빠르게 할 수 있는 경우가 많다. 용어. 개념 정리 노드(node)와 간선(edge)로 이루어져 있다. 노드 간에는 상/하위 관계가 있다. 두 노드가 연결되었을 때는 한쪽이 상위, 다른쪽이 하위여야 한다. 상위는 부모(parent), 하위는 자식(child), 부모가 같은 노드는 형제(sibling) 부모와 부모들은 선조(ancestor), 자식과 그 자식들은 자손(descendant) 자식은 여러개 가질 수 있어도 부모는 하나만 가질 수 있다. 가장 윗쪽 노드는 **루트(**root;뿌리) 자식이 하나도 없는 노트는 리프(leaf;잎) 깊이(depth) :루트에서 어떤 노드에 도달하기 위해 거..