DFS? Depth First Search의 약자이다. 즉, 깊이우선 탐색 알고리즘이다. 그렇다면 DFS 알고리즘은 어떻게 동작하는 지 알아보자. IDEA 위와 같이 생긴 그래프를 노드 0에서부터 깊이 탐색을 해보자. 1. 0 2. 0 -> 1 3. 0 -> 1 -> 5 5번 노드에서 갈 수 있는 노드가 없으므로 다시 뒤로 복귀한다. 4. 0 -> 1 -> 5 1번 노드 또한 더 이상 탐색할 수 있는 노드가 없으므로 0번으로 복귀한다. 5. 0 -> 1 -> 5 -> 2 0번에서 2번을 탐색할 수 있으므로 2번을 탐색한다. 6. 0 -> 1 -> 5 -> 2 -> 3 6. 0 -> 1 -> 5 -> 2 -> 3 -> 6 7. 0 -> 1 -> 5 -> 2 -> 3 -> 6 -> 7 7번 노드에서 0번으로..

IDEA 문제를 탐색해보면 DFS로 문제를 풀 수 있다. CODE 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #define MAX_NODE 100 #define INIT_PREV -1 int visited[MAX_NODE][MAX_NODE] = { 0, }; int adj[MAX_NODE][MAX_NODE]; int N; void dfs(int start, int prev, int now) { if (visited[start][now] == 1) { return; } if (prev != INIT_PREV) { //처음 탐색을 했을 때, start에서 now로 가는 경우는 start = now인 경우이다. //따라서, 본인에서 본인으로 갈 수 없..

다익스트라 알고리즘? 그래프에서 노드들간의 최단 거리를 알아내기위해 사용하는 알고리즘이다. 다익스트라 알고리즘은 매우 직관적인 알고리즘이다. 그렇다면 다익스트라 알고리즘이 어떻게 동작하는지 알아보자. IDEA 예를 들어 아래와 같은 상황을 생각해보자. 위 와같은 지도를 보자. 집에서 각각의 상점까지의 최단거리를 알아내고자한다. 이때 다익스트라 알고리즘을 사용하여 해결해보자. 1. 처음 집에서 출발을 한다. 집에서 처음 출발할때, 가지고 있는 정보는 집에서 집으로 갈 때, 0이라는 시간이 소요된다는 것 뿐이다. 이제 집에서 바로 갈 수 있는 장소들에 대해 탐색해보자. 2. 집에서 바로 갈 수 있는 장소들 중 상점, 영화관, 은행의 경우 기존의 거리(INF)보다 집에서 집까지의 거리 + 집에서 각 위치들 까..

IDEA 1 무식하게 풀기 재귀함수를 통해 완전탐색을 하여 문제를 해결해보자. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 #define MAX_WINE_CUP 10000 #define MAX_DRINK_CON 2 int wineAmount[10001] = { 0, }; int wineCupCount; int totalDrink; void drinkWine(int cupIndex, int drinkAmount, int continuous) { if (cupIndex > wineCupCount) { totalDrink = max(totalDrink, drinkAmount); return; } drinkWine(c..

일반적으로 피보나치 수를 이용하여 문제를 해결하려고 해보면, 1 2 3 4 5 6 7 int getFibo(int n) { if (n long long 자료형을 사용해 주자. 그리고 시간 복잡도의 경우 2^n이므로 최악의 경우 2^90 = 1,237,940,039,285,380,274,899,124,224‬ 이므로, 1초의 시간을 넘어 서게 된다. 위의 경우, 어떻게 문제를 해결해야 할까? IDEA 1 for 문으로 탐색해서 피보나치 값을 구해보자. 1 2 3 4 5 6 7 8 9 10 if(n

IDEA N의 최댓값은 1,000,000이며 M의 최댓값은 2,000,000,000이다. 가능한 모든 높이의 길이를 탐색하여 답을 구하고자 한다면, 1,000,000 * 2,000,000,000 즉, 주어진 시간제한을 넘길 것이다. 이를 해결하기 위해서 좀 더 생각을 해보자. 나무가 나열된 순서는 상관이 없다. 그렇다면 나무를 순서내로 나열 시켜보자. 위와 같이 나무를 정렬 시켰을 때, 자르고자 하는 나무의 높이를 이분탐색하여 찾는다고 생각해보자. 우선, 나무를 정렬시키는데 사용되는 시간은 NlogN --> 1,000,000*lg1,000,000 약, 20,000,000의 시간이 소요된다. 그리고 이분탐색을 이용하여 높이의 최댓 값을 탐색해보자. NlogM --> 1,000,000*lg2,000,000,..