728x90 전체 글431 Computational Graph / Backpropagation Gradient위와 같은 SVM Loss function에 대해서 어떤 식으로 gradient를 연산할지 생각해보자.당연히 직접 계산을 하나씩 해나갈 수 있다.그러나 당연하게도 직접 하나하나 계산하는 것은 어마어마한 양의 행렬 연산으로 인해 낭비가 많다. 또한 만약 Loss function을 바꾸고 싶어지면 연산을 처음부터 다시해야한다. 마지막으로 복잡한 모델에서는 더더욱 문제가 많을 것이다. 따라서 Computational graphs와 Backpropagation을 이용한다. 아래는 Computational graphs의 표현법이다.역전파의 간단한 예시를 살펴보자.우리가 알고있는 미분 값과 알고 싶은 미분 값은 아래와 같다.이를 chain rule을 이용하여 역으로 진행시켜 구할 수 있다.위 과정을 .. 2024. 5. 3. 프로그래머스 - 소수 만들기 문제문제 설명 주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요. 제한사항 1. nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다. 2. nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다. 입출력 예 nums result [1,2,3,4] 1 [1,2,7,6,4] 4 입출력 예 #1[1,2,4]를 이용해서 7을 만들 수 있습니다. 입출력 예 #2[1,2,4]를 이용해서 7을 만들 .. 2024. 5. 2. Algorithm design - DP / Levenshtein Distance Dynamic ProgrammingDynamic Programming은 동적 계획법이라는 뜻이지만 실제로 그렇게 동적이지는 않다. 오히려 기록해둔 과거 기록을 저장해두고 꺼내서 이용한다는 점에서 Tabular Method라는 이름이 어울린다.Divide-And-Conquer는 top-down approach로 나누어진 부분들 사이에 서로 상관관계가 없는 문제를 해결하는데 적합하다. 반면Dynamic programming은 bottom-up approach로 큰 문제를 작은 문제로 나눈 다는 점은 Divide-And-Conquer와 동일하나 작은 문제를 먼저 해결하고, 그 결과를 저장한 다음, 후에 그 결과가 필요할 때마다 다시 계산하는 것이 아니고 그 저장된 결과를 이용한다는 점이 다르다. 해답을 구축하.. 2024. 5. 2. Digital Image Processing - Color Image Processing Backgrounds of Color색의 3속성은 흔히 색상(Hue), 명도(Brightness,value), 채도(Purity,saturation,chroma)로 불린다.Primary color(원색)은 서로 혼합되어 다른 컬러를 생성하는 기본 색상으로 일반적으로 R,G,B의 3색을 이용한다. 100% 모든 color를 생성하지는 못하지만 practically 충분하다.Color gamut은 Primary color의 조합으로 만들어낼 수 있는 모든 컬러를 말한다.CIE XYZ Color ModelCIE(CommissionInternationaledeI'Eclairage,International Commission on Illumination)에서 제정한 모델로 CIE primary color를 정했다.. 2024. 5. 1. 알고리즘 설계 실습 - Fibo_counter 문제피보나치 수는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 아래 소스 코드는 N번째 피보나치 수를 구하는 재귀함수이다.int fibonacci(int n) { if (n == 0) { print("0"); return 0; } else if (n == 1) { print("1"); return 1; } else return fibonacci(n‐1) + fibonacci(n‐2);}fibonacci(3)을 호출하면 다음과 같이 동작한다.- fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출- fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출- 두 번째 호출한 fi.. 2024. 5. 1. 시험 대비 코드 정리(2) 보호되어 있는 글 입니다. 2024. 4. 22. 시험 대비 코드 정리(1) 보호되어 있는 글 입니다. 2024. 4. 19. Algorithm Design - Huffman encoding / Encryption / RSA File compression시간보다는 공간을 절약하는 방법에 대해 연구된다. 대부분의 컴퓨터 화일에서 데이터가 중복되어 있다는 것에 착안된 개념이다. 파일 압축의 대상으로는 텍스트 파일 인코딩된 이미지의 래스터 파일 사운드나 다른 아날로그 신호의 디지털 표현 등이 있다. 현재는 허프만 인코딩이 거의 주를 이루지만 이 개념이 나오기까지 몇몇 다른 시도들이 존재했었다. 우선 run-length encoding(런-길이 인코딩)은 동일한 문자가 여러개 나올 경우 숫자와 문자쌍으로 화일을 압축하는 기법이다. 이진수로 표현되는 비트맵 이미지를 압축하는데 사용됐었다. 화일에서 가장 기본적인 중복은 같은 문자가 연속적으로 나타나는 것이다. 이를 다음과 같이 압축해내는 기법이다.AAAABBCCC → 4A2B3C.. 2024. 4. 18. Digital Image Processing - Fourier transform / Frequency domain 푸리에 변환 푸리에 변환은 Fourier가 제시한 아이디어인 Fourier series라는 모든 주기함수는 각기 다른 주파수의 사인과 코사인 함수의 가중합으로 표현될 수 있다는 아이디어로부터 확장된 개념이다. 아래 그림은 다양한 주파수의 사인함수를 더해서 unit function에 수렴하게 만드는 대표적인 Fourier series의 예시이다. 푸리에 변환은 어떤 함수를 주기함수(주파수를 갖는 함수)의 합으로 표현할 수 있다는 개념을 차용하여 아래와 같이 변환하는 방법이다. 물론 그 역과정을 통해 원시함수를 찾아내는 푸리에 역변환 과정도 가능하다. 이때 F(w)는 Magnitude가 A이고 Phase가 Ø인 주기함수이고 각각은 아래와 같이 실수부 R(w)과 허수부 I(w)로 표현된다. Continuous.. 2024. 4. 18. Optimizer Optimizer 모델이 학습한다는 것은 loss를 최소화하는 최적화과정을 거치는 것이다. 이전에도 optimizer를 직접 구현하며 optimizer의 종류를 알아보고 성능을 비교해봤지만 너무 중요한 내용이고 수업에 나왔기에 다시 한번 수식과 그 의미를 간단히 정리해보고자 한다. 딥러닝 직접 구현하기 - (Optimizer) SGD 확률적 경사 하강법(stochastic gradient descent)의 줄임말인 SGD는 현재 상태에서 학습률과 미분값에 비례한 값을 빼서 갱신하는 방식을 이용한다. 위 식을 기반으로 파이썬 클래스로 구현하면 아래 canvas4sh.tistory.com SGD Stochastic Gradient Descent는 확률적 경사 하강법으로 이름 그대로 모든 데이터에 대해서 그래.. 2024. 4. 17. 알고리즘 설계 실습 - KMP 문제 KMP 알고리즘을 구현하세요. 구현한 KMP 알고리즘으로 문자열 T에서 문자 열 P를 모두 찾고, 찾은 개수와 위치를 출력하세요. 첫째 줄에는 문자열 T가 주어집니다. 문자열 T의 길이 n은 1이상 100만 이하입니다. 둘째 줄에는 문자열 P가 주어집니다. 문자열 P의 길이 m은 1 이상 26 이하입니다. 문자열은 모두 알파벳 대문 자로만 이루어져 있습니다. (줄 바꿈 문자 \n을 포함하면 최대 문자열 길이가 2 추가됩니다.) 첫째 줄에는 문자열 T에서 문자열 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력하세요. 둘째 줄에는 문자열 T에서 문자열 P가 나타나는 위치를 차례대로 공백으로 구분하여 출력하세요. 예를 들면, 문자열 T의 i～i+m-1번째 문자와 P의 1～m번째 문자가 차례로 일.. 2024. 4. 17. Algorithm Design - 라빈-카프 / 패턴 매칭 Rabin-Karp 라빈-카프 알고리즘은 스트링을 숫자값으로 바꾼 다음 해시 값을 계산하여 매칭하는 알고리즘이다. 최악의 시간 복잡도는 O(MN)이지만 평균적으로는 선형에 가까운 빠른 속도를 가지는 알고리즘이다. 첫 번째 M 자리의 나머지를 구한 다음부터는 한 자리씩만 추가하면서 간단한 계산으로 나머지를 구할 수 있으므로 빠른 시간에 스트링 탐색을 수행한다. 해시 값이 다르다면 두 문자열이 다르다는 것이 보장된다. 그러나 해시 값이 같다고 해서 두 문자열이 같다는 것이 보장되지는 않기 때문에 해시값이 같은 경우 문자열을 비교하는 과정을 거친다. 찾고자하는 패턴은 한번 연산을 해두면 해시값이 정해져있지만 한칸씩 넘어가며 텍스트와 비교를 할때 텍스트에서 비교하고자 하는 부분의 해시값을 매번 다시 연산하는 것.. 2024. 4. 17. 이전 1 ··· 5 6 7 8 9 10 11 ··· 36 다음 728x90
