분류 전체보기68 [코딩테스트 대비]완전탐색 (BP - 브루트포스) 완전탐색 (Brute-Force) BP라고 불리는 완전탐색은 단어 그래로 모든 경우의 수를 다 해보는 것이다. 알고리즘을 풀때 강력한 방식이지만, 시간은 최대로 들어간다. 예를들어 비밀번호가 4자리이고 숫자로만 이루어져 있다면, 0 ~ 9999까지 다 해보면된다. 경우의 수는 10,000가지이다. 만약 한 숫자당 1초가 걸린다고 하면 10,000초 = 2.7시간정도가 걸린다. 따라서 완전탐색을 풀기위해서는 대표적으로 4가지를 생각해볼 수 있다. for문 사용 순열, 조합 사용 재귀함수 사용 비트마스크 사용 2309번 일곱 난쟁이 조합을 이용해서 풀면된다. 1476번 날짜 계산 나머지를 이용 14500번 테트로미노 노가다 문제... 1966번 프린터 큐 큐 개념도 연습할 수 있다. 2231번 분해합 순열(.. 2019. 3. 30. [코딩테스트 대비]알고리즘 기본문제 (덧셈, 나머지연산, 유클리드) Fundamental 코딩테스트를 처음 준비하거나 알고리즘 문제를 풀기 전에 간단히 풀어보면 좋은 유형들을 모아보았다. 처음에는 간단한 입 출력부터 연습을 하고 사칙연산을 통해 기본을 마무리 한 후에 나중에 나올 유형들을 풀 때 유용하게 쓰이는 것들을 연습해 볼 수 있도록 모아두었다. 입 출력 2557번 Hello World 11718번 그대로 출력하기 덧셈 연산 1000번 A+B 2558번 A+B -2 10950번 A+B -3 10951번 A+B -4 10952번 A+B -5 10953번 A+B -6 11021번 A+B -7 11022번 A+B -8 15552번 빠른 A+B 나머지 연산 참고 : A+B % N = (A % N) + (B % N), (A-B) % N = ((A % N) - (B % N) .. 2019. 3. 30. [코딩테스트 대비] 깊이 우선 탐색 (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 ··· 12 다음
