Search

'알고리즘/자료구조'에 해당되는 글 16건

  1. 2016.12.10 모듈러 나눗셈 연산 처리하기 (2)
  2. 2016.12.04 완전순열(교란순열)
  3. 2016.07.30 LCA(Lowest Common Ancestor)
  4. 2016.07.23 Count sort
  5. 2015.09.07 Segment Tree
  6. 2015.09.05 SQRT Decomposition
  7. 2015.08.27 LIS를 O(nlogn)시간 내에 해결하는 방법
  8. 2015.08.26 c++ priority_queue에서 comparator 선언해주는 방법
  9. 2015.07.07 인덱스 트리
  10. 2015.06.27 union find
  11. 2015.02.27 오일러회로
  12. 2015.02.27 트라이
  13. 2015.02.25 트립(Treap)
  14. 2015.02.24 접미사배열
  15. 2015.02.24 KMP 알고리즘
  16. 2015.02.21 BIT(Binary Indexed Tree)

모듈러 나눗셈 연산 처리하기

알고리즘/자료구조 2016.12.10 12:14 Posted by 아는 개발자

프로그래밍 문제에서 가끔 이런 연산을 요구하는 문제들이 있다.


(N/K) % MOD


N과 K의 값이 작으면 N과 K의 값을 먼저 계산 하고 나서 모듈러 연산을 취해주면 문제가 없다.


하지만 N과 K값이 64bit 이상으로 변수에 넣을 크기를 초과하는 경우 앞의 나눗셈 계산은 정상적인 값을 내놓지 않을 것이고 모듈러 연산은 정상이 아닌 값을 받아 처리해 결론적으로 잘못된 값을 낸다.


주로 N과 K를 팩토리얼로 받는 조합의 경우의 수를 구할 때 난감하다 -> nCr % MOD 인 경우


이런 경우를 해결 하기 위해 모듈러 연산의 나눗셈을 계산하는 특별한 방법이 존재한다.


모듈러 연산에서 나눗셈 N/K는 K로 나누는 대신에 K의 곱셈 역원(multiple inverse)를 곱하는 방식으로 이뤄진다. 곱셈 역원은 MOD(모듈러 연산으로 나누는 값)과 나누는 값 K가 서로소일때만 존재한다. 곱셈 역원을 구하는 방법은 다음과 같다.


modInv(K, MOD) = K^(MOD-2)%MOD


곱셈역원을 이용해 나눗셈을 다음과 같이 정리 할 수 있다.


(N/K) % MOD = (N * modInv(K, MOD-2))%MOD    (페르마의 소정리라고도 한다. 이해하긴 어려우니 일단 외우자)


하지만 여기서 MOD 값이 매우 크다면 (대부분 문제에서 1,000,000,007을 잡는다) K^(MOD-2) 까지 곱하는데 시간이 오래 소요될것이다. 그래서 이런 경우 최적화 할 방법도 같이 기억해두면 좋다.


1. 가장 간단한 방법은 지수의 제곱승을 이용하는 방법이다(이 테크닉의 정확한 이름을 모르겠다)


예를들어 A^5 을 구한다고 한다면, A를 다섯번 곱해 A*A*A*A*A 구하는 방법이 있지만 다른 방법은 A*(A^2)*(A^2) 로 구하는 방법도 있다. A^2를 한 번만 구하면 되므로 기존 방법보다 곱셈의 횟수를 줄일 수 있다. 시간 복잡도는 O(logMOD)이다.


코드는 이렇다

 
long long modInv(long long a, int M) {
	if (M == 1)
		return a;
	if (M == 0)
		return 1;

	long long  tmp = modInv(a, M / 2);
	if (M % 2)
		return (long long)((long long)((tmp*tmp) % MOD)*a) % MOD;
	else
		return (long long)(tmp*tmp) % MOD;
}


2. O(logMOD)말고 O(1)에 해결하는 방법도 있다고 한다. 이건 이 포스트를 참고하자. 나도 증명은 잘 모르겠다.


http://koosaga.myungwoo.kr/entry/%EC%9D%B4%ED%95%AD%EA%B3%84%EC%88%98-nCr-mod-p-%EA%B3%84%EC%82%B0%ED%95%98%EA%B8%B0


위 포스트 글을 코드로 옮기면 이렇다.

 
	for (int i = 2; i <= MAX; i++) {
		inv[i] = (-(MOD / i)*inv[MOD%i] + MOD)%MOD;
		if (inv[i] < 0)
			inv[i] += MOD;
		inc[i] = (inc[i - 1] * inv[i]) % MOD; // 팩토리얼 곱셈역원 계산
	}


