kakasoo

어려웠다. 어떻게 접근해야 할지 고민하다가 알아낸 것이, 전깃줄이 교차되는 경우의 수였다. 예제의 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 ..