(23.05.14) https://github.com/gompaang/algorithm_python GitHub - gompaang/algorithm_python Contribute to gompaang/algorithm_python development by creating an account on GitHub. github.com Count sort (계수 정렬) 모든 데이터가 양의 정수이고, 데이터의 범위가 제한 적일 경우에 사용하면 매우 빠르다. 시간 복잡도와 공간 복잡도는 O(N+K) 이다. 동일한 값을 가지는 데이터가 여러 개 등장할 때 사용하기에 적합하다. # count sort def count_sort(array): count = [0] * (max(array)+1) result = []..

(23.05.14) 정렬 알고리즘 정리!! https://github.com/gompaang/algorithm_python GitHub - gompaang/algorithm_python Contribute to gompaang/algorithm_python development by creating an account on GitHub. github.com selection sort : 선택 정렬 1. 가장 작은 수를 선택하여 맨 앞의 수와 자리를 바꾼다. 2. 그 다음으로 가장 작은 수를 선택하여 맨 앞에서 두번째 수와 자리를 바꾼다. 3. 위의 과정을 반복한다. def selection_sort(array): for i in range(len(array)): min_index = i for j in ..

(2022.03.25) 기계학습 들으면서 정리하기 1탄 Lecture1_ML 내용 정리 ML 기초 지식 기존의 문제 해결 방법: 인간이 기계에게 하나하나 지시하는 것 - 새로운 문제해결이 불가능 머신러닝: 문제를 해결하는 일반적인 방법을 가르쳐줌 - 새로운 문제 해결이 가능 - 단순 지시가 아님 데이터가 입력되고 패턴(규칙)이 분석되는 과정 --> 학습 파라미터를 변경하여 동작이 결정되는 프로그램 --> 모델 더 좋은 동작이 나오도록 파라미터를 변경하는 것 --> 학습 머신러닝은 1) 파라미터에 따라 동작하는 알고리즘을 선택하고, 2) 이 알고리즘에 데이터를 제공해서 알고리즘이 더 나은 동작을 하도록 파라미터를 수정하는 것 이라고 정리해볼 수 있음. Tom Mitchell 작업 T (task) : 컴퓨터..

(2021.12.07) 알고리즘 수업 들으면서 정리하기 24탄 w14-2, w14-3 녹강 정리 TM transition function, crashing, halting 에 대해 배웠다 저번 실강이랑 겹치는 내용이 많아서 정리할 내용이 거의 없다 TM transition function (여기서 Q의 정의부분이 틀렸다. halt 를 포함하지 않는다고 되어있는데 halt state도 포함한다) 이렇게 표현할 수 있다 example) Processing a string > string의 가장 왼쪽과 가장 오른쪽에는 blank symbol을 두고, blank가 아닌 string의 가장 첫번째 cell에 tape head를 두고 과정을 진행한다. > input string w에서 transition 과정이 진..

(2021.12.01) 알고리즘 수업 들으면서 정리하기 23탄 w14 실강 NP-completeness 내용 시작 계산 복잡도, 튜링 기계에 대해 배웠다 NP-completeness Computational Complexity > 알고리즘은 특정 알고리즘의 performance 특성 (성능 특성)에 대한 연구이다. > 계산 복잡도(계산 이론)은 알고리즘보다는 문제의 특성에 대한 연구이다. 우리는 문제를 solvable problem과 unsolvable problem으로 나눌 수 있다. > unsolvable problem은 다시 세가지로 나뉜다. 1. Unsolvable problems ---> halting problem 2. Solvable problems a. Provably intractable..

(2021.11.30) 알고리즘 수업 들으면서 정리하기 22탄 w13-2 녹강 N-Queens problem에 관한 내용이다 지금까지 배운 것 중에서 개념은 정말 쉬운 것 같은데 구현하는게 어려울 것 같다.. 시간나면 구현해봐야지.. N-Queens problem : backtracking 기본형 problem이다 n x n의 체스보드에서 n개의 서로다른 queen들이 서로 공격하지 않는 자리에 어떻게 둘 수 있는지를 물어본다. 예를 들어 n=4 라고 했을 때, 4개의 Queen들이 위치할 수 있는 전체 경우의 수는 16 x 15 x 14 x 13 = 43680 가지이다. 그러나 우리는 이를 더욱 간단하게 알아 볼 수 있다. --> search space를 줄여나가면서!! 기본적인 sketch idea는..

