DailyStudyNote

DFS(Depth First Search, 깊이 우선 탐색) BFS(Breadth First Search, 너비 우선 탐색) DFS(Depth First Search, 깊이 우선 탐색) 란 루트 노드 혹은 다른 임의의 노드에서 다음 분기(Branch)로 넘어가 기전에 해당 분기를 완벽하게 탐색하는 방법이며 스택(Stack) 혹은 재귀함수(Recursion)로 구현된다. 코드(Python) """ 1 / | \ 2 5 9 | /\ | 3 6 8 10 / | 4 7 """ graph = { 1: [2,5,9], 2: [3], 3: [4], 4: [], 5: [6,8], 6: [7], 7: [], 8: [], 9: [10], 10: [] } def recursive_dfs(v, visited = []): vi..

최소 공통 조상(Lowest Common Ancestor, LCA) 최소 공통 조상(Lowest Common Ancestor, LCA) 란? 최소 공통 조상(LCA) 란 두 노드의 공통된 조상 중에서 가장 가까운 조상을 찾는 알고리즘 이다. 즉 두 정점이 만나는 최초 부모 정점을 찾는 것을 의미한다. 최소 공통 조상(Lowest Common Ancestor, LCA) 알고리즘 모든 노드에 대한 깊이(Depth)를 계산한다. 최소 공통 조상을 찾을 두 노드를 확인한다. 먼저 두 노드의 깊이(Depth)가 동일 하도록 거슬러 올라간다. 이후에 부모가 같아질 때까지 반복적으로 두 노드의 부모 방향으로 거슬러 올라간다. 최소 공통 조상을 찾을 두 노드를 확인한다. LCA 알고리즘 풀이 이해 1. 각 노드의 "D..

이진 탐색(Binary Search) 이진 탐색(Binary Search) 란? 정렬되어 있는 배열에서 특정한 값을 찾아내는 알고리즘이다. 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X 와 비교한다. X 가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터를 대상으로, X 가 중간 값보다 크면 우측을 대상으로 다시 탐색한다. 동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교한다. 해당 값을 찾을 때까지 이 과정을 반복한다. 코드(Python) # 반복 알고리즘 def binary_search(arr, target): low, high = 0, len(arr) - 1 while low target: high = mid - 1 if arr[mid] == target: return mi..

최장 증가 부분 수열 (LIS, Longest Increasing Sequence) 최장 증가 부분 수열(LIS) 란? 어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거하여 부분 수열을 만들 수 있다. 이 때 만들어진 부분 수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라 한다. 예를 들어, [6,2,5,1,7,4,8,3] 라는 수열이 존재하는 경우 LIS는 [2,5,7,8] 이 된다. [2,5], [2,7] 등 증가하는 부분 수열은 많지만 그 중에서 가장 긴 것이 [2,5,7,8] 이기 때문이다. LIS(최장 증가 부분 수열)의 길이를 구하는 방법에는 두 가지가 있다. (1) DP(Dynamic Programing, 동적 계획법) - O(N^2) 알고리즘 (2) Lo..

계수 정렬(Counting Sort) 계수 정렬(Counting Sort) 계수 정렬(Counting Sort)란 숫자들간 비교를 하지 않고 정렬하는 알고리즘이다. 각 숫자가 몇개 있는지 개수를 세어 저장한 후에 정렬하는 방식이다. 계수 정렬은 특정한 조건이 부합될 때만 사용할 수 있는데 조건은 다음과 같다. ▶ 데이터의 크기 범위가 제한된 경우 → 0~100 까지의 점수를 정렬하는 경우가 이 조건에 해당하는 예가 될 수 있다. ▶ 데이터가 양의 정수인 경우 → 데이터가 실수인 경우 무한의 범위를 가질 수 있으므로 1번 조건에 부합하지 못한다. ▶ 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000(백만)을 넘지 않는 경우 → 필수적인 조건은 아니지만 차이가 클 수록 메모리의 사용이 많아진다...

힙(Heaps) 힙(Heap)이란? 이진 트리의 한 종류 (이진 힙-binary heap)이다. 1. 루트(root) 노드가 언제나 최댓값 또는 최솟값을 가진다. 최대 힙(max heap) 최소 힙(min heap) 2. 완전 이진 트리 완전 이진 트리란 각 노드가 최대 2개의 자식 노드를 갖는 트리 형태의 자료구조 로서 마지막 레벨을 제외한 모든 노드는 완전히 채워져 있어야 한다. 최하단 레벨의 노드는 좌측만 노드가 채워져 있거나 좌측과 우측 모두 채워져 있어야 한다. 노드를 삽입할 때는 최하단 좌측 노드부터 차례대로 삽입해야 한다. 최대 힙(max heap)의 추상적 자료 구조 재귀적으로도 정의된다. 즉, 어느 노드를 루트로 하는 서브 트리도 모두 최대 힙 이다. 연산의 정의 __init__(): 빈..

조인(Join) 조인(Join) 이란? 두개 이상의 테이블이나 데이터베이스를 연결하여 데이터를 검색하는 방법이다. 자신이 검색하고 싶은 컬럼이 다른 테이블에 있을 경우 주로 사용하며 여러 개의 테이블을 마치 하나의 테이블인 것처럼 활용하는 방법이다. 보통 Primary Key 혹은 Foreign Key 로 두 테이블을 연결한다. 테이블을 연결하려면 적어도 하나의 컬럼은 서로 공유되고 있어야 한다. Inner Join 기준 테이블과 조인한 테이블의 중복된 값을 보여준다. 쉽게 말해 교집합이라고 생각하면 된다. 결과 값은 A의 테이블과 B테이블이 모두 가지고 있는 데이터만 검색이 된다. --문법-- SELECT 테이블별칭.조회할칼럼, 테이블별칭.조회할칼럼 FROM 기준테이블 별칭 INNER JOIN 조인테이..

퀵 정렬(Quick Sort) 퀵 정렬(Quick Sort) 이란? 퀵 정렬은 평균적으로 매우 빠른 수행속도를 자랑하는 정렬 방법으로 분할정복(Divide and Conquer) 알고리즘이다. 퀵 정렬은 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다. 또한 병합 정렬과는 다르게 퀵 정렬은 배열을 비 균등하게 분할한다. 분할(Divide) → 정복(Conquer) → 결합(Combine) 퀵 정렬은 pivot 을 선정하여 pivot 을 기준으로 좌측과 우측으로 pivot 보다 작은 값은 왼쪽 pivot 보다 큰 값은 오른쪽으로 재배치를 하고 계속해서 분할하여 정렬하는 알고리즘이다. * 분할정복(Divide and Conquer) 문제를 작은 2개의 문제로 분리하고 각각..