오로지 PS만을 위한 Sprague-Grundy Theorem(스프라그-그런디 정리) PS를 하다 보면 Combinatorial Game Theory(조합론적 게임 이론) 분야가 있다. 이번 방학 동안 참가한 알고리즘 캠프에서 알게 된 분야인데, 내용이 상당히 어려웠고 다른 사람들도 어렵게 느낄 것이라는 생각이 들었다. 이 분야를 이해하기 위해 열심히 발버둥친 결과, 증명 등은 배제하고 몇 가지 핵심만 안다면 많은 사람들이 충분히 이 분야의 문제들에 도전해볼 수 있을 것이라는 생각을 했다. 따라서 이 글은 엄밀하게 Combinatorial Game Theory를 공부해 보자는 글은 아니며 오로지 PS만을 위한 응용을 목적으로 하는 글이다. 이어지는 내용에서 결론만 이야기하고 넘어가는 부분들이 많은데 이 글의 목적을 위해서 그렇게 서술한 것이니 관심이 있는 사람들은 마지막에 달아 놓은 링크.. 2021. 3. 2. [BOJ #11659] 구간 합 구하기 4 BOJ #11659, 구간 합 구하기 4 문제입니다. 원소 수 N개의 정수 배열이 주어졌을 때 입력된 구간의 합을 출력하면 됩니다. 프로그램 자체가 간단하지만, 일반적인 방법으로는 시간복잡도가 너무 높아 시간 내에 풀 수 없습니다. 이를 해결하기 위해서는 '누적합'을 이용하면 됩니다. 수학에서 수열을 다룰 때 급수를 이용해 a_n = s_n - s_(n - 1)과 같이 나타내는 것과 동일한 원리를 이용합니다. 이것을 알면 코드 구현은 어렵지 않게 할 수 있겠습니다! 추가적으로 더 효율적인 방식도 있고 다양한 방식이 있으니 검색을 통해 찾아보시거나 직접 떠올려 보시면 큰 도움이 될 것이라고 생각합니다. 간단한 코드이나 제 코드를 첨부하도록 하겠습니다. 더보기 #include #include int main.. 2020. 7. 19. [BOJ #11728] 배열 합치기 BOJ #11728, 배열 합치기 문제입니다. 문제의 내용 자체는 간단합니다만 입력 데이터의 크기가 크고 시간 제한이 체감되는 문제입니다. 입력으로 정렬된 두 개의 배열이 주어지면 출력으로는 두 배열을 합쳐서 정렬한 배열을 출력하면 됩니다. 여러 개의 인덱스 변수를 동시에 다루는 방법으로 해결했습니다. 코드는 다음과 같습니다. 더보기 #include #include int main(void) { int N, M; scanf("%d %d", &N, &M); int *A = (int *)malloc(sizeof(int) * N); int *B = (int *)malloc(sizeof(int) * M); for (int i = 0; i < N; i++) scanf("%d", &A[i]); for (int i .. 2020. 7. 18. [BOJ #2231] 분해합 BOJ #2231, 분해합 문제입니다. 크게 어렵진 않은 문제이나, 새로운 접근 방법을 찾아내 공유할 겸 작성하게 되었습니다. 문제의 정의를 살펴 봅시다. a + a의 각 자릿수의 합 == b이면 a는 b의 생성자입니다. 처음에 이 관계가 잘 와닿지 않는데, a를 조작해서 b를 생성하므로 a가 b의 생성자라고 이해했습니다. 이런 사실들로부터 생각을 이끌어 보면, a에서 b를 구하는 것은 정말 쉽다는 것을 알 수 있습니다. 문제가 아무런 의미가 없게 되겠죠. 그렇지만 이 문제는 b에서 a를 구해야 하기 때문에 살짝 복잡해집니다. 왜냐하면 a == b이면서 동시에 a' == b일 수 있기 때문입니다. 이런 상황에서 가장 만만하게 써볼 수 있는 녀석이 완전탐색(Brute-Force)입니다. 멋있는 영어 이름도.. 2020. 7. 15. [BOJ #1252] 이진수 덧셈 BOJ #1252, 이진수 덧셈 문제입니다. 정답률은 28.3%로 상당히 낮습니다. 저 또한 문제의 세부 조건을 발견하지 못해 잠깐 헤맸습니다. 우선 이 문제는 크게 두 가지 방법이 있습니다. 첫 번째로 입력받은 이진수를 십진수로 변환하여 더하고, 다시 이진수로 변환하여 출력하는 방법이 있습니다. 두 번째로는 변환 없이 이진수 덧셈 자체를 구현하는 것이 되겠습니다. 첫 번째 방법은 어떻게 보면 더 효율적이고 더 빠른 방법일 수는 있겠으나, 문제의 의도는 아닐 것이라고 생각됩니다. 그리고 두 번째 방법으로 만들어보는 것이 실력적으로 더 큰 도움이 될 것입니다. 알고리즘은 동일하나, 이번 문제의 특성 상 C보단 Python으로 푸는 게 편리합니다. 저는 연습을 위해 일부러 C로 풀었지만 여기선 Python을.. 2020. 7. 14. [BOJ #2447] 별 찍기 - 10 BOJ #2447, 별 찍기 - 10 문제입니다. 이전에 해 오던 별 찍기랑은 꽤 다른 문제입니다. 이 문제의 핵심은 재귀(recursion)입니다. 문제에서 재귀라는 단어가 언급되기도 하였으므로 재귀를 이해하고 있는 사람이라면 어렵지 않게 풀 수 있을 것이라고 생각합니다. 입력으로는 3의 거듭제곱 수(3, 9, 27, ...)가 주어집니다. 출력으로는 N * N 크기의 패턴을 출력해야 합니다. 패턴은 이렇습니다. 우선 N == 3인 경우엔 다음과 같이 출력합니다. 이것이 base case가 됩니다. *** * * *** N > 3인 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N / 3) * (N / 3) 정사각형을 크기 N / 3의 패턴으로 둘러싼 형태가 됩니다. 따라서 N == 27인 경우 .. 2020. 7. 14. 이전 1 다음