모듈러 연산은 진짜 왠만하면 피하고 싶은 문제인데, 그래도 이번 기회에 테크닉이라도 배워 뒀으니 앞으로 자주 써먹어야겠다.

'알고리즘 > 자료구조' 카테고리의 다른 글

모듈러 나눗셈 연산 처리하기  (2) 2016.12.10
완전순열(교란순열)  (0) 2016.12.04
LCA(Lowest Common Ancestor)  (0) 2016.07.30
Count sort  (0) 2016.07.23
Segment Tree  (0) 2015.09.07
SQRT Decomposition  (0) 2015.09.05
  1. 깜장호랭 2017.10.07 22:33  댓글주소  수정/삭제  댓글쓰기

    좋은 설명 감사합니다. O(1)방법에서 inv[1] = 1; 이 꼭 있어야 하네요. 쉽게 찾을 수 있는 것이지만, 코드에서 빠져 있어서요.

완전순열(교란순열)

알고리즘/자료구조 2016.12.04 20:52 Posted by 아는 개발자

어떤 배열의 원소 Xi의 위치가 i라고 할 때 모든 원소들이 자기의 위치에 존재하지 않을 때 이를 완전 순열이라고 한다.


 X2

X1 

X4 

X3 


점화식을 통해 원소의 개수에 따라 완전순열의 개수를 구할 수 있다.


공식은 다음과 같다


a(n) = (n-1) * (a(n-1) + a(n-2))


증명을 하면,


1 부터 N까지 오름 차순으로 이뤄진 배열이 있다고 하자 여기서 배열내의 원소중 1의 위치를 X로 옮기려고 한다. 이럴 경우 두가지 경우가 발생한다.


- X를 1의 위치로 옮기는 경우 -> N-2의 개수로 완전순열을 구하는 경우와 같다.

- X를 1의 위치로 옮기지 않는 경우 -> N-1의 개수로 완전순열을 구하는 경우와 같다.


1이 선택 할 수 있는 X 의 개수는 N-1개 이므로 이를 점화식으로 나타내면 위와 동일하게


a(N) = (N-1) * (a(N-1) + a(N-2)) 가 나온다.


위의 경우처럼 단순히 원소들이 자기의 위치에 존재하지 않는 경우만 생각하면 별 쓰임이 없을 것 같은데,

여러 원소들을 분산해서 써야하는 경우를 생각하면 쓸데가 있다.

(결론은 기억은 해두자)

'알고리즘 > 자료구조' 카테고리의 다른 글

모듈러 나눗셈 연산 처리하기  (2) 2016.12.10
완전순열(교란순열)  (0) 2016.12.04
LCA(Lowest Common Ancestor)  (0) 2016.07.30
Count sort  (0) 2016.07.23
Segment Tree  (0) 2015.09.07
SQRT Decomposition  (0) 2015.09.05

LCA(Lowest Common Ancestor)

알고리즘/자료구조 2016.07.30 13:24 Posted by 아는 개발자

트리 내부에 있는 두개의 노드 사이의 최저 공통 조상을 효율적으로 찾아주는 자료구조이다.


가장 간단히 생각 할 수 있는 구현방법(모든 모드를 일일히 탐색하는)으로는 최저 공통 조상을 찾는데 O(N)의 시간이 걸리지만


최적화된 LCA 알고리즘으로는 O(logN)시간만에 구할 수 있다.


LCA 알고리즘에서 트리의 노드들은 자신의 부모노드에 대한 정보외에 현재 높이에서 2^i 위에 위치한 조상노드에 대한 정보도 가지고 있다.

그림으로 표현하면 다음과 같다.


(자신의 부모노드 뿐만 아니라 2^i위치에 해당하는 조상노드의 정보를 가지는 것은 빠른 탐색을 할 때 유용하게 쓰인다.)


알고리즘의 절차는 다음과 같다.


1. 두 노드의 depth가 다르다면 depth를 맞춰준다.

* 이때 일일히 모든 부모노드를 방문하는 것이 아니라, 2^i에 대한 높이의 정보를 이용하면 신속하게 동일한 depth를 가지는 곳으로 이동 할 수 있다.

코드는 다음과 같다.



2. 가장 높은 조상부터 찾도록 하고 두 노드간의 공통조상이 다른 경우에는 그 위치부터 다시 조상을 찾도록 한다.



