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 무식하게 풀기 재귀함수를 통해 완전탐색을 하여 문제를 해결해보자. 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,..

IDEA 1 문제에서 주어진 N의 경우 10,000이다. 그리고 각각의 A[x]는 30,000을 넘지 않는 자연수라고 하였다. 그렇다면 N의 값이 최대일때, 모든 A[x]를 다 더하여도 300,000,000을 넘지 않는다. 즉, 최댓값이 2,147,438,647인 int형의 최댓값보다 작다. 만약 아래와 같이 배열을 만든다고 가정하고 생각하자. 1 2 3 4 5 int sums[MAX_N] for(int i = 0; i