MintPsycho's Blog

GPG (GnuPG, Gnu Privacy Guard) - PGP(Pretty Good Privacy-필 짐머만, RSA 기반 이메일 암호화 알고리즘.) 의 오픈소스 구현판이다. 원리 GPG는 RSA 암호 기술을 이용합니다. 이런 암호화의 비밀번호는 암호화할 때 쓰는 암호와 복호화(암호화된 것을 푸는 것을 의미합니다)할 때 쓰는 암호가 같습니다. (이런 암호화 방식을 대칭키 암호화라 합니다). 하지만 RSA는 다릅니다. RSA는 암호(이하 키)가 2개입니다. 어떤 키로 암호화하면 다른 키로만 복호화할 수 있습니다. (다른 키로 암호화하면 어떤 키로만 복호화 할 수 있음. 즉, 역도 성립함.) 그리고 수학적으로 큰 수를 사용하기에 깨는 데 오랜 시간이 걸립니다. 여기서 다른 사람에게 키를 공개해야 합니다...

힙 정렬(Heap sort) 이란? 최대 힙 트리나 최소 힙 트리를 사용한 정렬 알고리즘. 가장 큰 값 몇개만 필요할 때 힙정렬은 매우 효과적이다. min_heap, max_heap 을 이용한 정렬 방법입니다. 시간복잡도 O(NlogN) Process 정렬 할 요소들로 최대 힙 or 최소힙(완전 이진 트리 형태)를 만든다. 만들어진 힙에서 요소를 하나씩 꺼내어 배열에 순서대로 저장한다.

[자료구조] AVL 트리, 탐색구조 동적메모리 할당 이중연결리스트 구조, 동작방식 이진트리표현, 이진탐색트리, 힙 우선순위큐, 그래프 종류 및 용어 AOE 네트워크 / 위상 정렬 계량된 순환합병, 힙, 퀵, 기수, 허프만 [알고리즘] 알고리즘 시간복잡도 추정, 공간복잡도 추정 알고리즘 성능 비교 / 배열 구조 재귀법 벨만포드 알고리즘 [네트워크] HTTP 메소드 HTTPS / 공개키와 대칭키 OSI 7계층, TCP와 UDP Transfer Protocols in Cloud 웹의 동작 웹 브라우저에서 URL 입력 시 발생하는 일 GET과 POST 비교 DNS Round Robin SDN-Assisted Slow HTTP DDos Attack Defense Method Authentication과 Autho..

다중 프로그래밍 다중 태스킹 CPU 스케줄링 가상 메모리 / 물리 메모리 / 논리 메모리 파일 시스템 프로세스 동기화 및 통신을 위한 기법 교착상태 회피 시스템 콜, 인터럽트 > 인터럽트 벡터의 특정 위치로 트랩(trap)을 거는 형태 trap ,,, syscall 타이머, 타이밍 프로그램(수동적, passive), 프로세스(능동적, active) 프로그램 카운터 스레드 캐시, 캐싱 마운팅, 언마운팅 보안식별자(Security ID, SID) SSL(Secure Socket Layer) 가상화 P2p(peer to peer) 클라우드 활성화 레코드(activation record : 함수 호출시, 함수 매개변수, 지역 변수, 복귀 주소를 포함) 스와핑 문맥교환

Binary Heap (이진 힙) 이진 힙은 이진 트리형태로 만들어진 min-heap, max-heap 을 말한다. 완전 이진 트리라는 조건을 만족해야한다 --> 마지막 레벨은 왼쪽부터 생성. 값의 대소관계는 오직 부모관계에만 성립 --> 같은 레벨일 경우엔 상관이 없다. 힙의 삽입, 삭제 시간복잡도는 O(logN), 특정값(최대,최소) 탐색은 O(1) 삽입 최하층 리프노드에 입력값을 삽입한다. 부모와 값을 비교 후, 조건에 맞으면 그대로 두고 아니면 부모와 교환한다. 조건에 맞을 때 까지 위 과정을 반복한다. 그림에서 (7)이 새로운 입력값으로 힙에 들어왔다. 부모 노드에 있는 (18) 과 값을 비교, 자녀에 위치한 (7)이 더 작기 때문에 부모위치와 교환한다. 다시한번 부모노드인 (9) 와 값을 비교..