두 노드가 동일하거나, 두 노드의 공통조상이 모두 동일하다면 가장 낮은 조상을 return한다.


여기서 왜 공통조상이 아닐 때 재귀함수를 부르는지 이해가 가지 않았었다. 그래서 아예 가장 낮은 높이부터 조상들을 비교해 동일한 조상이 나오면 return하도록 했는데 이런경우 문제점은 공통 조상은 찾아주는데 최저 공통조상은 찾아줄 수 없다(높이 자체가 2의 지수 형태로 되어 있기 때문). 이때 찾는 공통 조상은 현재 위치에서 2의 지수 높이에 있는 공통 조상중 가장 낮은 위치에 있는 공통조상을 찾아주게된다.


동일한 level을 맞춰주기 위해 2^i의 형태로 이동했던 것 처럼 위 경우에도 가장 낮은 부분 부터 하나씩 올라가야 한다.


LCA 알고리즘의 가장 키 포인트는


2의 지수승에 해당하는 자료구조를 만들 때 최적화 효과를 볼 수 있다는것.


이런 아이디어는 LCA뿐만 아니라 다른 형태의 문제를 풀 때도 유용하게 사용 할 수 있을 것 같다.

'알고리즘 > 자료구조' 카테고리의 다른 글

모듈러 나눗셈 연산 처리하기  (2) 2016.12.10
완전순열(교란순열)  (0) 2016.12.04
LCA(Lowest Common Ancestor)  (0) 2016.07.30
Count sort  (0) 2016.07.23
Segment Tree  (0) 2015.09.07
SQRT Decomposition  (0) 2015.09.05

Count sort

알고리즘/자료구조 2016.07.23 19:47 Posted by 아는 개발자

quicksort나 mergesort처럼 일반적인 sorting알고리즘은 O(NlogN)을 가지나 sorting에 사용되는 값들을 사전에 알고 있는 경우에는 시간복잡도를 O(N)까지 단축 시킬 수 있다. 그중에서도 가장 강력하게 사용되는 알고리즘이 Count sorting이다.


Count sorting은 정렬에 쓰이는 값이 충분히 작은 경우(배열의 최대 크기가 될 수 있는 값보다 작아야 한다)에 주로 사용할 수 있다. 배열의 인덱스는 이미 자동적으로 정렬되있으니 수열에 포함된 값 각각의 개수를 배열의 인덱스에 해당하는 값에 저장해둔 후 그 그 개수를 참고해서 정렬하는 방식이다.


글로 설명하기에는 어려우니 예를 들어보자. 


5 3 6 7 4 5 인 수열을 정렬한다고 하자. 위 수열의 각 값의 개수를 관리하는 배열을 count[10]라 하자. 그러면 count의 값은 다음과 같을 것이다.


count[0] = 0

count[1] = 0

count[2] = 0

count[3] = 1

count[4] = 1

count[5] = 2

count[6] = 1

count[7] = 1

count[8] = 0

count[9] = 0


정렬하고자한 수열의 값들은 이미 배열의 index를 통해서 자동적으로 정렬이 되었다. 이제 각각의 개수만큼 표현만 해주면 된다.


count[0] = 0 -> 수열에 포함 안됨

count[1] = 0 -> 수열에 포함 안됨

count[2] = 0 -> 수열에 포함 안됨

count[3] = 1 -> 3

count[4] = 1 -> 3, 4

count[5] = 2 -> 3, 4, 5, 5

count[6] = 1 -> 3, 4, 5, 5, 6

count[7] = 1 -> 3, 4, 5, 5, 6, 7

count[8] = 0 -> 수열에 포함 안됨

count[9] = 0 -> 수열에 포함 안됨


생각해보면 정말 자명하고 직관적이어서 쉽다. 구현도 쉬워서 자주자주 써먹을 수 있을 것 같으나 써야할 때를 자주 깜빡한다.


가장 최근에 푼 문제중에는 좌표상에 표현되는 값을 x, y로 정렬해야 했는데 조건이 x, y < 1000000이었다. 이때도 count sort를 사용해서 정렬 할 수 있었는데 구현도 어려운 quicksort를 구현하느라 시간을 한참 소비했다 ㅡㅡ


다른분이 정렬한 코드를 참고해서 새롭게 작성한 후 올린다..




'알고리즘 > 자료구조' 카테고리의 다른 글

