Computer Security

다익스트라의 최단 경로 1.각 간선에 대한 정보를 우선순위 큐에 담아 처리하는 방식으로 동작 원리가 프림 알고리즘과 흡사하다. 2.다익스트라의 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작한다. 3.현실 세계에서는 음의 간선이 존재하지 않기 때문에 다익스트라는 현실 세계에 적합한 알고리즘이다. 동작방식 1.그래프의 시작점을 선택해 트리T에 포함시킨다. 2.T에 포함된 노드와 T에 포함되지 않은 노드 사이의 간선 중에서 '이동거리'가 가장 작은 간선을 찾는다. 3.해당 간선에 연결된 T에 포함되지 않은 노드를 트리 T에 포함시킨다. 4. 모든 노드가 포함될 때까지 2와 3과정을 반복한다. 코드예시 #define _CRT_SECURE_NO_WARNINGS #include #include #inc..

최소 신장 트리 1.신장 트리란 특정한 그래프에서 모든 정점을 포함하는 그래프이다. 2.최소 신장 트리는 스패닝 트리 중에서 간선의 가중치 합이 가장 작은 트리를 의미한다. ->모든 노드를 연결할때, 가장 적은 간선만 선택 할 수 있도록 한다. 프림 알고리즘 1.그래프에서 정점 하나를 선택해 트리T에 포함시킨다. 2.T에 포함된 노드와 T에 포함되지 않은 노드 사이의 간선 중에서 가중치가 가장 작은 간선을 찾는다. 3.해당 간선에 연결된 T에 포함되지 않은 노드를 트리 T에 포함시킨다. 4.반복한다. ->프림 알고리즘은 각 간선에 대한 정보를 우선순위 큐에 담아 처리하는 방식으로 구현할 수 있다. 코드예시 #define _CRT_SECURE_NO_WARNINGS #include #include #incl..

해시 1.해시(Hash)는 데이터를 최대한 빠른 속도로 관리하도록 도와주는 자료 구조이다. 2.해시를 사용하면 메모리공간은 많이 소요하지만, 매우 바른 속도로 데이터를 처리할 수 있다. 3.빠르게 데이터에 접근할 수 있다는 점에서 데이터베이스 등의 소프트웨어에서 활용된다. 해시함수는? 어떠한 데이터를 암호화시키기에 용이하다. 예를들어, 해시함수를 n mod 5 라하자. n mod 5는 n을 넣었을때, 5로 나눈 나머지값인데 입력데이터가 23 오리 16 피자 14 김치 2 나물 이라 한다면 key가 key 값 3 오리 1 피자 4 김치 2 나물 이런식으로 작성된다. 특징 특정한 값을 찾고자 할 때는 그 값의 키(Key)로 접근할 수 있다. 일반적인 해시함수는 모듈로 연산등 수학적 연산으로 이루어져 있으며,..

1.AVL트리는 균형이 갖춰진 이진트리를 의미한다. 2.완전 이진트리는 검색에 있어서 O(logN)의 시간 복잡도를 유지할 수 있다. 3.AVL트리는 간단한 구현과정으로 특정 이진 트리가 완전 이진 트리에 가까운 형태를 유지하도록 해준다. AVL트리를 통해 얻는 이점? 한쪽으로 편향되어있는 트리 같은경우 너비우선탐색을 좀 더 효율적으로 만들어 줄 수있다. 균형인수를 통해 알고리즘을 세운다. 균형인수란? = ㅣ왼쪽 자식 높이 - 오른쪽 자식 높이ㅣ 특징 1.AVL트리느 모든 노드에 대한 균형 인수가 +1, 0 , -1 인 트리를 의미한다. 2.균형 인수가 위 세 가지 경우에 해당하지 않는 경우 '회전'을 통해 트리를 재구성한다. 3.AVL트리의 각 노드는 '균형 인수'를 계산하기 위한 목적으로 자신의 '높..