코딩 테스트를 위한 자료 구조와 알고리즘 with C++ 이진 탐색 트리(BST) 왼쪽 자식 data return find(p->left, value) else return find(p->right, value) 삽입 의사 코드 insert(p, value): if value data if p->left == null p->left = new Node {value, null, null} else insert(p->left, value) else if p->right == null p->right = new Node {value, null, null} else insert(p->right, value) 삭제 의사 코드 delete(p, value): if p == null return null i..

Level 0. 가까운 수 sort() 함수에 커스텀 비교자를 지정하여 정렬하면 쉽게 해결할 수 있지만 O(nlog n) 시간이 소요된다. #include #include #include using namespace std; int solution(vector array, int n) { sort(array.begin(), array.end(), [n](const int a, const int b) { int distA = abs(n - a); int distB = abs(n - b); return (distA == distB) ? (a < b) : (distA < distB); }); return array[0]; } 코드가 다소 길어지긴 했지만 직접 순회하면 O(n) 시간에 해결 가능하다. #incl..

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ 트리의 주요 용어 루트(Root)가 가장 위에 있는 상하 반전 형태이다. 노드(Node)와 간선(Edge)을 활용해 계층을 구성한다. 부모(Parent) 노드와 자식(Child) 노드를 가질 수 있다. 부모의 다른 자식 노드를 형제(Sibling) 노드라고 한다. 특정 노드를 루트로 하는 부트리(Subtree)가 존재한다. 자식이 없는 가장 끝의 노드들을 단말(Leaf) 노드라고 한다. 단말 노드가 아닌 노드를 내부(Internal) 노드라고 한다. 부모 노드와 그 부모들을 선조(Ancestor)라고 한다. 자식 노드와 그 자식들을 자손(Descendant)라고 한다. 자신을 포함한 모든 자손 노드의 개수를 노드의 크기(Size)라고 한다. 루트에..

Level 0. 합성수 찾기 에라토스테네스의 체를 활용해 해결했다. 2부터 소수인 수는 자신을 제외한 자신의 배수들을 합성수로 표시하는 알고리즘이다. 가장 작은 소수는 2이기 때문에 last(n / 2)까지만 반복문을 수행하면 된다. #include #include #include using namespace std; int solution(int n) { int last = n / 2; vector v(n + 1, true); for (int i = 2; i

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ 같은 시간 복잡도를 갖더라도 내부적인 구현에 따라 실제 실행 시간에는 다소 차이가 있을 수 있다. 그럴 때 아래와 같은 사이트에서 구현한 코드를 실행해 실제 결과를 비교해 볼 수 있다. Quick C++ Benchmarks Quickly benchmark C++ runtimes quick-bench.com

Level 0. 약수 구하기 1과 n은 무조건 포함되므로 생성 시 초기화해준다. n까지 반복할 필요 없이 제곱근보다 작거나 같은 경우까지만 반복하고 제수(Divisor)와 몫(Quotient)을 함께 추가해줘도 된다. vector에 삽입한 후 sort() 함수를 실행하면 O(nlog n) 복잡도를 갖게 된다. 애초에 레드-블랙 트리를 사용하여 정렬된 상태를 유지하는 set에 삽입하는 것 역시 O(nlog n)의 복잡도를 갖는다. 나는 코드 줄을 줄이고 이해하기 쉬운 코드를 짜기 위해 후자를 택했다. #include #include #include #include using namespace std; vector solution(int n) { float square_root = sqrt(n); set s..