완전순열(교란순열)  (0) 2016.12.04
LCA(Lowest Common Ancestor)  (0) 2016.07.30
Count sort  (0) 2016.07.23
Segment Tree  (0) 2015.09.07
SQRT Decomposition  (0) 2015.09.05
LIS를 O(nlogn)시간 내에 해결하는 방법  (0) 2015.08.27

Segment Tree

알고리즘/자료구조 2015.09.07 16:34 Posted by 아는 개발자

옛날에 min max Tree를 공부 할 때 배열 특정 구간 내에서의 최대값과 최소값을 미리 저장해두어 범위가 주어 질 때 O(logN)시간내에 해결 했었는데 이렇게 구간 내의 특정 값을 저장해두는 방식을 Segment Tree라고 하나 보다.



범위가 주어지면 위 배열을 이용해서 해결하면 된다. 만약 3~6사이의 범위에 대해 구하라고 하면


이렇게 풀면 된다.


사실 이건 생각하는 것은 책 한번 보면 어렵지 않은데 이걸 어떻게 구현 할 것인가가 문제이다. 예전에는 이차원 배열 사용하며 메모리 낭비도 심하고 코드도 지저분하게 풀었는데 코드포스에 깔끔한 구현이 있어 참조해본다




펜윅트리와는 다르게 Segment 트리는 구간의 최대값과 최소값 또한 저장 할 수 있고 갱신도 용이하다. 앞으로 자주 사용해야겠다.


'알고리즘 > 자료구조' 카테고리의 다른 글

LCA(Lowest Common Ancestor)  (0) 2016.07.30
Count sort  (0) 2016.07.23
Segment Tree  (0) 2015.09.07
SQRT Decomposition  (0) 2015.09.05
LIS를 O(nlogn)시간 내에 해결하는 방법  (0) 2015.08.27
c++ priority_queue에서 comparator 선언해주는 방법  (0) 2015.08.26

SQRT Decomposition

알고리즘/자료구조 2015.09.05 20:39 Posted by 아는 개발자

만약 알고리즘 문제에서 해당 배열의 특정 구간(L, R)에서 최소값을 구하라는 문제가 나왔다면 가장 일반적으로 생각 할 수 있는 방법은 L, R 구간을 모두 탐색해보는 방법일 것이다.


하지만 테스트 케이스의 개수가 많고 배열의 크기가 크다면 시간이 오래 걸릴 것이다. 여기서 사용 할 수 있는 방법이 sqrt decomposition이다.




크기 N인 배열을 sqrt(N)으로 쪼개서 최소값을 저장하는 배열(sqrt 배열)을 미리 만들어 둔 후


주어진 구간의 최소값 찾을 때는 구간 내에 포함된 sqrt배열에 해당하는 최소값과 그 이외의 부분들의 값을 비교해서 해결 할 수 있다


현재는 최소값을 구하는데 사용했는데 이것 말고도 다양한 정보를 저장하는데 사용 할 수 있을 것 같다

'알고리즘 > 자료구조' 카테고리의 다른 글

Count sort  (0) 2016.07.23
Segment Tree  (0) 2015.09.07
SQRT Decomposition  (0) 2015.09.05
LIS를 O(nlogn)시간 내에 해결하는 방법  (0) 2015.08.27
c++ priority_queue에서 comparator 선언해주는 방법  (0) 2015.08.26
인덱스 트리  (0) 2015.07.07

LIS는 수열 중에서 가장 긴 수열의 길이를 찾는 방법이다.


동적 계획법 해결 방법은 이전에 찾았던 수열의 마지막 값들 중 현재의 위치의 값보다 작으면 그 마지막 값이 가지고 있는 수열의 길이에 1을 더하는 방식이다. 조건에 해당하는 수열 중에서 가장 긴 수열을 선택해야 한다.


기존의 방법은 긴 수열을 찾는데 O(N)의 시간이 걸려 모든 배열의 값을 탐색한 후에는 전체 알고리즘 복잡도는 O(N^2)가 되었다 


하지만 길이 L 인 수열의 마지막 값들 중 최소 값을 저장하는 배열을 둔다고 생각해보자 C[L]


C[]배열은 순 증가하는 그래프가 될 것이다. 

(간단히 설명하자면 C[N]은 C[N-1]의 영향을 받을 것이고 C[N-1]은 현재 길이에서 최소의 값을 가지기 때문에...귀납적으로 설명하면 그렇다. 직감적으로도 그러하고)


만약 나의 현재 위치의 값이 S라면 C[]에서 이분 탐색을 하고 index값을 통해 위치를 반환 할 수 있을 것이다.


