정글에서 온 개발자

“프로그래밍” 은 테이블을 이용한 방법을 뜻한다. (컴퓨터와 관련이 없다.) 부분 문제의 해를 결합해 문제를 해결한다. 일반적으로 **최적화 문제(optimization problem)**에 적용한다. 최적화 문제 해와 값을 구분하자 문제의 풀이를 “해(Solution)” 라 한다. 그 풀이가 낸 답을 “값(Value)” 라 한다. 최적해는 각 해의 값 중 최적의 값을 내는 해이다. 최적의 값은 하나이지만 그 값을 내는 해는 여러개이다. 최단 거리(값)를 크루스칼, 프림 등 여러 방법(해)으로 풀 수 있다. 즉 최적화 문제는 여러개의 해를 가진다. 분할정복과의 비교 분할 정복은 서로 겹치지 않는(disjoint) 문제를 부분 문제로 분할한다. DP는 부분문제가 서로 중복될 때(부분 문제끼리 부분문제를 공..

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

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