IT 내맘대로 끄적끄적

[알고리즘] 선형검색(Linear Search)와 이진 검색(Binary Search) 선형 검색(Linear Search) 다른이름으로 순차 검색(Sequential Search)이라고도 하는 선형검색에 대하여 먼저 알아보겠습니다. 선형 검색은 데이터가 모인 집합(배열, 링크드리스트 등)의 처음부터 끝까지 하나씩 순서대로 비교하며 원하는 값을 찾아내는 알고리즘입니다. 데이터를  정렬하거나 따로 건드릴 필요가 없고, 난이도가 쉬운 편이나, 데이터의 양이 많아지면 검색에 소요되는 시간도 비례하여 많아지고, 하나씩 일일이 비교하기 때문에 비효율적이라는 단점이 있습니다. 예를 들어 위와 같은 데이터의 집합이 있을 경우 4를 찾으려면 10번의 비교를 거쳐야 합니다. 100만개의 데이터가 있고 찾고자 하는 데이터가 100만번째에 있다면 100만번의 비교를 해야 한다는 뜻 입니다. 이와 같은 상황을 Worst Case라고 합니다. 관련된 용어로 평균적인 상황을 Average Case 좋은 상황을 Best Case라고 합니다. 이진 검색(Binary Search) 이진검색은 다른말로 이분검색이라고도 합니다. 반으로 나누어서 연산하기 때문이죠. 선형검색의 경우 데이터 집합의 처음에서 시작하여 끝까지 탐색하는 알고리즘이지만 이진검색은 중간값부터 탐색을 합니다. 선형검색은 링크드리스트에서 자주 쓰이는 반면에 이진검색은 트리구조에서 자주 쓰이는 형식입니다. 이진검색은 데이터를 계속 반으로 나누면서 연산하기 때문에 처리속도가 매우 빠르다는 장점을 가지고 있습니다. 그러나 이진검색을 하기 위해서 데이터의 집합이 반드시 정렬(Sort)되어야 한다는 단점이 있습니다. 이렇게 이야기하면 얼마나 빠른지 감이 잘 안올텐데, 예를 들어 70억명의 사람중 한 사람을 찾으려고 한다면, 선형검색은 Worst Case의 경우 70억번, 대략적으로 생각해도 35억번은 비교연산을 해야 하는데, 이진 검색은 최대 33번의 비교만으로도 원하는 데이터를 찾...

[알고리즘] 해싱테이블, 해싱함수 해싱 해싱은 Hash Table이라는 기억공간을 할당하고  해시 함수라는 기억공간을 할당하고 해시 함수를 이용하여 레코드 키에 대한 Hash Table내의 Home Address를 계산 한 후 주어진 레코드를 해당 기억장소에 저장하거나 검색 작업을 수행하는 방식 해싱은 DAM(직접 접근)파일 을 구성할 때 사용되며, 접근 속도는 빠르나 기억공간이 많이 요구된다. 다른 방식에 비해 검색 속도가 가장 빠르다 . 삽입 삭제 작업의 빈도가 많을 때 유리한 방식 이다. 키-주소 변환 방법이라고도 한다. 해시테이블(HashTable) 해시테이블은 레코드를 한개 이상 보관할 수 있는 Bucket들로 구성된 기억공간으로 보조기억장치에 구성할 수도 있고 주기억장치에 구성할 수도 있다. 버킷(Bucket) 하나의 주소를 갖는 파일의 한 구역을 의미하며, 버킷의 크기는 같은 주소에 포함될 수 있는 레코드 수를 의미한다. 슬롯(Slot) 한 개의 레코드를 저장할 수 있는 공간으로 n개의 슬롯이 모여 하나의 버킷을 형성한다. Collision(충돌현상)  서로 다른 두개이상의 레코드가 같은 주소를 갖는 현상이다. Synonym 충돌로 인해 같은 Home Address를 갖는 레코드들의 집합이다. Overflow 계산된 Home Address의 Bucket내에 저장할 기억공간이 없는 상태로, Bucket을 구성하는 Slot이 여러개일때 Collision은 발생해도 Overflow는 발생하지 않을 수 있다. Overflow처리 방법 개방주소법 : 선형방법. collision 발생시 순차적으로 그 다음 빈 버킷을 찾아 저장함(새로운 공간을 할당) 폐쇄주소법 : overflow된 레코드들을 별도의 overflow영역에 저장하고 chain(pointer)으로 홈 버킷에 연결하는 방법(주어진 해시 테이블 안에서) 재해싱 : collision 발생 시 새...

[알고리즘] DAG란? DAG(Directed Acyclic Graph)  직역하면, "방향성 비 사이클" 그래프(루프를 생성하지 않는 그래프) 루프(사이클) : 자기 자신에서 출발해서 다시 자기 자신에게 돌아오는 경로 3세대 블록체인이라고도 불림 순환 그래프가 아닌 비 순환 그래프   즉, 순환하는 싸이클이 존재하지 않고, 일방향성만 가짐 비가역적 일방향성적은 블록체인의 핵심적인 특성 순환 그래프란? 이런 그래프를 Negatvie Graph라고 함 그래프에서 볼 수 있듯이, A -> B -> C ->A의 싸이클이 발생하여 계속적으로 반복될 수 있는 상황이 발생 두가지 문제점이 생김 1. 오로지 긍정적인 위상(S, A, B, C, D)을 가져야 산출이 쉬워짐 2. A->B->C->A같은 순환이 없어져야 함 비 순환 그래프란? 계속적으로 순환 될 수 있는 구간이 없기 때문에, 순환그래프에서 발생하는 문제점들이 없음 이것을 위상정렬(Topologically sorted)라고 함 DAG도 이런 비 순환 그래프 출처 https://steemit.com/dag/@cryptodreamers/dag-dag-directed-acyclic-graph http://new93helloworld.tistory.com/182