(2021.11.05) 이번에 정리할 부분 목차 9.1 소수 9.1.1 정의 9.1.2 소수 집합의 크기 9.1.3 소수 판정 9.1.4 오일러의 φ 함수 9.1.5 페르마의 리틀 정리 9.1.6 오일러 정리 9.1.7 소수 생성 9.2 소수 판정 9.2.1 결정적 알고리즘 9.2.2 확률적 알고리즘 9.2.3 추천하는 소수 검증 9.3 소인수분해 9.3.1 산술 기본 정리 9.3.2 소인수 분해 방법 9.3.3 페르마 방법 9.3.4 pollard p-1 방법 9.3.5 Pollard rho 방법 9.3.6 더 효율적인 방법 9.1 소수 9.1.1 소수의 정의 소수: 1과 자기자신만을 약수로 가지는 수 합성수: 소수가 아닌 수 --> 3개 이상의 약수를 가짐 1은 소수가 아니다 --> 가장 작은 소수는..

(2021.11.04) 알고리즘 수업들으면서 정리하기 17탄 w10-1 실시간 강의 greedy algorithm에 관한 내용과 huffman code 설명 조금(huffman은 다음 동영상정리에) activity selection 내용 전에 greedy 알고리즘 설명해주신 부분의 연장선 같음 Greedy algorithm greedy algorithm은 언제나 optimal solution을 도출해내는 것은 아니다. greedy algorithm으로 해결했을 때, 그 결과가 optimal solution이 아닐 수도 있다는 것이다. 어떠한 상황에서 greedy로 풀면 optimal한 결과가 나온다 라는 general한 접근법이 없기 때문에 greedy algorithm은 해봐야 알 수 있다. greed..

(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.11.01) 이번에 정리할 부분 목차 8.1 현대 블록 암호의 사용 8.1.1 ECB 모드 8.1.2 CBC 모드 8.1.3 CFB 모드 8.1.4 OFB 모드 8.1.5 CTR 모드 8.2 스트림 암호의 사용 8.2.1 RC4 8.2.2 A5/1 8.3 그 밖의 이슈 8.3.1 키 관리 8.3.2 키 생성 8.1 현대 블록 암호의 사용 : 대칭키 암호화 기법은 현대 블록 암호를 기반으로 수행된다. DES와 AES라는 현대 블록 암호는 고정된 길이의 텍스트 블록을 암호화하고, 복호화한다. DES는 64비트, AES는 128비트 블록을 암호화하고 복호화하는데 실제 응용 환경에서 암호화되는 텍스트 길이는 가변적이고, 일반적으로 64비트나 128비트보다 훨씬 길다. --> 이러한 문제를 해결하기 위..

(2021.11.01) 이번에 정리할 부분 목차 3.3 전치 암호 3.3.1 키가 없는 전치 암호 3.3.2 키가 있는 전치 암호 3.3.3 두가지 방법의 결합 3.4 스트림 암호와 블록 암호 3.4.1 스트림 암호 3.4.2 블록 암호 3.3 전치 암호(Transposition Ciphers) : 전치 암호는 기호의 위치를 바꾸는 것으로 위치를 재정렬하는 것이다. 3.3.1 키가 없는 전치 암호(keyless transposition ciphers) 키가 없는 전치 암호에서 문자의 치환에는 두가지 방법이 있다. 1) 열 순서로 기록한 후, 행 순서로 전송하기 --> rail fence 암호 2) 행 순서로 기록한 후, 열 순서로 전송하기 --> 키가 없는 전치 암호는 해독이 매우 쉽다는 단점이 있다. ..

(2021.10.27) 알고리즘 수업들으면서 정리하기 15탄 Activity selection :공통의 자원에 대한 독점적인 사용을 필요로 하는 활동 N개가 있는데 이를 어떻게 스케줄링 할 것인가 하는 문제를 말한다. ex) 교실의 대한 사용을 스케줄링 하는 문제 Problem: 여러 competing activities 사이의 스케줄을 조정하는 것 ( 각 activity에 대해서 시작과 종료시간은 주어짐) Goal: nonoverlapping activities 의 largest possible set을 선택함 이를 이제 dynammic programming 기법으로 접근해보겠다 greedy algorithms으로 접근하는 건 다음 시간..

(2021.10.27) 알고리즘 수업들으면서 정리하기 14탄 greedy algorithms 개념 (생각보다 내용이 없다) Greedy algorithms : 탐욕 알고리즘 greedy algorithm은 dynamic algorithms과 마찬가지로 optimization에 쓰인다. greedy algorithm은 the activity selection problem에도 쓰인다. dynamic algorithms vs greedy algorithms - dynamic algorithms은 problem을 sub-problem으로 나누어서 sub-problem을 overlapping 하며 larger sub-problem으로 build up 해간다. - greedy algorithms은 problem을..

(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.14) 알고리즘 수업들으면서 정리하기 12탄 7주차 실강 내용- rod cutting problem (손글씨가 아닌 모든 첨부사진은 교수님 강의노트가 출처-알고리즘 교재) Rod cutting problem 설명하시기 전에 왜 dynamic programming인가?? 에 대한 수업을 하셨다 Why dynamic programming?? duplicate computation(반복적인 계산)이 많을 때, dynamic programming이 아주 효과적임! 예를 들어 생각하면 이해하기 쉽다. n개에서 k개를 고르는 이항정리 문제는 위와 같이 표현할 수 있다. 이것으로 코드를 만들어본 것이 아래다. C(n,k)=C(n-1,k-1)+C(n-1,k)에서 다시 C(n-1,k-1)과 C(n-1,k..

(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.10) 알고리즘 수업들으면서 정리하기 9탄 5주차 내용-3 마지막!!! Binary search 주어진 배열에서 찾고자하는 값이 있는 인덱스를 찾는 problem 이다. Divide-and-conquer approach Divide A[1..n] into two parts A[1..mid-1] and A[mid+1..n] Conquer: if A[mid]=x, return mid if A[mid]x, return A[1..mid-1] for next iteration Combine: just return the result (key: can reduce the array to it's half for the next iteration) BINARY_SEARCH(A,low,high,key)..

(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.09) 알고리즘 수업들으면서 정리하기 7탄 5주차 내용인데 이해하는데 오래걸림.. Maximum-subarray problem

(2021.10.08) 알고리즘 수업들으면서 정리하기 6탄 5주차 내용 -1 (4주차는 추석이어서 수업 없었음) Maximum-subarray problem input: sequence of numbers A[1 ... n] output: subarray의 greatest sum(contiguous subarray of A) A[i ... j] Naive approach 교수님께서 어떠한 문제를 풀 때는 naive하게 풀어보는 것부터 시작해보라고 하셨다 (naive 뜻을 몰라서 처음엔 무슨 말인지 이해하지 못했음) Divide-and-conquer approach Subproblem: Find a maximum subarray of A[low..high] (original call low=1, high=..