코딩 테스트를 위한 자료 구조와 알고리즘 with C++ 빠른 검색의 필요성 선형 검색은 O(n) 복잡도를 갖는다. 균형 트리에서의 검색은 O(log n) 복잡도를 갖는다. 유전자 데이터처럼 수백 수천만의 데이터가 저장된 경우에는 훨씬 효과적인 검색 방법이 필요하다. 해시 함수 주어진 입력을 고정 길이의 고유한 값으로 변환하는 단방향 함수이다. 그러므로 해시 값을 통해 원본 문자열을 복원하는 역함수는 존재하지 않는다. 좋은 해시 함수는 중복 확률이 낮은 함수이다. 해싱 해시 함수로 계산한 값을 통해 자료 저장 주소를 찾아내는 탐색 방법이다. 해시 테이블 해시 함수로 계산한 값을 인덱스로 하여 키(해시)와 값을 저장하는 자료구조이다. 키 값만 가지고는 테이블에 원소가 존재하는지 알 수 없고 값도 함께 확인..

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ 트리의 단점 계층적 구조를 표현할 수 있는 반면 순환적인 종속성을 표현할 수 없다. 그래프 순환 구조를 표현할 수 있다. 도시의 도로망, 항공 네트워크 등 정점(Vertex)과 정점 사이를 연결하는 간선(Edge)으로 구성된다. 각 정점은 연결된 다른 정점들의 정보를 유지해야 한다. 인접 행렬(Adjacency Matrix) 혹은 인접 리스트(Adjacency list)로 관리한다. 인접 행렬과 인접 리스트 인접 행렬은 삽입/삭제 시 O(1) 시간 복잡도를 갖으나 O(n²) 공간 복잡도를 갖는다. 인접 리스트는 삽입 시 O(1), 삭제 시 O(n) 시간 복잡도를 갖으나 간선의 개수만큼의 공간만 필요로 한다. 그래프의 구분 순환 그래프(Cyclic ..

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ 각 노드가 N개의 자식을 가질 수 있는 트리를 N-항 트리라고 한다. N-항 트리는 자식의 참조를 벡터로 저장하여 구현할 수 있다. struct node { int date; vectorchildren; } N-항 트리가 사용된 예 파일 시스템 구조 회사의 조직도

코딩 테스트를 위한 자료 구조와 알고리즘 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..

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

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