kakasoo

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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 #include using namespace std; int n, s, sum, counted; int arr[21]; bool visited[21]; void dfs (int start) { visited[start] = true; int cur = start; sum += arr[start]; if (sum == s) { counted++; } for (int i = start + 1; i > n >> s; for (int i = 0; i > arr[i]; for (i..

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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 #include #include using namespace std; /* push X : 정수 X를 스택에 넣는 연산이다. pop : 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 ..

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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 #include using namespace std; int k, n; // 문제에서 요구하는 랜선의 개수를 n이라고 하고, unsigned long long int arr[10000]; // arr 배열은 처음에 주어진 초기 랜선의 길이들이다. int counted..

어려웠다. 어떻게 접근해야 할지 고민하다가 알아낸 것이, 전깃줄이 교차되는 경우의 수였다. 예제의 1부터 10까지의 전봇대를 생각해볼 때, 1부터 10까지를 배열의 index처럼 취급할 수 있을 것이다. 만약 이 index가 더 후위에 있다면, 이 인덱스에 해당하는 배열의 값도 더 후위에 있어야 한다. 즉 1이 3으로 연결되어 있다면 2부터 10까지는 적어도 4 이상과 연결되어 있어야 1과 교차하지 않는다. 그러나 문제가 생기는 것이 바로 0이었다. 만약 1이 0이라고 한다면 2 ~ 10까지는 1이상과 연결되어도 되는 것이니 아무런 문제가 없다. 그러나 만약 index 2가 0이라고 한다면, 사실 index 2는 값과 무관하게 항상 앞전과 교차할 일이 없어야 하겠지만, 컴퓨터는 이 0을 0이라는 전봇대와..

그리디 알고리즘 (탐욕 알고리즘)이라고 하는데, 비슷한 종류의 문제들 중에 이게 가장 수준이 높았던 거 같다. 그리디 알고리즘은, 솔직히 나는 이런 거에 알고리즘이라는 말을 붙일 필요가 있나 싶을 정도로 간단했다. 그 순간 순간의 최적해를 쫓아 가서, 근사값을 구하는 방식의 알고리즘이라는 건데, 당연 그 순간의 최적해를 쫓을 때 최종적인 답안이 최적해가 아닐 수도 있다. 말하자면, 지금 알고리즘 조건에 따라서, 이렇게 설명할 수 있겠다. 2일 간격으로만 음식을 먹을 수 있고, 더 적은 음식을 먹어야할 때, 첫날 음식을 먹느냐 둘째날 음식을 먹느냐, 첫날과 둘째날을 비교해서 작은 쪽을 먹는다는 게 그리디의 방식이지만, 만약 셋째날이 무한대에 수렴한다면 다시 처음으로 돌아가 두번째를 먹는 것을 고르는 것이 ..

오랜만에 bfs 문제를 풀었다. 하도 안 보던 알고리즘을 푸니까 머리가 돌아버릴 거 같아서 일부러 bfs 문제를 풀었다. 역시 완벽하게 이해가 된 알고리즘은, 손이 알아서 치고, 이게 또 너무 재밌다. 음악을 즐긴 적은 없지만 무작정 피아노를 두들기는 사람들이 이런 기분이었을까. 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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 8..

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 30 31 32 33 34 35 36 37 38 39 #include using namespace std; int startLink[21]; int arr[21][21]; int visited[21]; int n; void dfs(int cnt, int start) { if (cnt == n / 2) { for (int i = 0; i

알고리즘 구분 알고리즘을 공부하며 가장 헷갈린 것이, 알고리즘의 이름이 무얼 의미하는지 몰랐던 부분이었다. n-Queen 문제를 풀 때도, 풀이를 보고 신기했던 경험이 있었지만 백트래킹에 대한 이해는 얕았다. 그러나 그것이 스도쿠 문제를 풀면서 완전한 이해로 갖춰지게 된 거 같다. 일단 기본적으로, 브루트 포스가 있다. 브루트 포스는 for문이든 중첩된 for문이든 간에 모든 경우의 수를 다 찾아보는 방식이다. 이 브루트 포스에서 방문한 칸을 체크하는 것으로 효율을 꾀하는 것이 dfs와 bfs로 나타난다. 그러나 dfs는 갈래의 마지막까지 방문한 다음에 옳고 그름을 판단하는데, 다음의 문제가 있다 1) 만약 재귀가 끝나지 않는다면? -> 런 타임 에러가 발생한다. 2) 중간에 틀린 걸 판별했다면? -> ..

문제를 처음 접했을 때, 이걸 어떻게 하라는 건가 싶었다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#include using namespace std; int k, n;unsigned long long int arr[10000]; int counted; bool cutting(int standard){ counted = 0; for (int i = 0; i = standard) { temp -= standard; counted++; } } if (counted >= n) return true; else return false;} int main(void){ cin ..

일단 첫번째로 올린 코드는 잘못된 코드다. 46%에서 시간초과로 끝나는 것을 확인할 수 있다, 이전 이분 탐색 문제에서는 내가 제시한 방법으로 시간초과를 해결했지만 이 문제에서는 같은 방법으로 해도 46%까지 밖에 안 되는 거로 보아 더 획기적인 해결 방법이 필요한 듯 하다. 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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 ..