암호화 알고리즘 암호를 만드는 알고리즘이다. 용어 평문(Plaintext) : 해독 가능한 형태의 메시지(암호화 전 메시지) 암호문(Cipertext) : 해독 불가능한 형태의 메시지(암호화된 메시지) 암호화(Encryption) : 평문을 암호문으로 변환하는 과정 복호화(Decryption) : 암호문을 평문으로 변환하는 과정 전자서명 송신자의 Private Key로 메시지를 서명하여 전달 수신자측에서는 송신자의 Public Key를 이용하여 서명값을 검증 양방향 암호화 암호화와 복호화과정을 통해 송,수신간 주고받는 메시지를 안전하게 암,복호화하는 과정 단방향 암호화 해싱(Hashing)을 이용한 암호화 방식으로 양방향과는 다른 개념이다. 평문을 암호문으로 암호화는 가능하지만 암호문을 평문으로 복호화 ..
MST(Minimum Spanning Tree 최소 신장 트리) 신장 트리 : 모든 정점이 연결된 그래프, 사이클이 존재하지 않아야 한다. n개의 점을 (n-1) 개의 간선으로 연결한다. 최소 신장 트리 : 신장 트리 중 간선 가중치의 합이 가장 작은 신장 트리를 의미한다. Prim(프림) 알고리즘 시작 정점에서 출발하여 신장트리 집합을 단계적으로 확장해 나가는 방법이다. 수행 과정 임의의 정점을 시작 지점으로 선택 연결된 모든 간선의 가중치를 비교 가장 작은 무게의 간선 선택(사이클이 만들어지지 않도록) 모든 정점이 연결될 때까지 2~3번 과정 반복 시간복잡도 V : 정점의 개수 E : 간선의 개수 우선순위 큐로 구현 우선순위 큐 생성 작업 : O(logV) * O(E) = O(ElogV) 각 노드에서..
재귀함수(Recursion) Stack 개념을 이용해 자기 자신을 다시 호출하며 반복하는 함수이다. 구성 탈출 조건, 연산, 재귀 호출로 이루어진다. 탈출 조건을 잘못 설정하면 Stack Overflow가 발생한다. public static int rSum(int n){ // 탈출 조건 if(n == 0) return 0; // 재귀 호출 return n += rSum(n-1); } 장점 가독성을 높일 수 있다.(재귀적인 표현이 자연스러운 경우) 단점 호출이 많아질수록 Stack에 쌓여 메모리 사용량이 계속 증가한다. Stack Overflow가 발생할 수 있다. 재귀함수 사용 예시 피보나치 수열, 팩토리얼 구하기 분할 정복 알고리즘 이진 탐색 하노이의 탑 백트래킹 알고리즘 Tail Recursion(꼬..
그리디 알고리즘(Greedy Algorithm) 다음 단계를 생각하지 않고, 현재 단계에서 가장 최선을 선택하는 기법이다 조건 탐욕 선택 속성(Greedy Choice Property) 이전의 선택이 이후에 영향을 주지 않음 최적 부분 구조(Optimal Substructure) 부분 문제의 최적결과가 전체에도 그대로 적용될 수 있어야 한다 특징 전체 상황에서의 최적의 결과를 보장하지 못한다. 속도가 매우 빠르다 사용 예시 : 거스름돈, 활동 선택(Action Selection) 문제 등 동적 계획법(Dynamic Programming) 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용 조건 겹치는 부분 문제(Overlapping Subproblems)..
Binary Search(이진탐색) 정렬된 배열, 이진 트리에서 특정한 값을 찾아내는 알고리즘이다. 정렬이 전제되어 있어야 한다. 한번 비교를 거칠 때 탐색 범위가 1/2로 줄어든다. 범위의 중앙 값과 비교한다. 찾는 값이 중앙 값보다 작다면 왼쪽(그림 : 내림차순 정렬이므로 오른쪽) 1/2의 범위에서 탐색한다. 찾는 값이 중앙 값보다 크다면 오른쪽(그림 : 내림차순 정렬이므로 왼쪽) 1/2의 범위에서 탐색한다. 1번/2번 해당하는 작업을 반복한다. 찾는 값이 중앙 값이면 탐색을 종료한다. 기본 형태의 Java 코드 int BinarySearch(int dataArr[], int size, int findData) { int low = 0, high = size - 1, mid; // high가 low보..
