Knuth-Morris-Pratt 3명이 개발한 알고리즘이다. 보통 첫 글자를 따서 KMP 알고리즘이라고 한다. 이 알고리즘은 문서에서 동일한 문자열을 찾기 위해서 사용한다.배열 S에서 문자열 W가 몇 개가 있는지를 찾아내는 알고리즘을 만들어 보자. S 배열의 처음부터 W가 일치하는지를 일일이 확인하는 간단한 방법을 생각 할 수 있다. 아래 예제를 보자. ...
길이가 같은 두 개의 문자열 S와 T가 있다. 이들이 같은 형태의 문자열인지를 판단하라. 같은 형태란 S에 있는 문자를 다른 문자로 치환해서 T와 같아지걸 의미한다. 예제. "egg"와 "add"는 true를 반환한다. e를 a로 g를 d로 치환하면 add가 되기 때문이다. "foo"와 "bar"는 false를 반환한다. "paper"과 "title"는 t...
알고리즘은 문제를 정확하게 해결하는 것이 중요하다. 이때 정확하게 해결한다는 의미는 답을 얻기만 하면 된다는 의미가 아니다. 적당한 시간내에 답을 얻을 수 있어야 한다는 것을 의미한다. 어떤 알고리즘은 컴퓨터를 동원하더라도 수십년 혹은 수백만년이 걸릴 수 있다. 반면 동일한 문제를 푸는데, 하루 혹은 몇 시간이 걸리는 알고리즘을 만들 수도 있다. 아주 간단...
역폴란드 표기법(Reverse Polish notation - RPN) 혹은 후위 표기법은 연산자(operator)를 연산대상(operands)의 뒤에 쓰는 연산 표기법이다. 예를 들어 "3 + 4"의 경우 "3 4 +"로 표기한다. 연산자가 두 개 이상이라면 연산자 바로 뒤에 다음번 연산대상을 표기한다. "3 - 4 + 5"가 있다면 "3 4 - 5 +"...
n개의 원소를 가진 배열을 뒤집는다. n=7 때, 배열 로 회전하기 위한 몇 개의 방법이 있는가.아마도 가장 간단하게 생각 할 수 있는 방법일 것이다. 원본 배열과 같은 크기의 배열을 만들고, 원본 배열의 맨 뒤에서 부터 순환하면서 값을 복사한다. O(n) 공간과 O(n) 시간이 필요하다. O(1) 공간을 사용하는 방법을 찾아보자.O(1)이며 공간 복잡도는...
n개의 원소를 가진 배열을 k번 만큼 오른쪽으로 회전하라. 예를 들어 n=7, k=3 이라면, 배열 가 된>다.원본 배열과 동일한 크기의 배열을 만들어서, 순환된 결과를 복사한다. 공간복잡도 O(N), 시간복잡도 O(N)이다.버블소트를 응용해서 공간 복잡도를 O(1)로 줄일 수 있다.공간 복잡도는 O(1)이지만 시간 복잡도는 O(nk)다. 예제의 경우 시간...
성능은 아래와 같다. getRandom(100)을 10000회 실행한 결과다.컴퓨터는 입력에 따라 출력이 정해진다. 따라서 컴퓨터는 의사난수만을 만들 수 있다. 이 입력 값을 Seed라고 한다. Seed 값에 따라서 난수표가 달라진다. Seed를 이용하는 난수 발생기는 Seed를 예측 할 수 있기 때문에, 시간을 이용해서 Seed를 예측하기 힘들게 한다. ...
선형회귀를 이해하면 Logistic classification을 더 쉽게 이해 할 수 있다. 그래서 복습한다. 복습해야 할 내용은 아래와 같다. Hypothesis Cost Function Gradient decent아래와 같은 데이터가 있다고 가정해보자.|| x1(hours) || x2 (attendance) || y(score) |||| 10 || 5...
다중 선형 회귀(Multivariable linear regress)는 설명 변수가 두개 이상인 회귀분석을 의미한다. 단순 회귀 선형의 Hypothesis는 H(x)=Wx+b이다. 반면 다중 선형 회귀의 Hypothesis 는H(x_1, x_2)=w_{1}x_{1}+w_{2}x_{2}+b이다.x_1외에 x_2가 추가 됐기 때문에, w도 하나가 추가됐다. 설...
871 POSTS HERE
Knuth-Morris-Pratt 알고리즘
Knuth-Morris-Pratt 3명이 개발한 알고리즘이다. 보통 첫 글자를 따서 KMP 알고리즘이라고 한다. 이 알고리즘은 문서에서 동일한 문자열을 찾기 위해서 사용한다.배열 S에서 문자열 W가 몇 개가 있는지를 찾아내는 알고리즘을 만들어 보자. S 배열의 처음부터 W가 일치하는지를 일일이 확인하는 간단한 방법을 생각 할 수 있다. 아래 예제를 보자. ...
Isomorphic String
길이가 같은 두 개의 문자열 S와 T가 있다. 이들이 같은 형태의 문자열인지를 판단하라. 같은 형태란 S에 있는 문자를 다른 문자로 치환해서 T와 같아지걸 의미한다. 예제. "egg"와 "add"는 true를 반환한다. e를 a로 g를 d로 치환하면 add가 되기 때문이다. "foo"와 "bar"는 false를 반환한다. "paper"과 "title"는 t...
알고리즘 기반 지식 : 복잡도 측정
알고리즘은 문제를 정확하게 해결하는 것이 중요하다. 이때 정확하게 해결한다는 의미는 답을 얻기만 하면 된다는 의미가 아니다. 적당한 시간내에 답을 얻을 수 있어야 한다는 것을 의미한다. 어떤 알고리즘은 컴퓨터를 동원하더라도 수십년 혹은 수백만년이 걸릴 수 있다. 반면 동일한 문제를 푸는데, 하루 혹은 몇 시간이 걸리는 알고리즘을 만들 수도 있다. 아주 간단...
Reverse Polish notation
역폴란드 표기법(Reverse Polish notation - RPN) 혹은 후위 표기법은 연산자(operator)를 연산대상(operands)의 뒤에 쓰는 연산 표기법이다. 예를 들어 "3 + 4"의 경우 "3 4 +"로 표기한다. 연산자가 두 개 이상이라면 연산자 바로 뒤에 다음번 연산대상을 표기한다. "3 - 4 + 5"가 있다면 "3 4 - 5 +"...
배열 뒤집기
n개의 원소를 가진 배열을 뒤집는다. n=7 때, 배열 로 회전하기 위한 몇 개의 방법이 있는가.아마도 가장 간단하게 생각 할 수 있는 방법일 것이다. 원본 배열과 같은 크기의 배열을 만들고, 원본 배열의 맨 뒤에서 부터 순환하면서 값을 복사한다. O(n) 공간과 O(n) 시간이 필요하다. O(1) 공간을 사용하는 방법을 찾아보자.O(1)이며 공간 복잡도는...
배열 회전
n개의 원소를 가진 배열을 k번 만큼 오른쪽으로 회전하라. 예를 들어 n=7, k=3 이라면, 배열 가 된>다.원본 배열과 동일한 크기의 배열을 만들어서, 순환된 결과를 복사한다. 공간복잡도 O(N), 시간복잡도 O(N)이다.버블소트를 응용해서 공간 복잡도를 O(1)로 줄일 수 있다.공간 복잡도는 O(1)이지만 시간 복잡도는 O(nk)다. 예제의 경우 시간...
알고리즘
심심해서 알고리즘 문제들 풀어보기로 했다. ...
Crypto
성능은 아래와 같다. getRandom(100)을 10000회 실행한 결과다.컴퓨터는 입력에 따라 출력이 정해진다. 따라서 컴퓨터는 의사난수만을 만들 수 있다. 이 입력 값을 Seed라고 한다. Seed 값에 따라서 난수표가 달라진다. Seed를 이용하는 난수 발생기는 Seed를 예측 할 수 있기 때문에, 시간을 이용해서 Seed를 예측하기 힘들게 한다. ...
Logistic (regression) classification
선형회귀를 이해하면 Logistic classification을 더 쉽게 이해 할 수 있다. 그래서 복습한다. 복습해야 할 내용은 아래와 같다. Hypothesis Cost Function Gradient decent아래와 같은 데이터가 있다고 가정해보자.|| x1(hours) || x2 (attendance) || y(score) |||| 10 || 5...
Multi Variable Linear Regress
다중 선형 회귀(Multivariable linear regress)는 설명 변수가 두개 이상인 회귀분석을 의미한다. 단순 회귀 선형의 Hypothesis는 H(x)=Wx+b이다. 반면 다중 선형 회귀의 Hypothesis 는H(x_1, x_2)=w_{1}x_{1}+w_{2}x_{2}+b이다.x_1외에 x_2가 추가 됐기 때문에, w도 하나가 추가됐다. 설...