DailyStudyNote

이진 탐색(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(백만)을 넘지 않는 경우 → 필수적인 조건은 아니지만 차이가 클 수록 메모리의 사용이 많아진다...

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

삽입 정렬(Insertion Sort) 삽입 정렬(Insertion Sort) 란? 삽입 정렬(Insertion Sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치에 삽입함으로써 정렬을 완성하는 알고리즘이다. 삽입 정렬은 처음 Key 값을 두 번째 요소부터 시작하게 되며 그 앞쪽 요소들과 비교하여 삽입할 위치를 지정한 후 요소를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘이다. 삽입 정렬(Insertion Sort) 시간 복잡도 ▶ 최악의 경우(입력 자료가 역순일 경우) T(n) = O(n^2) ▶ 최선의 경우(입력 자료가 정렬되어 있는 경우) T(n) = O(n) 삽입 정렬(Insertion Sort) 알고리즘의 특징 1. 대부분의 ..

'어서와! 자료구조와 알고리즘은 처음이지?' 이진트리의 넓이 우선 순회(BFS; Breadth First Traversal) 원칙 ✔ 수준(level)이 낮은 노드를 우선으로 방문 ✔ 같은 수준의 노드들 사이에서는 부모 노드의 방문 순서에 따라 방문 ✔ 왼쪽 자식 노드를 오른 쪽 자식 노드보다 먼저 방문 ✔ 한 노드를 방문했을 때, 나중에 방문할 노드들을 순서대로 기록(방문한 노드의 자식 노드 기록) ✔ 큐(Queue) 이용 → 순회 결과: A - B - C - D - E - F - G - H - J 알고리즘 설계 1. traversal 빈 리스트 초기화 2. 빈 트리가 아니면(root != None) root node를 큐에 추가(enqueue) 3. q 가 비어있지 않는 동안, 3.1 node ← q..

'어서와! 자료구조와 알고리즘은 처음이지?' 이진 트리(Binary Tree) 연산의 정의 1. size() - 현재 트리에 포함되어 있는 노드의 수를 구한다. 2. depth() - 현재 트리의 깊이 (또는 높이, height)를 구한다. 3. 순회(traversal) 이진 트리의 구현 - 노드(Node) class Node: def __init__(self, item): self.data = item self.left = None self.right = None 이진 트리의 구현 - 트리(Tree) class BinaryTree: # r 은 node def __init__(self, r): self.root = r 이진 트리의 구현 - size() 재귀적인 방법으로 쉽게 구할 수 있다. class N..

'어서와! 자료구조와 알고리즘은 처음이지?' 트리(Tree) 정점(node)와 간선(edge)을 이용하여 데이터의 배치 형태를 추상화한 자료구조 ✔ 부모의 부모(의 부모의...) - 조상(ancestor) ✔ 자식의 자식(의 자식의...) - 후손(descendant) 트리의 높이(Height) 트리의 높이(height) = 최대수준(level) + 1 트리의 높이는 깊이(depth)라고도 한다. 부분트리(서브트리, SubTree) 노드의 차수(Degree) = 자식(서브트리)의 수 degree 가 0인 노드는 leaf 노드이다. 이진트리(Binary Tree) 모든 노드의 차수가 2 이하인 트리 이진트리는 재귀적으로 정의할 수 있다. ✔ 빈 트리(Empty Tree)이거나 ✔ 루트노드 + 왼쪽 서브트리..