알고리즘
-
[알고리즘 개념] 해시 알고리즘알고리즘 공부 2020. 8. 28. 21:27
해시 함수 어떤 길이의 데이터를 입력해도 정해진 길이의 결과를 주는 함수 여기서 정해진 길이는 256 bits로 input의 길이에 관계없이 output의 길이는 일정하다. 해시 함수의 특징 - 데이터의 입력의 길이에 제한이 없다 - 결과는 정해진 256bits의 길이를 가진다 - 결과값이 중복될 가능성이 거의 없다 - 결과값을 가지고 입력값을 유추할 수 없다 해시 알고리즘 크기가 U인 테이블 T를 생성하고 key k를 slot h(k)에 저장하는 방식이다. 이때 key의 중복은 없어야 한다. key k가 slot h(k)로 해쉬 되었다고 하며 h(k)를 key k의 해쉬 값이라고 부르고, h()가 해쉬 함수이다. slot의 크기는 무한하지 않기 때문에 h(k)의 값이 중복되어 나타날 수 있다. 이 경우..
-
[알고리즘 개념] 동적계획법알고리즘 공부/알고리즘 개념 2020. 8. 22. 17:54
동적 계획법 영어로 하면 Dynamic Programming이다. 큰 문제를 작은 문제로 나누어 푸는 문제를 일컬어 동저계획법이라고 한다. 이 점에서 분할 정복과 비슷하지만, 가장 큰 차이점은 동적 계획법에서는 쪼개진 작은 문제가 중복되지만, 분할 정복은 절대로 중복될 수가 없다는 점이다. 따라서 동적 계획법은 작은 문제의 결과를 저장해둔다. 이미 계산한 값을 저장해 두는 메모리를 캐시라고 하며 같은 문제가 다시 등장하였을 때 이를 이용하여 문제 해결 속도를 향상할 수 있다. 조건 작은 문제의 반복이 일어나는 경우. 단, 이 작은 문제의 결과는 같아야 한다. 즉, 어떤 문제가 여러 개의 부분 문제로 쪼개어질 수 있어야 하며 이 부분 문제는 같은 부분 문제이거나 재귀 알고리즘을 통해 해결되어야 한다. 피보..