알고리즘10 Floyd 알고리즘이란 무엇인가? 플로이드(Floyd) 알고리즘 플로이드 알고리즘 : 모든 정점 쌍에 대해서 둘 사이의 최단 거리를 구한다. 다익스트라 알고리즘 : 한 시작점에서 다른 정점까지의 최단 거리를 구한다. 1) 경유점 a와 b로 연결되어 있는 간선의 비용 : 5 a와 c : 2, c 와 b : 2 => 4 a와 b로 가는데 c를 거쳐가는 것이 더 효율적이다. c와 같이 경로가 거쳐가는 정점이 경유점이라고 한다. 플로이드 알고리즘은 두 정점 사이의 어떤 경유점이 존재한다면 경유점을 거쳐가는 것을 확인하면서 더 짧은 것을 선택하게 된다. 2) 구현 위 그래프가 있을 때, 모든 쌍의 최단거리는 어떻게 될까?🤔 다익스트라 알고리즘을 이용하여 모든 정점에 대해서 구할 수 있지지만, 플로이드 알고리즘을 쓰면 보다 쉽고 빠르게 구할 수 있.. 2021. 8. 14. Backtracking이란 무엇인가? 백트래킹(Backtracking) 일반적인 알고리즘이다. 백트래킹은 CSP(Constrain Staisfaction Problems)을 해결하기 위해 쓰인다. 백트래킹은 모든 조합의 수를 조건이 만족할 때 살펴본다. N-Queen문제에서 많이 사용된다. N * N 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 4 * 4 기준으로 문제를 풀어보자. 퀸은 칸을 기준으로 오와 열, 대각선 이동이 가능하다. 첫 번째 퀸과 공격할 수 없게 배치할려면 2번째 줄은 3, 4번째 위치에 퀸을 놓아야 한다. 첫 번째 퀸의 위치를 (1, 1)로 하면 트리구조는 다음과 같다. 만약 이문제를 가지치기 하지않는 DFS로 풀이했다면 유망하지 .. 2021. 8. 4. DP란 무엇인가? 동적 계획법 동적 계획법(dynamic programming) : 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 부분 문제 반복과 최적 부분 구조를 가지는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. 1. 동적 계획법의 조건 1) 부분 반복 문제(Overlapping Subproblem) 동적 계획법의 등장은 피보나치 수열에서 시작되었다고 한다. 피보나치 수열을 재귀 함수로 표현할 시, 이와 같다. fib(1) = 1; fib(2) = 1; fib(n) = fib(n-1) + fib(n-2); // 메소드로 표현한 피보나치 수열 int fib(int n) { if (n 2021. 8. 4. DFS, BFS란 무엇인가? DFS DFS 개념 (Depth First Search, 깊이 우선 탐색) 갈 수 있는만큼 깊게 가고, 더 이상 갈 수 없다면 이전 정점으로 돌아간다. stack으로 구현 DFS 사용할 때2) 맨 위에서 하나 빼낸 후, 그 위치에서 갈 수 있는 경로를 스택에 다 넣는다. 3) 원하는 값을 찾을 때까지 2번을 반복한다. 1) 첫 번째 위치를 스택에 넣는다. BFS BFS 개념 (Breath First Search, 넓이 우선 탐색) 현재 정점에서 갈 수 있는 위치부터 끝까지 탐색해나감 queue으로 구현 BFS 사용할 때2) 큐에 넣었던 값을 빼낸 후, 그 위치에서 갈 수 있는 경로를 큐에 넣는다. 3) 원하는 값을 찾을 때까지 2번을 반복한다. 1) 첫 번째 위치를 큐에 넣는다. dfs, bfs 주의할 .. 2021. 7. 29. 이전 1 2 다음
