동기, 비동기 여기서의 동기, 비동기는 프로그래밍 영역이랑 관련이 있다. 개발을 하다보면 "동기 또는 비동기적으로 수행한다" 라는 말을 종종 듣게 된다. 무슨 의미일까? 동기, 비동기는 실행 순서에 관한 개념이다. 동기 코드는 위에서부터 아래로 순차적으로 수행된다. 그래서 순차 코드라고 불리기도 한다. 만약 중간에 I/O 코드가 있으면 I/O 작업이 끝날때까지 대기한 후 다음 코드를 실행한다. 비동기 코드는 순차적으로 실행되지 않는다. 비동기 코드가 수행된 시점부터 프로그램의 실행 순서를 특정할 수 없으며 아래처럼 실행 순서는 3가지 경우로 나눠진다. 비동기 코드가 먼저 수행 다음의 동기 코드가 먼저 수행 비동기 코드와 다음의 동기 코드가 동시 수행 비동기 코드는 실행 순서를 특정할 수 없게 만들어 프로..
서브 쿼리 쿼리 내부에 포함된 select 쿼리를 서브 쿼리(Sub Query)라 부른다. select 쿼리에 들어가는 서브 쿼리 종류에는 인라인 뷰, 스칼라 서브쿼리, 중첩 서브쿼리가 있다. 이때 서브 쿼리를 포함한 select 쿼리를 메인 쿼리라 하며 서브 쿼리가 실행 된 후 메인 쿼리가 실행된다. 1. 인라인 뷰 from 절에 들어가는 서브 쿼리 서브 쿼리의 조회 결과를 테이블 처럼 사용할 때 씀 alias 지정 필수 select * from ( select l.common, l.col_l, r.col_r from table_l l left join table_r r #on table_l.common = table_r.common; using(common) union select r.common, ..
Join MySQL의 sql로 관계 대수의 자연 조인, 세타 조인, 외부 조인, 세미 조인, 카티션 곱 등이 가능하다. inner join 두 릴레이션에 있는 모든 튜플을 조회 한다. 조인을 할 때 주로 ANSI 조인 형태를 사용한다. ANSI 조인은 JOIN 키워드와 ON이 있기 때문에 쉽게 조인 조건을 알 수 있다. # ANSI 조인 형태 # 다른 sql에서도 범용적으로 사용 가능 # where 조건절과 join 조건이 분리되므로 가독성이 높음 select * from table_l [inner] join table_r on table_l.common = table_r.common; # 조인 속성이 동일 하다면 아래와 같이 쓸 수 있음 select * from table_l [inner] join t..
Segment Tree 구간 트리(Segment Tree)는 저장된 자료의 특정 구간 질의를 빠르게 대답하기 위해 저장된 자료를 전처리한 트리를 말한다. 흔히 구간 트리는 일차원 배열의 특정 구간 질의를 빠르게 대답하는데 사용된다. 예를 들어 [1, 7, 5, 3, 2] 라는 일차원 배열이 있을 때 [1, 2] 구간의 최소치를 찾는 연산을 해야 한다. 이를 연산하는 간단한 방법은 구간의 시작부터 끝까지 순회하면서 최소치를 찾으면 되며 시간 복잡도는 O(N)이 된다. 반면 구간 트리를 한 번 만들어두면 위 연산을 O(log N)으로 할 수 있다. 구간 트리의 핵심 아이디어는 배열 구간에 대한 이진 트리를 만드는 것이다. 구간 트리의 노드는 구간을 표현한다. 루트 노드는 항상 배열의 전체 구간 [0, n-1..
최단 경로 최단 경로 문제(shortest path problem)는 그래프에서 주어진 두 정점을 연결하는 가장 짧은 경로를 찾는 문제로, 그래프 관련 문제 중에서 최단 경로 문제가 많다. 최단 경로 문제를 해결하기 위해서는 그래프가 어떤 그래프인지 파악하고, 그에 맞는 최단 경로 알고리즘을 적용해야한다. 최단 경로 알고리즘은 최단 경로를 구성하는 정점들의 목록을 구해 주는 것이 아닌 최단 경로의 길이를 찾아줄 뿐이라는 점에 유의해야한다. 실제 경로를 계산하기 위해서는 BFS에서 그랬듯이 탐색 과정에서 별도의 정보를 저장하고, 이것으로부터 실제 경로를 찾아내야한다. 가중치가 없는 그래프에서는 BFS로 최단 경로를 구할 수 있다. 여기서의 최단 경로는 경로의 길이가 가장 짧은 경로를 말한다. 가중치가 있는..
Binary Search Tree (BST) 데이터 탐색 알고리즘으로 이진 탐색 알고리즘이 있다. 탐색 범위를 반으로 줄이면서 탐색하는 알고리즘이다. 정렬된 배열에서 이진 탐색 알고리즘을 적용해 O(log N)의 시간복잡도로 탐색할 수 있지만 배열의 원소를 추가, 삭제하는데 O(N)의 시간복잡도가 든다는 단점이 있다. 이를 극복하기 위해 BST를 사용한다. 균형 잡힌 BST(BBST)라면 탐색, 삽입, 삭제의 시간 복잡도를 O(log N)으로 만들 수 있다. BST는 이진 트리에 속하며 이진 탐색을 목적으로 하는 트리다. BST의 모든 노드는 아래의 규칙을 갖는다. 각 노드의 왼쪽 서브 트리에는 해당 노드의 원소보다 작은 원소를 가진 노드들이, 오른쪽 서브 트리에는 해당 노드의 원소보다 큰 원소를 가진 ..
트리 트리는 계층 구조를 표현하는 자료구조이다. 트리는 다양한 목적으로 사용되어 다양한 종류의 트리들이 등장했다. 현실 세계 계층 구조 표현 이진 검색 트리 힙 세그먼트 트리 유니온-파인드 트라이 등등 트리 용어 node(노드) : 트리 구성 요소 edge(간선) : 노드와 노드를 연결한 선 parent : 두 노드가 간선으로 연결되었을 때 상위 노드 child : 두 노드가 간선으로 연결되었을 때 하위 노드 sibling : 같은 부모를 가지는 자식 노드들 ancestor : 부모 노드와 그 부모 노드의 상위 노드들 descendant : 자식 노드와 그 자식 노드의 하위 노드들 root : 부모가 없는 최상위 노드 leaf : 자식이 없는 노드 Internal : 리프 노드가 아닌 노드 depth :..
신장 트리 (Spanning Tree) n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리, 즉 그래프의 모든 정점을 가장 적은 개수의 간선으로 연결한 그래프 최소 신장 트리 (Minimum Spanning Tree) 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 신장 트리, 최소 신장 트리를 만드는 대표적인 알고리즘에는 Prim 또는 Kruskal 알고리즘이 있다. 보통 최소 신장 트리를 줄여서 MST라고 부른다. Kruskal 알고리즘 1. 최초, 모든 간선을 가중치 순으로 오름차순 정렬 1-1. 간선 리스트를 만든다. 1-2. 만든 간선 리스트를 가중치 순으로 오름차순 정렬한다. 2. 간선을 하나씩 확인해 해당 간선이 사이클을 발생시키는지 확인 (초기..
