728x90 반응형 알고리즘4 다익스트라 알고리즘 다익스트라 알고리즘(Dijkstra 알고리즘) 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용한다. 다익스트라 알고리즘의 경우 어떤 경우에는 다이나믹 프로그래밍, 어떤 경우에는 탐욕 알고리즘으로 분류되기도 한다. 탐욕 알고리즘이란? 현재 상황에서 여러가지 경우가 있을 경우, 그 순간의 최선의 선택을 하는 알고리즘이다. 작동 과정 출발 노드를 설정 출발 노드를 기준으로 각 노드의 최소 비용을 저장 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신 위 과정에서 3~4.. 2019. 4. 23. 자료구조와 알고리즘 자료구조란? 프로그램이란 데이터를 표현 알고리즘이란? 표현된 데이터를 처리 알고리즘을 평가하는 두 가지 요소 - 시간 복잡도 - 공간 복잡도 시간 복잡도의 평가 방법 - 중심이 되는 특정 연산의 횟수를 세어서 평가를 한다. - 데이터의 수에 대한 연산횟수의 함수 T(n)을 구한다. O(1) - 상수 시간 알고리즘이 문제를 해결하는데 오직 한 단계만 거친다. O(log n) - 로그 시간 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어든다. O(n) - 직선적 시간 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가진다. O(n^2) - 2차 시간 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱이다. O(C^n) - 지수 시간 문제를 해결하기 위한 단계의 수는 주어진 상수.. 2019. 4. 18. cordforces - A. Theatre Square Theatre Square in the capital city of Berland has a rectangular shape with the size n × mmeters. On the occasion of the city's anniversary, a decision was taken to pave the Square with square granite flagstones. Each flagstone is of the size a × a. What is the least number of flagstones needed to pave the Square? It's allowed to cover the surface larger than the Theatre Square, but the Square ha.. 2018. 1. 24. 전자 서명 알고리즘 - RSA 개인키,공개키를 생성하는 방법은 전의 RSA 암호 알고리즘때의 설명과 동일합니다. ● 사용자 public key(n,e) 임의의 두 소수 p,q의 곱으로 이루어진 합성수 n만 공개를 하고 어떤 p,q로 곱해져있는지 절대로 공개하면 안됩니다. (p-1)(q-1)의 서로소인 아무거나 e를 공개키로 합니다. ● 사용자 private key(n,d) d를 구하려면 e는 공개된 값이고 은 multiplicative group이기 때문에 역원이 존재합니다. d는 mod (p-1)(q-1)상에서 역원만 구하면 되는데 p,q를 알아야 구할 수 있습니다. p,q만 알면 이미 알려진 e의 역원 구하는 것은 쉽습니다. 따라서 n에 대한 p,q를 아는 사람만 비밀키를 구할 수가 있습니다. ● Signature 사용자가 어떤 .. 2017. 12. 9. 이전 1 다음 728x90 반응형
