별집사의 IT세상

그리디 알고리즘정렬이 필수, 그 상황에 따른 최적의 답을 도출한다. 다이나믹 프로그래밍배열이 필수 이전 기록으로 작성 n번째의 값을 구하기 위해 n-1번째의 값에 n번째 시행을 더해서 계산 BFS 너비 우선 탐색큐를 이용해 집어넣는다 DFS 깊이 우선 탐색스택을 이용해 집어넣는다미로탐색 다이나믹으 ㅣ한종류? 백트래킹 재귀를 이용해 가능한 모든 방법을 찾는경우(시간이 많이 걸리므로 가지치기를 많이 할줄 알아야 성공할 수 있다. 다익스트라 알고리즘 한 점에서 차례대로 가면서 최단거리 값을 갱신하는 방법

인터넷이 발달하여 사람들이 웹서핑을 많이 하는데, 웹브라우져를 켜서 보통은 19번의 클릭을 한다고한다. 페이지를 전환하는 상태가 아래 그래프와 같이 주어진다면, 1번 페이지에서 2번, 3번, 4번 페이지로 갈 때의 가장 짧은 페이지 클릭 횟수는 1,1,2이고, 2번 페이지에서 1번, 3번, 4번 페이지로 갈 때 가장 짧은 페이지 클릭 횟수는 3,2,1이고, 3번 페이지에서 1번, 2번, 4번 페이지로 갈 때 가장 짧은 페이지 클릭 횟수는 1,2,3이고, 4번 페이지에서 1번, 2번, 3번 페이지로 가는 가장 짧은 페이지 클릭 횟수는 2,3,1이다. 이때, 가장 짧은 페이지 클릭 횟수의 합을 모두 구하면 1+1+2+3+2+1+1+2+3+2+3+1=22 이다.이 그래프에서 모든 쌍은 12쌍이 나오기 때문에 ..

최단경로 구하는 그래프이론에 쓰이는 알고리즘이다. 포문을 삼중으로 돌려A에서 B로 가는데 C를 거치는 경로가 더 작다면 arr[A][C] > arr[A][B] + arr[B][C], 값을 작은 값으로 갱신하는 방식이다. 모든 경우의 수를 다 돌려서 가장 작은 값들로 리셋 시키는 방식, 시간복잡도는 O(n^3)이다. int i, j, k; for(j = 0; j dist[i][j] + dist[j][k])dist[i][k] = dist[i][j] + dist[j][k]; }}}