탐색 전에 반드시 정렬되어 있어야하고, 범위를 절반씩 줄여가면서 답을 찾아야한다. 시간복잡도 따라서 정렬 O(NlogN) + 이진탐색 O(logN) -> 결과적으로 O(NlogN). 즉, 경우에 따라서 선형탐색 O(N) 이 더 좋은 선택이 될 수도 있다. 하지만 여러번 탐색을 해야하는 경우라면, 그 탐색의 횟수가 N번이라면, 선형 탐색의 경우에는 N * O(N) = O(N^2) 이 된다. 그러나 이진 탐색을 하면, 정렬 O(NlogN) + N * O(logN) = O(NlogN)이 된다. 결론 결과적으로 탐색을 한번만 하는 경우에는 굳이 정렬을 해가면서 이진탐색을 사용할 이유가 없다. 하지만 탐색을 여러번 해야하는 경우에는 정렬 한번 해두고, 이진탐색을 해주는게 더 빠를 수 있다. C++ lower/up..
기본적으로 모든 경우를 탐색하며, DFS/BFS와 방식은 유사하다. 하지만 백트래킹은 가지치기를 통해 탐색 경우의 수를 줄인다는 차이가 있다. 정리하면, 백트래킹은 최악의 경우에는 모든 경우를 다 살펴보게 될 수도 있지만, 가지치기를 통해서 가능한 덜 보겠다는 전략이다. 가지치기의 원리는 가망성이 없으면 가지 않겠다는 원리를 바탕으로 한다. 어려운 문제일수록 극한의 가지치기를 요구할 수 있음
시간복잡도 인접행렬: O(V^2) 인접리스트: O(V + E) == O(max(V,E)) 정점의 개수와 간선의 개수 중 더 큰 값을 기준으로 인접리스트는 간선의 개수가 적을수록 메모리 공간을 덜 잡아먹는 장점이 있었음 만약 간선의 개수가 V에 비해 월등히 적으면 O(V)로 표현이 될 수 있음 즉, 간선 개수가 적으면 인접리스트가 훨씬 유리해진다.
순환성이 없는 무방향 그래프이다. 특징 특정하지 않는한 어떤 노드든지 root가 될 수 있다. 가장 바깥쪽 노드는 leaf node이다. node A에서 node B로 가는 경로는 반드시 존재하며 유일하다. (단 1개) 노드개수 = 간선개수 + 1 자료구조에서의 트리 부모 -> 자식 관계가 있는 방향 그래프이며, root는 하나다.
구성요소 Vertext(node) edge 그래프 종류 방향성 무방향 그래프(양방향 그래프) 방향 그래프 순환성 순환 그래프(Cyclic Graph) 비순환 그래프(Acyclic Graph) 방향성 비순환 그래프(DAG. Directed Acyclic Graph) VCS (Version Control System) 버전 관리 시스템으로 대표적으로 git과 github가 있다. 또한 이는 대표적인 방향성 비순환 그래프이다. 연결 요소(Connected Component) 아래 그림은 연결요소가 3개인 그래프이다. 코드로 그래프를 나타내는 방법 인접행렬 인접리스트 인접행렬 vs 인접리스트 둘 중에 뭘 써야할까? 여기에서 시간과 공간 사이의 trade off를 알 수 있다. 메모리 공간 인접행렬 노드가 n개이..
🗒️ 요구사항 명세서 메뉴를 생성/조회/수정/삭제할 수 있어야 한다. 메뉴는 하나 이상의 메뉴그룹과 매핑될 수 있다. 메뉴마다 가격과 칼로리가 존재한다. 메뉴마다 재료를 추가하거나 변경할 수 있다. 메뉴는 판매가능한 시간(모닝, 런치)이 존재한다. 세트메뉴를 생성/조회/수정/삭제할 수 있어야 한다. 세트메뉴는 기본적으로 햄버거 + 감자튀김 + 음료의 조합이다. 대신, 콤보(햄버거 + 음료)처럼 다양한 조합이 나올 수 있다. 햄버거를 제외한 나머지 메뉴는 각 그룹 내에서 교환할 수 있다. 1. 요구사항 분석 2. 개념적 모델링 인용 https://yeongunheo.tistory.com/entry/DB-%EC%84%A4%EA%B3%84%ED%95%98%EB%8A%94-%EB%B2%95-feat-%EB%8D..
하나의 릴레이션에 관련없는 속성이 들어가지 않게 하기위해서 속성들의 친밀도를 정확히 판단하고, 이 기준에 따라 릴레이션을 구성하는 방법을 정규화라고 한다. 또는 데이베이스를 잘못 설계하면 불필요한 데이터 중복이 발생하여 릴레이션에 대한 데이터의 삽입, 수정, 삭제 연산을 수행할 때, 부작용이 발생할 수 있는데 이러 한 부작용을 이상현상이라고 하고, 이상 현상을 제거하면서 데이터베이스를 올바르게 설계해나가는 과정이 정규화이다. 이상 현상의 종류 삽입 이상: 새 데이터를 삽입하기 위해 불필요한 데이터도 함께 삽입해야 하는 문제 갱신 이상: 중복 tuple 중 일부만 변경하여 데이터가 불일치하게 되는 모순의 문제 삭제 이상: tuple을 삭제하면 꼭 필요한 데이터까지 함께 삭제되는 데이터 손실의 문제 정규화의..
논리적 데이터 모델의 개념과 특성 선택한 DBMS에 따라 사용자 입장에서 E-R 다이어그램으로 표현된 개념적 구조를 데이터베이스에 저장할 형태로 표현한 논리적인 구조를 논리적 데이터 모델이라고 한다. 즉, 논리적 데이터 모델은 논리적 데이터 모델링의 결과물이고, 사용자가 생각하는 데이터베이스의 모습 도는 구조이다. 그리고 논리적 데이터 모델로 표현된 데이터베이스의 논리적 구조가 바로 데이터베이스 스키마이다. 데이터베이스에 있는 데이터 간의 관계를 표현하는 방법에 따라 다양한 논리적 데이터 모델이 존재한다. 일반적으로 누구나 쉽게 이해할 수 있는 데이터 구조를 가지고, 데이터의 검색, 삽입, 삭제, 수정 등의 연산을 제공하는 논리적 데이터 모델이 관계 데이터 모델이다. 데이터베이스 설계 개념 관계 데이터 ..
릴레이션에 포함된 tuple들을 유일한게 구별해주는 역할은 속성 또는 속성들의 집합인 키가 담당한다. 키는 관계 데이터 모델에서 중요한 제약조건을 정의한다. 1. 슈퍼키 슈퍼키는 유일성의 특성을 만족하는 속성 또는 속성들의 집합이다. 유일성은 키가 갖추어야 하는 기본 특성으로, 하나의 릴레이션에서 키로 지정된 속성 값은 tuple마다 달라야 하다는 의미이다. 하지만 (고객아이디, 고객이름)과 같이 슈퍼키 중에는 tuple 하나를 유일하게 구별하기 위해서 또는 2개의 tuple이 서로 다름을 판단하기 위해 불필요한 속성 값까지 확인하는 비효율적인 작업이 필요한 경우도 있다. 이때, 꼭 필요한 속성의 집합만으로 tuple을 유일하게 구별할 수 있도록 하는 또 다른 키의 개념이 필요한데, 이 것이 후보키이다...