출처 - 알고리즘 문제해결 전략

'알고리즘 > 자료구조' 카테고리의 다른 글

Segment Tree  (0) 2015.09.07
SQRT Decomposition  (0) 2015.09.05
LIS를 O(nlogn)시간 내에 해결하는 방법  (0) 2015.08.27
c++ priority_queue에서 comparator 선언해주는 방법  (0) 2015.08.26
인덱스 트리  (0) 2015.07.07
union find  (0) 2015.06.27


위의 Prove class는 내가 문제를 풀기 위해 임의로 만든 것이기 떄문에 무시해도 된다.
만약 int인 priorityqueue를 만들고 싶다면

priority_queue<int, vector<int>, mycomparison>
으로 선언하면 된다.

여기서 세가지 인자가 들어가는데 하나는 자료형, 자료형을 저장하는 자료구조, 그리고 비교연산이다

자료구조는 별일 없으면 vector로 선언하면 된다.
mycomparison이 비교 연산을 하는 것인데 이건 class로 선언해줘야 한다.

algorithm 라이프러리에 sort를 해결할 때는 일반 함수처럼 선언해서 해결하면 되었었는데 priority_queue는 그렇지 않았다

그리고 여기서 heap을 어떤 순서로 나열하느냐는 일반적인 compare와 다르다

sort에서는 오름 차순으로 하려면

compare(int a, int b) return a < b;

이렇게 했는데 priority_queue에서는

compare(int a, int b) return a > b;
로 해주어야 한다.

heap만의 특성이라 그런가 보다


'알고리즘 > 자료구조' 카테고리의 다른 글

SQRT Decomposition  (0) 2015.09.05
LIS를 O(nlogn)시간 내에 해결하는 방법  (0) 2015.08.27
c++ priority_queue에서 comparator 선언해주는 방법  (0) 2015.08.26
인덱스 트리  (0) 2015.07.07
union find  (0) 2015.06.27
오일러회로  (0) 2015.02.27

인덱스 트리

알고리즘/자료구조 2015.07.07 18:05 Posted by 아는 개발자

일정 데이터 집합에 대하여 구간별로 특정한 데이터를 저장해둔 것을 인덱스 트리라 한다. 


특정 값은 주로 최대값이나 최소값을 의미한다. 위 자료구조를 통해 주로 Min Max Tree를 만든다. 만드는데 시간이 상당히 오래 걸리며 한 번에 깔끔히 완성하는 것은 상당히 어렵다.


BIT에서 해결하지 못했던 최대 최소 문제를 해결해줄 수 있는 알고리즘이긴 하지만... 구현하는데 시간이 오래걸리는 것은 아쉽다.



'알고리즘 > 자료구조' 카테고리의 다른 글

LIS를 O(nlogn)시간 내에 해결하는 방법  (0) 2015.08.27
c++ priority_queue에서 comparator 선언해주는 방법  (0) 2015.08.26
인덱스 트리  (0) 2015.07.07
union find  (0) 2015.06.27
오일러회로  (0) 2015.02.27
트라이  (0) 2015.02.27

union find

알고리즘/자료구조 2015.06.27 11:04 Posted by 아는 개발자

알고리즘 문제를 풀다 보면 노드들 간의 집합이 존재하는 경우가 있다.


이때 해야할 일이 크게 두 가지 있다.

1. 두 노드가 같은 집합에 포함되어 있는지, 다른 집합에 있는지 확인하는 작업

2. 두 집합을 병합하는 작업



사람마다 위 과정을 처리하는 방법이 모두 다르고 시간복잡도도 다르다.

나 또한 무식하게 문제를 풀때는 O(n^2)이렇게 풀기도 했다. 


하지만 위 작업을 최적화한 자료구조로 union find가 있다.

(양교수님께서 알려주신 내용인데 당시에는 학점받기에 급급해 제대로 공부하지 못했다.)


그림파일 올리려고 했는데 귀찮아서 못올리겠다

http://blog.secmem.org/521

좋은 블로그가 있으니 여기를 참고하길..





'알고리즘 > 자료구조' 카테고리의 다른 글

c++ priority_queue에서 comparator 선언해주는 방법  (0) 2015.08.26
인덱스 트리  (0) 2015.07.07
union find  (0) 2015.06.27
오일러회로  (0) 2015.02.27
트라이  (0) 2015.02.27
트립(Treap)  (0) 2015.02.25

오일러회로

알고리즘/자료구조 2015.02.27 15:21 Posted by 아는 개발자

