본문 바로가기
반응형

Algorithm18

Algorithm - Dijkstra(다익스트라) 알고리즘 Dijkstra Algorithm : Dynamic programming을 이용한 대표적인 최단경로(Shortest path) 탐색 알고리즘. 다익스트라 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려줌. 이 때 음의 Edge는 포함할 수 없음(현실 세계에선 음의 Edge가 존재 하지 않기 때문에 다익스트라는 현실에서 사용하기 매우 적합함). / 음의 가중치가 없는 그래프의 한 정점(vertex)에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘 / 에츠허르 다익스트라 라는 사람이 고안한 알고리즘이라함. / 그래프 방향의 유무는 상관없으나 간선(Edge)들 중 단 하나라도 가중치가 음수이면 이 알고리즘은 사용할 수 없음. 음의 가중치를 가지는 간선이 있으며 가중치 합이 음인.. 2022. 5. 7.
Algorithm - Backtracking(백트래킹) Backtracking : 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾는 기법. 최적화 문제와 결정 문제를 푸는 방법이 된다. / 가능한 모든 방법을 탐색한다라는 성격을 가짐. / 모든 경우의 수를 전부 고려하는 알고리즘. 상태 공간을 트리로 나타낼 수 있을때 적합한 방식(일종의 트리 탐색 알고리즘). 방식에 따라서 DFS, BFS, 최선 우선 탐색 등이 있다. DFS가 일반적. / 현재 상태에서 가능한 모든 후보군을 따라 들어가며 해결책에 대한 후보를 구축해 나아가다 가능성이 없다고 판단되면, 즉시 후보를 포기하면서 정답을 찾아가는 범용적인 알고리즘. DFS와 Backtracking : DFS - DFS의 장점은 무한히 깊은곳을 찾아야 할때 효과적이고 단점은 모든곳을 방문하기 때문에.. 2022. 5. 4.
Algorithm - Brute force(브루트 포스) Brute force : 키 전수조사(exhaustive key search), 무차별 대입, 완전탐색 알고리즘 조합 가능한 모든 문자열을 하나씩 대입해 보는 방식으로 암호를 해독하는 방법. 흔히 암호학에서 연구되지만, 알고리즘 분야에서도 사용. (수학 문제를 원시적으로 푸는 방법인 '수 대입 노가다'의 학술적 버전) / 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져옴. 브루트 포스의 강력한 점은 예외없이 100%의 확률로 정답만을 출력한다. Brute force 특징 : brute-force는 "짐승같은(난폭한) 힘"의 뜻이고 오래 걸리는 데다 자원이 엄청나게 들어서 얼핏 보면 무식해보이지만, 항상 정확도 100%를 보장 한다는 것이 암호 해독법 중 가장 확실하고 무서운 방.. 2022. 5. 2.
Algorithm - Divide and Conquer(분할 정복) Divide and Conquer algorithm : 분할 정복은 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘. (원래 문제를 분할하여 비슷한 유형의 더 작은 하위 문제들로 나눈다) Divide and Conquer 알고리즘 설계 요령 (도식화) : - Divide : 문제가 분할이 가능한 경우, 2개 이상의 문제로 나눈다. / 문제를 더 이상 분할할 수 없을 때까지 동일한 유형의 여러 하위 문제로 나눈다. - Conquer : 나누어진 문제가 여전히 분할이 가능하면, 다시 divide를 수행. 그렇지 않다면 문제를 푼다. / 가장 작은 단위의 하위 문제를 해결하여 정복. - Combine : Conquer한 문제들을 통합하여 원래 문제의 답을 얻는다. .. 2022. 4. 28.
Algorithm - Breadth First Search(너비 우선 탐색) Breadth-First Search(BFS, 너비 우선 탐색) : root 노드(혹은 다른 임의의 노드)로부터 시작해서 인접한 노드를 먼저 탐색하는 방법. (최단 경로 탐색, 임의 경로 탐색) / 시작 노드로부터 가까운 노드를 먼저 방문하고 멀리 떨어진 노드는 나중에 방문하는 traverse방법. / 깊게(deep하게) 탐색하기 전 넓게(wide하게) 탐색. / 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을때 이 방법을 사용. / 예) facebook같은 거에 존재하는 모든 친구 관계를 그래프로 표현한 후 Hong과 Jo 사이에 존재하는 경로를 찾을때. DFS - 모든 친구 관계를 다 살펴봐야 할 수도 있음. BFS - Hong과 가까운 관계부터 탐색. / BFS가 DFS보다 좀 더 복잡함... 2022. 4. 20.
Algorithm - Depth First Search(깊이 우선 탐색) Graph 탐색 : 하나의 vertex로 부터 시작하여 차례대로 모든 vertex들을 한 번씩 방문하는 것. / 예) 특정 도시에서 다른 도시로 갈 수 있는가, 전자 회로에서 특정 단자끼리 서로 연결 되어 있는가 Depth-First Search(DFS, 깊이 우선 탐색) : root 노드(혹은 다른 임의의 노드)로부터 시작해서 다음 branch로 넘어가기 전에 해당 branch를 완벽하게 탐색하는 방법. / 미로 탐색시 한 방향으로 갈 수 있을때까지 계속 가다가 더 이상 갈수 없을때, 다시 가장 가까운 갈림길로 돌아와서 이곳에서 다른 방향으로 다시 탐색을 진행하는 방법과 유사함. / 넓게(wide하게) 탐색하기 보다는 깊게(deep하게) 탐색하는 것. / 모든 node를 방문하고자 하는 경우에 이 방법.. 2022. 4. 19.
반응형

티스토리툴바

*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*