전체 글 썸네일형 리스트형 튜링의 불완전성 정리 증명 ※ 혼자 공부한 내용을 정리한 글입니다. 엄밀한 내용이 궁금하다면 참고 문헌을 읽어 보길 권합니다. 1. 불완전성 정리란? 힐베르트는 수학 체계가 완전하다고 믿었다. 즉 모든 참인 증명은 수학 체계의 공리에서 유도될 수 있으며 따라서 공리에서부터 출발하여 모든 참인 증명을 기계적으로 만들 수 있다고 여겼다. 하지만 괴델이 자연수의 체계에 대해 자연수 체계 속에서 증명될 수 없지만 체계 외부에서 보면 참인 명제가 존재한다는 것을 증명했으며, 이를 불완전성 정리라고 한다. 간략한 증명 방법은 다음과 같다. G = G는 증명불가능하다. 이러한 명제 G가 존재한다고 가정하자. 명제 G는 거짓일 수 없으므로 참이지만 증명불가능한 명제가 되며, 곧 공리계의 불완전성을 의미한다. 위 명제는 명제 속에서 자기 자신을 .. 더보기 백준 2673번 교차하지 않는 원의 현들의 최대집합 http://icpc.me/2673 2673번: 교차하지 않는 원의 현들의 최대집합 평면상에 있는 원의 둘레에 100개의 점이 일정한 간격으로 시계방향으로 번호가 1, 2, ... 100으로 붙여져 있다. 이 점들을 끝점으로 갖는 N개의 선분(원의 현)이 입력으로 주어질 때, 이들중에서 서 www.acmicpc.net 풀이 원의 현이라고 하면 되게 복잡해지고 풀기 싫어집니다. 하지만 두 현의 교차 여부만 중요하다는 점을 잘 생각해 보면 현을 수평선상의 구간으로 생각해도 문제가 없다는 것을 알 수 있습니다. 두 현의 교차하려면 각 현을 나타낸 두 구간이 겹치면서 한 구간이 다른 구간에 포함되지 않아야 합니다. 아래 그림은 예제를 구간으로 나타낸 모습입니다. 여기까지 왔으면 DP로 문제를 풀 수 있습니다. .. 더보기 ABC 228 E Integer Sequence Fair 풀이 오늘 대회 중에 아쉽게 못 풀었던 문제입니다. 페르마의 소정리를 안다면 어렵지 않게 풀 수 있고, 좋은 문제인지는 잘 모르겠지만 개인적으로 이 문제를 풀며 몇 가지를 배우게 되어 정리할 겸 풀이를 작성하려 합니다. 문제 https://atcoder.jp/contests/abc228/tasks/abc228_e E - Integer Sequence Fair AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 1 이상 K 이하의 자연수가 N개 있는 모든 배열에 1 이상 M 이하의 가치를 매기는 경우의 수를 $Q = 99824435.. 더보기 백준 17106번 빙고 http://icpc.me/17106 17106번: 빙고 한 줄에 5개의 글자, 총 5줄을 출력한다. 각 줄은 순서대로 빙고판의 각 행을 나타낸다. 색칠된 칸은 "#", 색칠되지 않은 칸은 "."로 따옴표 없이 나타낸다. 예를 들어 A1, C3, C4만 색칠하려면 다음과 www.acmicpc.net 풀이 25개의 빙고 칸 각각을 색칠하거나 색칠하지 않을 수 있으므로 빙고 칸을 채우는 경우의 수는 $2^{25}$가지입니다. 모든 경우를 살펴보며 각 경우의 수마다 모든 칸이 올바르게 색칠되었는지를 체크하는 코드를 작성하면 정답을 찾을 수 있습니다. 다소 문제가 되는 칸은 B5입니다. 다른 칸들은 모두 빙고판의 상태를 통해 올바르게 색칠되었는지 알 수 있지만 이 칸은 그렇지 않습니다. B5가 참이라고 가정하고.. 더보기 백준 4828번 XML http://icpc.me/4828 4828번: XML 인터넷프로그래밍 교수 이다솜은 XML이야말로 세상을 바꿀 혁신적인 언어라고 믿으며, 항상 학생들에게 XML의 장점을 어필한다. 그러나 잘못 사용되었다가는 지구를 파괴할 수도 있는 무시무시 www.acmicpc.net 풀이 코드를 한 글자씩 읽으며 현재 상태를 저장하는 열거형 변수 now의 값과 현재 글자에 따라 적절히 처리해주었습니다. 상태가 TAG이면 태그를, AMPERSAND이면 & 다음을 읽고 있다는 의미이며 둘 다 해당되지 않는 상태는 NORMAL으로 나타냅니다. 문제가 있는 코드를 만나면 상태를 ERROR로 지정하고 읽기를 중단합니다. 코드를 모두 읽은 후 context 스택이 비었는지, 아직 태그나 & 뒤를 읽고 있는지 여부를 추가적으로 .. 더보기 신기한 정렬 알고리즘 생활코딩에서 신기한 정렬 알고리즘을 접했습니다. 이게 왜 되지? 싶지만 놀랍게도 오름차순으로 잘 정렬됩니다!! 논문 링크도 있길래 읽어 보았습니다. 아래는 위 논문을 참고한 알고리즘 정당성 증명입니다. 초기 배열에 같은 수가 없다고 가정하고 작성했지만, 있어도 큰 차이는 없습니다. 정당성 증명 위 알고리즘을 그대로 구현하고, 과정을 확인하기 위해 swap 직후마다 배열 전체를 출력하는 코드를 추가했습니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #include using namespace std; int arr[1000]; void print(int* a, int n) { for (int i = 1; i 더보기 세그먼트 트리 라이브러리 개발(C++) #1 지금까지는 세그먼트 트리 문제 풀 때마다 새로 구현했었는데, 오늘 엉겁결에 세그먼트 트리 라이브러리를 개발해 보았습니다. 지금까지 사용해 본 C++ STL을 떠올리면서 최대한 비슷하게 만드려 노력했는데 충분히 쓰기 편한지는 모르겠네요ㅠㅠ 구간 쿼리와 점 업데이트를 처리할 수 있고 구간 업데이트는 아직 처리하지 못합니다. 멤버 변수 T* tree - 세그먼트 트리를 나타낼 배열(을 동적할당할 포인터)입니다. T* arr - 세그먼트 트리에 저장할 원소들을 담은 배열(을 동적할당할 포인터)입니다. int size, cap - 각각 원래 배열의 크기, 세그먼트 트리 배열의 크기를 나타냅니다. T(*oper)(T, T) - 세그먼트 트리의 리프 노드가 아닌 노드의 값은 두 자식 노드의 값을 덧셈, min/max.. 더보기 백준 20051번 Zagrade http://icpc.me/20051 20051번: Zagrade It is well known that the Central Intelligence Agency is tasked with gathering, processing and analyzing national security information. It is also suspected that they own quite large collections of commonly-used computer passwords and are developing some q www.acmicpc.net 문제 인터랙티브 문제입니다. 길이가 짝수인 정수 $N$이고 여는 괄호( '(' )와 닫는 괄호( '(' )의 개수가 같은 문자열이 있을 때, ? s e 쿼리로.. 더보기 이전 1 2 3 4 다음