(2021.11.12) 알고리즘 수업들으면서 정리하기 19탄 w10-3 녹화강의, w11-1 실강 BFS,DFS 내용이다. Network flow graph 알고리즘 - Breadth-first search - Depth-first search - Minimum spanning tree (Prim's algorithms) - Maximum flow (The Ford-Fulkerson method) graph G=(V,E) 로 표현한다. - V는 vertices 의 집합 (G.V) - E는 edges 의 집합 (G.E) G는 방향성일 수도 있고, 무방향성일 수도 있다. (directed, undirected) 보통 graph는 인접리스트나 인접행렬로 표현한다. BFS(Breadth-first search)..

(2021.11.08) 알고리즘 수업들으면서 정리하기 18탄 w10-2 녹화강의 huffman code 개념, 만드는 방법, greedy 알고리즘 Huffman codes each character를 binary charcter code로 디자인하는 것 optimal prefix code 라고도 한다. huffman code는 빈도수에 따라서 설정해준다. huffman code는 variable-length code이며, fixed-length code보다 효율적이다. (fixed-length code는 3비트로 표현한다--> 많은 저장용량을 차지한다.) prefix-free code (prefix code) huffman code의 가장 큰 특징은 prefix-free code(prefix code)이..

(2021.11.03) 알고리즘 수업들으면서 정리하기 16탄 w9-2 강의 activity selection을 greedy algorithm으로 푸는 방법을 배웠당 Activity Selection : greedy algorithm d.p는 subproblem이 두개가 나오지만, greedy algorithm은 subproblem이 하나만 나온다. aj와 am이 다른 경우에 Ak'를 정의하게 되는데 Ak'은 Ak에서 aj를 빼고, am을 넣은 것이라고 생각하면 된다. Ak'의 activity들이 서로 오버랩되지 않는다는 것이 중요하다. am은 Sk에서 가장 빨리 끝나는 activity이고, aj는 Ak에서 가장 빨리 끝나는 activity이다. 그렇기 때문에 am이 aj보다 빨리 끝날 것이다.(am이 더..

(2021.10.14) 알고리즘 수업들으면서 정리하기 13탄 7주차 보충강의내용- Knapsack problem (보충강의 있는지 모르고 실강 전에 안들었다..) Knapsack problem:dynamic programming 문제: item 여러개가 있는데, 그 item은 각각의 value와 weight를 가진다. knapsack은 W(kg)까지 수용할 수 있다. 이때, knapsack에 담을 수 있는 최대 value가 무엇인가?? 우선, 이 문제를 navie approach로 풀어본다면 각각의 item을 순서대로 넣을지 말지를 결정하기 때문에 2 x 2 x ... x 2=2^n 의 시간이 걸린다. --> O(n^2) Dynamic programming 의 4단계를 거쳐 문제를 풀어볼 수 있다. Ch..

(2021.10.10) 알고리즘 수업들으면서 정리하기 11탄 6주차 내용- LCS optimal substructure 을 찾는 것에 중점을 두자 recurrence를 쓸 수 있어야 함 LCS(The longest common subsequence) Definition[subsequence] Definition[common subsequence] 만약 Z가 X의 subsequece 이면서, Y의 subsequence이면, Z는 X와 Y의 common subsequence라고 한다. Z는 consecutive(연속적) 일 필요는 없으나 in order (순서대로) 여야한다. Definition[Prefix of a subsequence] X= 이라는 sequence에 대해 prefix of X (for i..

(2021.10.10) 알고리즘 수업들으면서 정리하기 10탄 6주차 내용- 새로운 개념 등장 Dynamic programming Dynamic programming 의 개념 Dynamic programming 의 4단계

(2021.10.09) 알고리즘 수업들으면서 정리하기 8탄 5주차 내용-2 Quick sort input: sequence of numbers output: permutation (오름차순) Divide-and-conquer approach Divide: Partiton the array into two subarrays(A[p..q-1] and A[q+1..r]) (A[p..q-1] ≤ A[q] < A[q+1..r]) Conquer: Sort the two A[p..q-1] and A[q+1..r] by recursive calls to quick sort Combine: no work is needed to combine them(subarrays are already sorted) a pivot x..

(2021.10.07) 알고리즘 수업들으면서 정리하기 5탄 3주차 내용 끝!! Divide-and-Conquer algorithms Divide-and-conquer를 이용하여 merge sort의 T(n) 계산 proof by telescoping 은 수업시간에 했음 ↓↓↓↓↓↓↓↓ proof by induction on n 은 과제로 했음 ↓↓↓↓↓↓↓↓ (답이 맞는지는 아직 모름..) Master Method for solving recurrences 과제로 했던 master method 문제들 ↓↓↓↓↓↓↓↓

(2021.10.06) 알고리즘 수업들으면서 정리하기 3탄 3주차 내용 Asymptotic Notation (점근적 표기) 알고리즘의 런타임을 표기하기 위해서 highest-order term으로 정의하는 것을 점근적 표기라고 한다. 점근적 표기에는 세가지가 있다. Big O: 상한선 제시 - upper bound Big Omega: 하한선 제시 - lower bound Big Theta: 상한선과 하한선 둘다 제시 (Big O는 Big theta로 표기가능하지만, Big theta는 Big O로 표기할 수 없음 - 교수님 왕강조) Big O --> 상한선 제시 : upper bound Big Omega --> 하한선 제시 : lower bound --> BEST case performance를 얘기할 ..