오일러 회로는 그래프의 모든 간선을 방문하고 시작점과 끝점이 같은 회로를 말한다. 우리에게는 연필로 모든 간선을 칠하고 다시 돌아오는 것으로 친숙하다. 별표그릴때를 생각해보면.


이 회로를 만들기 위한 조건은 각 정점들마다 나가고 들어오는 간선의 수가 같아야 한다(무방향의 그래프는 정점과 연결된 간선의 수가 짝수개여야 한다) 


정말 간단히 생각하면 된다. 


어떤 정점의 나가는 간선의 수가 들어오는 간선의 수보다 적다면 그 정점으로 들어오는 간선들은 아직 방문하지 못한채 그 정점에서 나가지 못하게 된다. 

위의 그림에서 정점은 2개의 나가는 간선과 3개의 들어오는 간선이 있다. 검은색 간선은 이미 방문 한 것이고 파란색 간선은 아직 방문하지 않는 것이다. 현재 위치는 정점 3인데 여기서 더이상 어느 곳으로 나갈 수 없다. 나가지 못하므로 다시 3으로 들어오는 간선을 방문 할수도 없다


만약 더이상 방문할 간선이 없다면 오일러 회로가 성립한 것이나 파란색 간선이 남아있으므로 오일러 회로를 만들 수 없다.


위와 같은 정점이 그래프에 하나라도 있으면 오일러 회로는 만들수가 없다


모든 정점이 나가고 들어오는 간선의 수가 같아야만 오일러 회로가 성립하게 된다.


회로 존재의 유무를 찾는것은 쉬운데 회로를 찾는것은 조금 난감하다.

저자는 재귀함수를 이용해서 간단히 풀어버렸는데.. 나는 재귀함수 호출순서가 뭔가 문제가 있지 않을까 생각한다.... 물론 내가 틀렸을것 같은데... 이런게 아무래도 실력인가;


'알고리즘 > 자료구조' 카테고리의 다른 글

인덱스 트리  (0) 2015.07.07
union find  (0) 2015.06.27
오일러회로  (0) 2015.02.27
트라이  (0) 2015.02.27
트립(Treap)  (0) 2015.02.25
접미사배열  (0) 2015.02.24

트라이

알고리즘/자료구조 2015.02.27 14:35 Posted by 아는 개발자

요즘 운영체제에서는 단어 몇글자만 치면 자동완성 기능을 제공하는데

자동완성의 기본 알고리즘이 바로 트라이다.


자동완성을 만들려면 사전에 입력한 단어들을 저장하고 빠른시간안에 탐색 할 수 있어야 한다. 하지만 문자열은 숫자로 이루어진 이진트리와 달리 원소 비교를 상수시간 내에 할 수 없으므로 특화된 자료구조가 필요하다. 이때 유용한 자료구조가 트라이다.


구조는 다음과 같다.


만약 내가 TR, THE, TRY, TREE라는 단어를 저장해두었다고 하자. 그러면 다음과 같은 트리가 형성된다. 각각의 단어의 공통된 접두사를 부모로 두는 방법이다. 하지만 공통된 접두사가 내가 입력한 단어가 아니라면 bool 값을 이용해서 표현해야한다. 그림에는 하얀색 바탕으로 표현했다. 위 자료구조의 시간 복잡도는 트리의 높이로 볼수 있고 트리의 높이는 단어의 최대 길이와 같으므로 O(L)로 정의 할 수 있겠다.


예를들어 내가 TRY라는 문자가 있는 지 확인하고 싶다면 첫 문자 T로 비교를 한 후 존재하면 R을 비교, 그 후에는 Y를 비교해서 내가 찾으려 하는 노드가 존재하는지, 그리고 존재하면 사전에 입력된 단어인지를 확인하면 된다.


위 자료구조의 단점은 메모리를 너무 많이 잡아먹는다는 것이다. 나는 지금 TR, THE, TRY, TREE 이렇게 네개만 입력했는데 벌써 6개의 node가 필요하니 단어의 개수가 늘어나면 추가 메모리가 더 많이 필요할 것이다.


문자열에 특화된 자료구조는 이번이 처음이다. 자주 써먹어야겠다.

'알고리즘 > 자료구조' 카테고리의 다른 글

union find  (0) 2015.06.27
오일러회로  (0) 2015.02.27
트라이  (0) 2015.02.27
트립(Treap)  (0) 2015.02.25
접미사배열  (0) 2015.02.24
KMP 알고리즘  (0) 2015.02.24

