전체 글68 [코딩테스트 대비] 깊이 우선 탐색 (DFS) 정리 DFS (깊이 우선 탐색) 소개 Root Node 혹은 다른 임의의 노드에서 시작해서 다음 분기(Branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다. Stack과 재귀함수(Recursion)으로 구현한다. 경로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게되면 다른 방향으로 다시 탐색을 진행 모든 노드를 방문하는 경우에 이 방법을 사용한다. 사용용도 경로찾기 u, v가 주어졌을 때 u -> v로 가는 경로를 찾을 때 그래프의 사이클을 찾을 때 back edge 즉, 순환을 만들어 주는 마지막 edge를 찾는다. 시간복잡도 두 가지의 자료구조(인접 리스트, 인접 행렬)로 구현할 수 있다. 인접 리스트 : O(V + E) 인접 행렬 : O(V^2) 접점(V).. 2019. 3. 30. [코딩테스트 대비] 너비 우선 탐색 (BFS) 정리 BFS (너비 우선 검색) 정리 소개 Root Node 혹은 다른 임의의 노드에서 인접한 노드를 먼저 탐색하는 방법이다. Queue를 사용해서 구현한다. 시간 복잡도 인접 리스트 : O(V + E) 인접 행렬 : O(V^2) 접점(V), 간선(E) class Graph { private int V; private LinkedList adj[]; Graph(int v) { V = v; adj = new LinkedList[v]; for (int i=0; i 2019. 3. 30. [코딩테스트 대비] 동적 계획법 (DP) 정리 동적 계획법(Dynamic Programming) 정리 큰 문제를 작은 문제로 나눠서 푸는 알고리즘인데, 코딩테스트에서 자주 출제되는 알고리즘 기법입니다. DP 속성 Overlapping Subproblem (부분 문제가 겹친다.) Optimal Substructure (최적 부분 구조) Overlapping Subproblem 대표적인 예로 피보나치 수를 들 수 있다. Fn = Fn-1 + Fn-2 여기서 Fn을 큰 문제로 생각하고, 우측 항에 있는 Fn-1, Fn-2를 작은 문제로 나눈다고 생각하면 된다. Optimal Substructure 문제의 정답을 작은 문제의 정답을 합하는 것으로 구할 수 있다. 위의 예에서 작은 문제로 쪼갠 우측항의 Fn-1 + Fn-2로 큰 문제인 Fn의 값을 구할 수 .. 2019. 3. 30. 기초 암호학(3) - 공개키 암호 (RSA, Diffie-Helmman) 이번 포스팅에서는 대칭키의 키 배분 문제점을 해결한 공개키 암호화 알고리즘을 소개하려고한다. 비대칭 암호(Asymmetric Cryptography)라고도 불리는데, 두 개의 공개키(Public Key), 비밀 키(Private Key)를 사용한다. 공개 키(Public Key) 공개키 암호학 방식에서 키 생성은 Trap door one way function에 기반을 둔다. 한 방향으로 계산이 쉬우나 다른 방향으로의 계산이 어렵다는 것을 이용한 방식이다. 키를 생성하는데 두 가지의 방법이 존재한다. 첫 번째로 소인수분해를 이용한 키 생성 방법이 있다. $$ N\ =\ pq $$ p가 11이고 q가 13일때 N을 구하는 건 간단히 11x13 = 143 간단하게 구할 수 있지만 143을 소수인 p와 q를 .. 2019. 3. 27. 이전 1 2 3 4 5 6 ··· 17 다음