Critical Section Problem(임계 영역 문제) 동일한 자원을 동시에 접근하는 작업이 실행되는 코드영역을 사용할 수 있도록 하는 프로토콜 설계 상호 배제 (Mutual Exclusion) 진행 (Progress) 한정된 대기 (Bounded Waiting) Lock +) 스핀락 : 세마포 초기버전 Mutex와 Lock의 차이점 임계 영역의 락이 풀릴 때 까지 기다려야 한다는 점은 같지만, Lock은 접근 프로세스가 무한 루프를 돌면서 cpu자원을 사용한다. 반면 Mutex는 컨텍스트 스위칭을 실행한다. 따라서 다른 작업을 동시에 진행 할 수 있다. 세마포어 ㄴ 카운팅 세마포 : 가용한 개수를 가진 자원에 대한 접근 제어용으로 사용되며, 세마포는 그 가용한 자원의 개수로 초기화 된다. 자원을..

Hash function 이란? 해시함수(hash function) : 먼저, 해시함수는 해시테이블 에서 index 값으로 사용된다. key-value 쌍을 저장할 때, 고유한 key를 hash code로 변환시킨다. 이 때의 결과값은 데이터 고유의 index로 사용되기때문에 다른 값들과 같아선 안된다. 이를 위한 알고리즘이 바로 해시함수(hash function) 이다. hash function을 무조건 1:1 (key --> hash code) 로 만들게 되면, 결국 array와 다를바 없고 메모리를 너무 차지하게 된다. 따라서, 일반적으로 좋은 hash function은 키 전체를 참조하여 해쉬값을 만들어 낸다. hash function는 다음의 4가지 대표적 특성을 가진다. 압축 및 일관성 -> ..

#TODO : Count sort / Radix sort 버블 정렬(Bubble sort) 이란? 옆에 있는 값과 비교하여 더 큰 값을 반복적으로 뒤로 보내는 정렬 알고리즘. 시간복잡도 O(N^2) Process 한 칸씩 인접한 자료값을 비교하여, 큰 값이 뒤로 가도록 교환한다. 한번 끝까지 자료 탐색이 되면, 현재 iteration 에서 가장 큰 값이 맨뒤로 이동된다. 더이상 정렬할 것이 없을 때 까지 반복한다. 선택 정렬(Selection sort) 이란? 각 배열 위치에 순차적으로 어떤 원소를 넣을지 선택하여 정렬하는 알고리즘. 시간복잡도 O(N^2) Process 주어진 배열 중에서 최솟값을 찾는다. 해당 최솟값을 맨 앞에 위치한 값과 교체한다. 처음 위치를 제외한 나머지 리스트 요소들을 같은 방..

위상 정렬(topological sorting)이란? 비순환 유향 그래프 (싸이클이 없고 방향이 있는 그래프, DAG : directed acyclic graph)의 꼭짓점들(vertex)을 변의 방향(edge)을 거스르지 않도록 나열하는 것을 의미한다. 시간복잡도 O(|V| + |E|) Process 자기 자신을 가리키는 변이 없는 꼭짓점을 찾음. 찾은 꼭짓점을 출력하고 출력한 꼭짓점과 그 꼭짓점에서 출발하는 변을 삭제 아직 그래프에 꼭짓점이 남아있으면 단계 1로 돌아가고, 아니면 알고리즘을 종료시킨다. from collections import deque # 노드의 개수 v와 DAG v= 7 adj_list = [[1, 2], [1, 5], [2, 3], [2, 6], [3, 4], [4, 7], [..

Stack 알고리즘에서 O(1) 시간복잡도로 최솟값을 반환하는 방법 1. Stack 을 push 할 때, [원소 x, 현재까지 스택에 저장된 원소 중 최솟값] 저장하면 된다. class minimum_Stack(): def __init__(self): self.Stack = [] #파이썬은 리스트를 스택으로 사용가능 def push(self, element): # 스택 push if not self.Stack: self.Stack.append([element, element]) else: # 현재 스택의 최솟값(top.second)과 입력값을 비교하여 추가시킴. self.Stack.append([element, min(element, self.Stack[-1][1])]) def pop(self): ret..