트립(Treap)

알고리즘/자료구조 2015.02.25 11:19 Posted by 아는 개발자

이름에서도 예측 할 수 있듯이 트립(Treap)은 Tree + Heap인 자료구조이다.


기존 이진 트리는 어떻게 내가 삽입(insert)하느냐에 따라서 트리의 높이가 O(N)이 될 수 있고 O(logN)이 될수도 있는 문제점이 있다. 트리구조의 기본적인 목표는 최대한 높이를 낮추어 탐색의 시간을 빠르게 하는 것이 목적인데 높이가 O(N)되면 선형 구조와 다를바가 없어진다. 즉 균형의 문제가 발생한다.


균형의 문제를 해결하기위한 자료구조로는 AVL Tree와 Red Black Tree가 있는데 이것들은 구현하기가 어렵다. 그래서 간단히 Heap의 성질을 이용해서 구현한것이 Treap이다. 방법은 다음과 같다.


1. 삽입할 노드들에게 난수값으로 우선순위를 부여한다.

2. 노드가 어떤 subtree의 루트가 될지의 기준은 우선순위이다.

3. 노드가 어떤 node의 우선순위보다 작으면 자식이 된다.

4. 이때 왼쪽 자식이 될지 오른쪽 자식이 될지는 부모의 value값과 자식의 value값을 비교해서 이루어진다.


value값으로 tree의 높이를 결정하는 것이 아니라 특정 난수들로 tree의 높이를 결정한다. 물론 난수값이 내림차순으로 결정되면 Treap자료구조도 O(N)이 될수도 있다. 하지만 위 확률은 매우 적어서 신경쓰지 않아도 된다. 


삽입하고 삭제하고 합치는게 좀 까다로울 수 있다.


'알고리즘 > 자료구조' 카테고리의 다른 글

오일러회로  (0) 2015.02.27
트라이  (0) 2015.02.27
트립(Treap)  (0) 2015.02.25
접미사배열  (0) 2015.02.24
KMP 알고리즘  (0) 2015.02.24
BIT(Binary Indexed Tree)  (0) 2015.02.21

접미사배열

알고리즘/자료구조 2015.02.24 21:23 Posted by 아는 개발자

문자열로 나오는 문제들은 접미사 배열을 이용해 어려운 문제들도 간단히 해결이 가능하다.

접미사 배열은 말 그대로 어떤 문자들의 접미사들을 모아놓은 묶음이다.

예를 들면 


Algorithm이면 접미사들로는

m, hm, thm, ithm, rithm, orithm, gorithm, lgorithm, Algorithm,이 있을 건데

이것들을 사전 순데로 정리해서


Algorithm

gorithm

hm

ithm

m

orithm

rithm

으로 나타낸 것이다.


어떤 점에서 유용하냐 그냥 정렬만 해두었으면서 라 할수도 있다


하지만 이게 사전순으로 정리되어 있다는 점을 주목할 필요가 있다.

우리가 어떤 문자열을 찾는다면

처음부터 모두 뒤져보는 원시적인 방법을 써야하지만 O(N*N)


위 처럼 정리해두면 O(N*logN)이 걸린다.


단순하면서도 나중에 써먹을 곳이 많은 자료구조이다.


'알고리즘 > 자료구조' 카테고리의 다른 글

오일러회로  (0) 2015.02.27
트라이  (0) 2015.02.27
트립(Treap)  (0) 2015.02.25
접미사배열  (0) 2015.02.24
KMP 알고리즘  (0) 2015.02.24
BIT(Binary Indexed Tree)  (0) 2015.02.21

KMP 알고리즘

알고리즘/자료구조 2015.02.24 18:38 Posted by 아는 개발자

예전에 KMP는 왜 KMP인가라는 문제를 보고 KMP이거 뭐지 장난하는건가 싶었는데;

문자열에 관한 알고리즘인걸 책을 보고 깨달았다.. 이렇게 심오하고 환상적인 알고리즘이 있었다니 ㄷㄷ


KMP알고리즘은 어떤 문자에서 특정 문자열이 존재하는지 확인하는 방법이다.

예를 들어 길이가 N인 문자열에서 M이라는 문자열이 있는지 없는지 확인하고 싶으면

N의 모든 위치에서 M의 시작문자와 비교해보는 방법이 있다. 이 방법은 O(MN)이 든다.


하지만 KMP알고리즘은 모두 비교하지 않고 접두사 접미사의 개념을 활용해서 푼다.


