알고리즘/자료구조(Data Structure)
07 분할정복
시간복잡도:fastsum()과 recursivesum()이 종료하는 데 걸리는 시간은 함수 호출 횟수에 비례. 즉, recursivesum()은 n번의 함수호출fastsum()은 호출될때마다 최소한 두 번에 한 번 꼴로 n이 절반으로 줄어든다.따라서 두 값의 상한은 모두 logn이므로 O(logn)! 부적절한 경우) 절반으로 나누는 알고리즘이 큰 효율 저하 불러오는 이유:여러 번 중복되어 계산되면서 시간 소모 (=overlapping subproblems)(→ 이런 경우는 8장 동적계획법으로 해결) 대표적 예제) 병합 정렬 Merge SortMerge Sort (평균/최악:O(nlogn) 7.2 문제: 쿼드 트리 뒤집기(QUADTREE, 하)algospot.com :: QUADTREE쿼드 트리 뒤집기 문..
[자료구조] 비트마스크(BitMask) 알고리즘
비트마스크는 정수의 이진수 표현을 자료구조로 쓰는 기법이다. 이진수 즉, 0과 1만을 이용하므로 하나의 비트는 참/거짓을 의미한다. 시간 복잡도(수행시간)가 O(1)이라는 엄청난 장점이 있다. 공간 복잡도(메모리 사용량) 또한 적다. bit가 10개라면 2^10까지의 표현이 가능한 것이다. 그래서 DP같은 다이나믹 프로그래밍에 매우 적절하다. 논리회로 등을 공부해보신 분이라면 논리연산자들에 익숙할 것인데 비트마스크에서도 이러한 논리연산자들을 사용한다. 1. AND 연산 : & A와 B 둘다 참 ex) 1 & 1 => 1 2. OR 연산 : | A나 B 하나라도 참 ex) 0 & 1 =>1 3. XOR 연산 : ^ 둘 중 하나만 참 ex) 1 & 1 => 0 4. NOT 연산: ~ 참이면 거짓으로, 거짓이..