kakasoo

상근이는 1번을 학번으로 가지고 있다. 또한 상근이를 포함해 n번까지의 학생이 있고, 우리는 그 인간관계 m개를 받아서 서로의 친구 관계에 대해서 파악해볼 것이다. 만약 1번과 2번이 친구고, 2번과 3번이 친구라면 1번과 3번 역시 자동으로 친구다. 한 마디로 같이 노는 그룹 전체를 친구라고 한다는 것이다. (가운데 한 명 빠지면 어색해지는 사이라고 해도.) 나는 이것을 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..

(칸이라는 말을 들으면 유목민족이 먼저 떠오르는 건 이상한 걸까?) 가장 왼쪽 위 (0,0)이 하얀색이고, 하얀 색 위에 말이 몇 개 있는지 세라고 하니, 하얀 칸이 규칙성만 파악하면 되겠다. 가로 세로의 규칙을 파악해도 되겠지만 (가령 짝 짝 짝 짝 짝 짝- 줄이 바뀌면 홀 홀 홀 홀... 이런 식.) (0,0) 다음에 (0,2), 다음 줄에서는 (1,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 #include #include using namespace std; char map[8][8]; int ma..

갑자기 옛날 생각이 난다. 예전에 중학생 때, 교무실 앞에서 울고 있는 한 남자 아이가 있었다. 처음 보는 친구였지만, 그 친구가 우는 모습에 다가가서 무슨 일이냐고 물어봤다. (그 때도 새삼 내가 착했다는 게 느껴진다, 나는 앞으로도 착하게 살고 싶다.) "시험을 망했어." 그 친구가 얼마나 망했는지 몰라도, 이렇게 우는 걸 보니 노력에 결과가 따라오지 못한 듯 하였다. 당시 전교 17등이었던 내가, 그 아이를 위로하는 게 가증스러운 짓은 아닐까 염려되었지만, 나는 "너무 그러지마, 다음 번엔 더 잘 할 수 있을 거야." 라고, 조심스레 말을 골라냈다. "몇 등이길래 그래?" "2등." "뭐?" 그렇다. 이 친구는, 전교 1등을 처음으로 놓친 탓에 울고 있던 거였다. 이 일로 면식이 생긴 나는 이 친구..

바흐는 아는데 골드바흐는 처음 들었다. 그래서 알아보니까, 오일러의 친구였나보다. 골드바흐는 소수에 관한 추측들을 했는데, 이하 생략하고 그 중 하나로서 다음과 같은 추측을 해보았다. "4보다 큰 모든 짝수는 두 홀수 소수(2를 제외한 소수들)의 합으로 나타낼 수 있다." 사실 미해결된 명제이기도 하거니와, 소수를 구하는 공식도 결국 다 때려박기라 소수의 끝도 모르는데 저게 증명될 일이 있을까. 코딩러들은 이 문제를, brute force로 해봐서 모든 경우의 수가 성립함을 알 수 있을 것이다. 물론 long long int 범위 내에서... 수학은 근데 귀납을 인정 안하니 프로그래머들에겐 불가능하겠다. (빌게이츠는 세계적인 수학 난제도 증명도 했다던데?) (그 땐 빌게이츠도 프로그래머가 아니라 법대생이..

숫자가 예쁜 문제다, 14500번. 일단 문제에 대해서 간단한 해설을 쓰자면, 이건 무조건 dfs로밖에 풀 수 없는 문제다. 간단히 문제를 요약하건대, 아무 숫자가 적혀져 있는 2차원 배열이 주어질 때, 그 배열 위에 테트로미노 (이상, 위에 나와 있는 5가지 도형, 그리고 그 도형의 회전과 대칭)를 올려서 테트로미노 위에 적혀져 있는 숫자들의 합이 가장 큰 것을 구하는 문제이다. 고로 테트로미노가 4칸을 합쳐서 만든 도형이라는 특성 상, dfs든 bfs든 4칸이 되는 순간, 합을 반환하고 종료시켜야 하는데, bfs는 한 지점으로부터 상하좌우로 이동하기 때문에, 만들어진 도형이 반드시 인접할 거란 보장이 없다. 그에 반해 dfs는 한붓그리기와 같은 형태라서 안심하고 사용할 수 있다. 다만 dfs의 경우에..

질문에 있는 글인데, 너무나 잘 정리되어 있어서 가지고 왔다. (*이런 것에는 저작권이 없겠지?) 1. 가중치가 없는 최단 경로, 한 마디로 다익스트라 알고리즘을 써야 하는 게 아니면 무조건 bfs라는 것. 2. 모든 칸을 0으로 하나씩 바꿔보는 브루트 포스는, 최악의 경우 (1000 * 1000)^2의 반복이 된다. (map size = 1000 * 1000, 이고 각각의 칸이 모두 1인 경우가 있을 수 있기 때문에 1000000000000 번이다.) 3. 칸마다 방문 체크를 하는 방식으로는 풀 수 없다. 이거 참 중요한 이야기인데, 벽을 부수지 않은 세계와 벽을 부순 적 있는 세계가 있다고 가정해보자. 벽을 부수지 않은 세계를 0번 세계, 그리고 부순 세계를 1번 세계라고 할 때, 0번 세계에서 0번..

이 문제가 '브루트포스' 라는 분류를 가지고 있는 건, 내가 봤을 때 미친 짓이다. 브루트포스 방식으로도 풀 수야 있겠지만 시간초과가 미친듯이 난다. 브루트포스로, 더 이상 효율적으로 만들 수 없을 거라고 생각이 들 때까지 했는데 90%에서 시간초과였다. 그래서 다른 방식을 찾아서 했는데도 시간초과가 미친 듯이 나왔다. (그래서 데이터 구조와 STL을 적극 활용하였고, 최대공약수를 구하는 공식들도 훨씬 공부해야 했다.) 차라리 이건 '수학'만 구분으로 가지고 있는 게 낫다. 최대 값이 1000000000으로 입력될 수 있고, 같은 값이 2번 이상 입력되지 않는다고 하더라도 다른 수들과의 최대 공약수가 아무리 작아도 500000000은 나올 수 있을 텐데, 이걸 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 #include using namespace std; int memo[20] = { 1,1, }; int factorial(int num) { if (num == 0 || num == 1) return 1; if (!memo[num]) { return memo[num] = num * factorial(num - 1); } else return memo[num]; } int main(void) { int n,k; cin >> n >> k; cout

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이라는 전봇대와..