예를들어


abcabce -> 문자열 M

abcabcabcd -> 문자열 N


위의 M과 N을 비교했더니 abcabcabc까지는 같고 뒤에부터 달랐다.

그런데 다음 비교를 N의 두번째 문자열 부터 시작 하지 말고

abcabcabc의 접미사와 접두사가 같은 부분은 잘라서 하자는 것이다.

여기서 접두사 접미사가 같은 부분은 abc이다 따라서 N의 네번째 문자부터 탐색을 시작하면 효율적이다.


abcabcabcd

    abcabce

굵은a 부터 시작하라는것 왜냐면 앞에 있는 것들은 같은걸 아니까 따로 자료 구조를 만들어서 정리했으므로


문자열 N에 대하여 는 다음과 같은 자료 구조를 만들어야 한다


longestprefixsuffix[length];


length는 처음부터 length까지의 문자열 길이를 말하고

그 길이 까지 접미사와 접두사가 같은 부분의 최대 길이를 말한다.


구현은 다음과 같다.


#include<iostream>

#include<string>


using namespace std;



int p[1000];

int main()

{

string s;

cin>>s;


int begin=1, matched=0;


while(begin + matched < s.length())

{

if(s[begin + matched] == s[matched])

{

matched++;

p[begin + matched - 1] = matched;

}

else

{

if(matched == 0)

begin++;

else

{

begin += matched - p[matched-1];

matched = p[matched-1];

}

}

}


return 0;


}


접미사, 접두사 라는 개념을 사용하는건 이해가 가는데

이거를 깔끔하게 만드는 과정은 이해하기 어렵다.

'알고리즘 > 자료구조' 카테고리의 다른 글

오일러회로  (0) 2015.02.27
트라이  (0) 2015.02.27
트립(Treap)  (0) 2015.02.25
접미사배열  (0) 2015.02.24
KMP 알고리즘  (0) 2015.02.24
BIT(Binary Indexed Tree)  (0) 2015.02.21

BIT(Binary Indexed Tree)

알고리즘/자료구조 2015.02.21 21:56 Posted by 아는 개발자

어려운거 많이 가르치기로 소문난 양교수님께서 왜 BIT를 설명 안해주셨을까

이렇게 감탄스러운 자료구조가 있는 줄 몰랐다.

RB Tree, AVL, 24 Tree이런거는 구현이 어려운데

이거는 구현도 어렵지 않고 편리하다


간단히 소개를 하면

기본적으로 어떤 data를 추가 할 때 O(1) 

그리고 그 data의 총 합을 구할 때는 O(n)이 걸린다.


하지만 BIT는 추가 할때도 O(logn) 총 합을 구할 떄도 O(logn) 시간이 걸리는

신기한 자료구조이다.


http://183.106.113.109/30stair/bindexedtree/bindexedtree.php?pname=bindexedtree

개념 설명이 내가 너무너무 부족하니 여기 있는 글을 통해서 이해하길...


나는 이것을 어떻게 응용할 것인지를 생각해보면...

위 사이트에서도 이미 응용 했지만


부분 합을 구하는 자료 구조 뿐만 아니라

부분 최소 값을 구하는 자료 구조로도 이용 할 수 있지 않을까 한다.


1차원을 사용하면 원래 값들을 모두 잃어버리겠지만

만약 내가 최소값을 찾길 원한다면 모두 다 돌아다니지 않아도 O(logn)시간에 찾을 수 있으니

효율적이다. 


LIS에서도 이 방법을 적용 할 수 있다고 하니

응용할 수 있는 방법이 무궁무진한 자료구조이다.




#include<iostream>

using namespace std;


int tree[20];

#define MaxVal 16

int read(int idx)

{

int sum = 0;

while(idx > 0){

sum += tree[idx];

idx -= (idx & -idx);

}


return sum;

}


void update(int idx, int val)

{

while(idx <= MaxVal)

{

tree[idx] += val;

idx += (idx & -idx);

}

}


int main()

{

for(int i = 1; i <= 16; i++)

update(i, i);


for(int i = 1; i <= 16; i++)

cout<<tree[i]<<endl;

return 0;

}


'알고리즘 > 자료구조' 카테고리의 다른 글

오일러회로  (0) 2015.02.27
트라이  (0) 2015.02.27
트립(Treap)  (0) 2015.02.25
접미사배열  (0) 2015.02.24
KMP 알고리즘  (0) 2015.02.24
BIT(Binary Indexed Tree)  (0) 2015.02.21