Rtree

R-Tree는 지리 좌표, 직사각형, 폴리곤과 같은 다차원 정보를 색인하기 위해서 사용하는 트리 데이터 구조다. R-Tree는 1984년 Antonin Guttman이 제안 했으며, 이론은 실제 상황에서도 중요하게 사용하고 있다. R-Tree의 일반적인 사용 용도는 해안선, 건물, 호수, 도로 등을 포함한 지도내에서 특정 객체의 위치를 신속하게 찾는 것이다...

알고리즘 - 생일 케이크

매년 조카의 생일케이크를 준비해야 하는 임무가 주어졌다. 당신은 케이크와 함께 조카의 나이 만큼의 초도 준비해야 한다. 케익을 받은 조카가 촛불을 끄기위해서 바람을 불면, 그 중 가장 길이가 긴 촛불이 꺼지게 된다. 조카가 바람을 불었을 때 몇 개의 촛불이 꺼질지를 계산해야 한다.예를 들어 4살 조카의 생일 케이크라면 4개의 초도 함께 준비해야 할 것이다....

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...

알고리즘

심심해서 알고리즘 문제들 풀어보기로 했다. ...

알고리즘 기반 지식 : 복잡도 측정

알고리즘은 문제를 정확하게 해결하는 것이 중요하다. 이때 정확하게 해결한다는 의미는 답을 얻기만 하면 된다는 의미가 아니다. 적당한 시간내에 답을 얻을 수 있어야 한다는 것을 의미한다. 어떤 알고리즘은 컴퓨터를 동원하더라도 수십년 혹은 수백만년이 걸릴 수 있다. 반면 동일한 문제를 푸는데, 하루 혹은 몇 시간이 걸리는 알고리즘을 만들 수도 있다. 아주 간단...

배열 회전

n개의 원소를 가진 배열을 k번 만큼 오른쪽으로 회전하라. 예를 들어 n=7, k=3 이라면, 배열 가 된>다.원본 배열과 동일한 크기의 배열을 만들어서, 순환된 결과를 복사한다. 공간복잡도 O(N), 시간복잡도 O(N)이다.버블소트를 응용해서 공간 복잡도를 O(1)로 줄일 수 있다.공간 복잡도는 O(1)이지만 시간 복잡도는 O(nk)다. 예제의 경우 시간...

Reverse Polish notation

역폴란드 표기법(Reverse Polish notation - RPN) 혹은 후위 표기법은 연산자(operator)를 연산대상(operands)의 뒤에 쓰는 연산 표기법이다. 예를 들어 "3 + 4"의 경우 "3 4 +"로 표기한다. 연산자가 두 개 이상이라면 연산자 바로 뒤에 다음번 연산대상을 표기한다. "3 - 4 + 5"가 있다면 "3 4 - 5 +"...

역폴란드 표기 수식 평가

를 따르는 수식을 평가하는 코드를 작성하라. 사용 할 수 있는 연산자는 +, -, , /이다. 연산대상으로는 int를 사용 할 수 있다.예제 -> ((2 + 1) 3) -> 9 -> (4 + (13 / 5)) -> 6역폴란드 표기법 자체가 스택에 최적화 돼 있다.코드를 단순화 하기 위해서 에러처리는 하지 않았다....

배열 뒤집기

n개의 원소를 가진 배열을 뒤집는다. n=7 때, 배열 로 회전하기 위한 몇 개의 방법이 있는가.아마도 가장 간단하게 생각 할 수 있는 방법일 것이다. 원본 배열과 같은 크기의 배열을 만들고, 원본 배열의 맨 뒤에서 부터 순환하면서 값을 복사한다. O(n) 공간과 O(n) 시간이 필요하다. O(1) 공간을 사용하는 방법을 찾아보자.O(1)이며 공간 복잡도는...