빠에야는 개발중

해싱 해싱 어떤 데이터를 작은 크기의 데이터로 변환하여 테이블에 담는 데이터 관리 기법이다. 해싱을 사용하면 데이터를 빠른 속도로 검색할 수 있다는 장점이 있다. 그리고 이 해싱은 암호화, 복호화의 개념과 만나 전자서명에도 사용이 된다. 해시 함수 해싱을 하는 방법은 다양하게 존재한다. 임의로 어떤 데이터를 변환 하겠다고 정했다면 그 방법이 바로 해시 함수가 되는 것이다. 예를 들어 “문자를 한칸씩 뒤로 옮기는 변환”이라는 해시 함수를 생각했다면, “ABC”라는 문자는 “BCD”가 되는 것이다.(예시에 불과하며, 속도적 이득은 거의 없다고 볼 수 있다.) 해시 함수는 보통 원문을 단방향으로 해싱하는 용도로 쓰이며 역방향으로 원문을 알아내는 방법은 계산상 불가능해야 좋은 해시 함수라고 할 수 있다. 충돌 ..

다이나믹 프로그래밍은 “큰 문제를 작은 문제로 나누어 푸는 알고리즘”이다. 하지만 단순히 나누는 것이 다가 아니라, 두가지 조건을 만족해야만 다이나믹 프로그래밍으로 문제를 푼다고 할 수 있는데, 그 두가지는 Overlapping subproblem (겹치는 부분 문제) Optimal substructure (최적 부분 구조) 이다. Overlapping subproblem 겹치는 부분 문제란, “큰 문제를 작은 문제로 쪼갤 수” 있어야 하고, “큰 문제와 작은 문제를 같은 방법으로 풀 수” 있어야 한다는 것이다. 피보나치 수를 예로 들자면 f(0) = 0 f(1) = 1 f(n) = f(n-1) + f(n-2) 이런 식에서 f(n)을 구하는 문제는 다시 f(n-1)을 구하는 문제와 f(n-2)를 구하는 ..

이진 탐색은 분할 정복의 기본이라고 할 수 있다. 개념은 알고 있었는데 직접 코드로 짜본 적이 있었나 싶어서 짚고 넘어간다. 원리 간단하게 말하면 "반으로 쪼개기"이다. head에서 tail까지 범위의 배열의 가운데 인덱스인 mid를 정해서 그 수와 찾고자 하는 수를 비교한다. 그래서 "찾는수 가운데 수"이면 탐색 범위를 [mid+1 ~ tail]로 쪼개서 탐색하는 것이다. 이 방식은 O(logn)의 시간 복잡도를 가져 선형 탐색보다 빠르다. 바로 구현에 들어가보자.123456789101112131415161718192021222324252627public class BinarySearch { public st..