2025년 12월 4일 (목)
- 00:022025년 12월 4일 (목) 00:02 Post Correspondence Problem (역사 | 편집) [2,689 바이트] Pinkgo (토론 | 기여) (새 문서: 분류:계산 이론 개론 분류:컴퓨터 공학 상위 문서: Turing Machines ==개요== 해당 문서에서는 Post Correspondence Problem(PCP)에 대해서 설명한다. ==Definition of PCP== PCP는 도미노 개념에 기반하여 조직된 문제이다. 도미노란 아래와 같은 “위 문자열(top string)”과 “아래 문자열(bottom string)” 쌍을 의미한다: <math>[\frac{b}{ca}]</math>: 위 문...)
2025년 12월 1일 (월)
- 16:452025년 12월 1일 (월) 16:45 Independent Set (역사 | 편집) [547 바이트] Pinkgo (토론 | 기여) (새 문서: 분류:알고리즘 설계와 분석 분류:컴퓨터 공학 상위 문서: 알고리즘 설계와 분석 ==개요== Independent Set 문제는 아래와 같은 정의를 가진다. 입력: 그래프 <math>G=(V,E)</math>, 정수 <math>j</math> 질문: 서로 연결되지 않은 <math>j</math>개의 정점을 포함하는 집합이 존재하는가? 해당 문제는 Independent Set의 complement(여집합)가 Vertex Cover라...)
- 16:452025년 12월 1일 (월) 16:45 Vertex Cover (역사 | 편집) [641 바이트] Pinkgo (토론 | 기여) (새 문서: 분류:알고리즘 설계와 분석 분류:컴퓨터 공학 상위 문서: 알고리즘 설계와 분석 ==개요== ==Vertex Cover== Vertex Cover 문제는 아래와 같은 정의를 가진다. 입력: 그래프 <math>G=(V,E)</math>, 정수 <math>k</math> 질문: 최대 <math>k</math>개의 정점만 선택해서 모든 간선이 적어도 하나의 선택된 정점에 닿도록 만들 수 있는가? 해당 문제는 3-SAT <...)
- 16:422025년 12월 1일 (월) 16:42 Satisfiability Problem (역사 | 편집) [5,080 바이트] Pinkgo (토론 | 기여) (새 문서: 분류:알고리즘 설계와 분석 분류:컴퓨터 공학 상위 문서: NP-Completeness ==개요== SAT(Satisfiability Problem)는 컴퓨터 과학 이론에서 가장 유명한 NP-complete 문제이며, 전 세계의 알고리즘 전문가들이 빠른 알고리즘(다항시간)을 찾으려 했지만 실패했다. SAT를 빠르게 풀 수 있으면 P = NP가 되어버리며, NP 문제들이 전부 빠르게 풀려 암호...)
2025년 11월 25일 (화)
- 14:192025년 11월 25일 (화) 14:19 TriCache: A User-Transparent Block Cache Enabling High-Performance Out-of-Core Processing with In-Memory Programs (역사 | 편집) [362 바이트] Ahn9807 (토론 | 기여) (새 문서: 분류: USENIX OSDI {{Paper|title=TriCache: A User-Transparent Block Cache Enabling High-Performance Out-of-Core Processing with In-Memory Programs|author=Guanyu Feng and Huanqi Cao, Tsinghua University; Xiaowei Zhu, Ant Group; Bowen Yu, Yuanwei Wang, Zixuan Ma, Shengqi Chen, and Wenguang Chen, Tsinghua University|conference=OSDI|year=2022}} == 개요 ==) 태그: 시각 편집: 전환됨
2025년 11월 24일 (월)
- 05:142025년 11월 24일 (월) 05:14 NP-Completeness (역사 | 편집) [4,837 바이트] Pinkgo (토론 | 기여) (새 문서: 분류:알고리즘 설계와 분석 분류:컴퓨터 공학 상위 문서: 알고리즘 설계와 분석 ==개요==)
2025년 11월 21일 (금)
- 03:202025년 11월 21일 (금) 03:20 중화인민공화국 (역사 | 편집) [41,911 바이트] Pinkgo (토론 | 기여) (새 문서: 분류:교양 문서 분류:중국 문화와 역사 상위 문서: 중국 문화와 역사 ==개요== 해당 문서는 현재 중국 대륙을 지배하고 있는 중화인민공화국의 역사에 대해 다룬다. ==마오쩌둥== 중국 공산당이 러시아 혁명의 영향을 받아 발달하기 시작할 당시, 젊은 시절의 마오쩌둥은 중화민국#5·4운...)
2025년 11월 15일 (토)
- 04:102025년 11월 15일 (토) 04:10 Edit Distance (역사 | 편집) [16,376 바이트] Pinkgo (토론 | 기여) (새 문서: 분류:알고리즘 설계와 분석 분류:컴퓨터 공학 상위 문서: Dynamic Programming ==개요== ==각주==)
- 03:302025년 11월 15일 (토) 03:30 The Gas Station Problem (역사 | 편집) [3,568 바이트] Pinkgo (토론 | 기여) (새 문서: 분류:알고리즘 설계와 분석 분류:컴퓨터 공학 상위 문서: Dynamic Programming ==개요== Gas Station Problem은 아래와 같은 문제 정의를 가진다: 가정 1: 뉴욕에서 플로리다까지 가는 길에 주유소 <math>g_1, g_2, \cdots, g_n</math>이 있다. 가정 2: 각 주요소는 mile marker <math>m_i</math>에 위치해 있으며, 자동차는 한 번 주유로 R마일을 달릴 수 있다. 목표: 목적지까지 가기 위해...)
- 03:292025년 11월 15일 (토) 03:29 Binomial Coefficients (역사 | 편집) [3,762 바이트] Pinkgo (토론 | 기여) (새 문서: 분류:알고리즘 설계와 분석 분류:컴퓨터 공학 상위 문서: Dynamic Programming ==개요== 이항 계수(Binomial Coefficients)는 동적 프로그래밍의 고전적인 응용 중 하나이다. 이항 계수는 수학적으로 아래와 같이 정의된다: <math>\dbinom{n}{k}=</math> "n개 중에서 k개를 선택하는 방법의 수" 이항 계수는 흔히 조합(combination)이라고 불리며, 다양한 분야에 활용된다. 예를 들어 n...)
- 03:232025년 11월 15일 (토) 03:23 Fibonacci Numbers (역사 | 편집) [3,196 바이트] Pinkgo (토론 | 기여) (새 문서: 분류:알고리즘 설계와 분석 분류:컴퓨터 공학 상위 문서: 알고리즘 설계와 분석 ==개요== 해당 문단에서는 동적 프로그래밍 활용의 대표적인 예시들 중의 하나인 피보나치 수열을 통해서 동적 프로그래밍의 구현 방법에 대해 알아보는 것을 목표로 한다. ===Intuitive Version=== 피보나치 수열의 점화식 정의는 아래와 같다: <math>F_n=F...)
2025년 11월 14일 (금)
- 22:022025년 11월 14일 (금) 22:02 중화민국 (역사 | 편집) [28,215 바이트] Pinkgo (토론 | 기여) (새 문서: ==신해혁명과 중화민국의 건국== 섬네일|259x259픽셀|Figure 1. 쑨원 신해혁명의 계기가 되는 우창 봉기가 일어나기 전, 혁명 찬성론자들은 비밀 조직을 결성하며 힘을 길렀다. 대표적인 혁명론자인 쑨원은 1905년 일본에서 중국동맹회를 창설하였으며, 민족주의, 민권주의, 민생주의를 기반으로 하는 삼민주의(三民主義)를 그들의 사상적 기반으...)
2025년 11월 7일 (금)
- 03:162025년 11월 7일 (금) 03:16 청나라/역사 (역사 | 편집) [48,060 바이트] Pinkgo (토론 | 기여) (새 문서: ==개요== ===후금의 건국=== 섬네일|337x337픽셀|Figure 3. 청나라 황실 의복 여진족은 본래 통일된 민족이 아니라, 여러 부족 집단으로 나뉘어져 있었다. 하지만 16세기 후반, 명의 통제력 약화와 무역 제재로 여진 사회 내부에 경제·군사적 긴장이 축적되었고, 이 상황을 틈타 누르하치(ᠨᡠᡵᡤᠠᠴᡳ, Nurhaci)는 만주의 여진족들 사이...)
2025년 11월 1일 (토)
- 19:472025년 11월 1일 (토) 19:47 Turing Machines (역사 | 편집) [27,391 바이트] Pinkgo (토론 | 기여) (새 문서: 분류:계산 이론 개론 분류:컴퓨터 공학 상위 문서: 계산 이론 개론 ==개요== ==각주==)
2025년 10월 31일 (금)
- 03:432025년 10월 31일 (금) 03:43 Dynamic Programming (역사 | 편집) [12,244 바이트] Pinkgo (토론 | 기여) (새 문서: 분류:알고리즘 설계와 분석 분류:컴퓨터 공학 상위 문서: 알고리즘 설계와 분석 ==개요== 동적 프로그래밍(Dynamic Programming)은 좌우 순서로 배열된 문제들<ref>문자열, 수열 등에 관한 문제이다.</ref>에 대한 최적화 문제를 효율적으로 푸는 방법이다. 동적 프로그래밍의 핵심적인 아이디어는 복잡한 문제를 작은 하위 문제(subproblem)...)
2025년 10월 30일 (목)
- 05:072025년 10월 30일 (목) 05:07 Pumping Lemma (역사 | 편집) [10,004 바이트] Pinkgo (토론 | 기여) (새 문서: DFA는 유한한 개수의 상태(state)만을 가진다. 만약 DFA가 무한한 문자열을 인식하는 언어 L 을 인식한다고 할때, 충분히 긴 문자열을 입력하면, 반드시 같은 상태를 두 번 이상 방문하게 된다. 이때 반복된 부분을 여러 번 반복(pumping)할 수 있고 여전히 DFA가 받아들이므로, DFA가 인식하는 모든 정규언어에는 특정한 반복 구조가 존재한다. 이 논리에서 pumping lemma가 출발...)
2025년 10월 26일 (일)
- 05:542025년 10월 26일 (일) 05:54 Pushdown Automaton (역사 | 편집) [13,209 바이트] Pinkgo (토론 | 기여) (새 문서: 분류:계산 이론 개론 분류:컴퓨터 공학 상위 문서: Context-Free Languages ==개요== 정규 언어를 다루기 위해서는 FA(Finite Automaton)으로 충분하지만, 그보다 더 일반적인 언어인 CFG(Context-Free Languages)를 다루기 위해서는 PDA(Pushdown Automaton)가 사용된다. PDA는 FA의 한계를 보완하기 위해서 추가적인 기억 장치인 stack을 활용하며, 이...)
- 02:092025년 10월 26일 (일) 02:09 CYK Algorithm (역사 | 편집) [3,654 바이트] Pinkgo (토론 | 기여) (새 문서: 분류:계산 이론 개론 분류:컴퓨터 공학 상위 문서: Context-Free Languages ==개요== CNF으로 변환된 문법을 기반으로, 주어진 문자열이 언어 <math>L</math>에 속하는지를 결정론적으로(deterministic) 판단할 수 있다. 이때 recognizer라는 개념이 등장하는데, recognizer는 문자열 <math>w</math>를 입력받아, 그 문자열이 언어 <math>L</math>에 속하는...)
- 01:422025년 10월 26일 (일) 01:42 Chomsky Normal Form (역사 | 편집) [3,887 바이트] Pinkgo (토론 | 기여) (새 문서: 분류:계산 이론 개론 분류:컴퓨터 공학 상위 문서: Context-Free Languages ==개요== CNF(Chomsky Normal Form)는 CFG를 더욱 간단하고 증명하기 쉽게 바꾼 표준 형식이다. 모든 CFG는 CNF와 동등한 문법으로 바뀔 수 있으며, CFG가 다음 세 가지의 규칙만 가지면 CNF에 해당한다: # <math>A \rightarrow BC</math><ref>이때 B, C는 시작 기호 S가 아니다...)
2025년 10월 25일 (토)
- 19:182025년 10월 25일 (토) 19:18 Backtracking (역사 | 편집) [20,609 바이트] Pinkgo (토론 | 기여) (새 문서: 분류:알고리즘 설계와 분석 분류:컴퓨터 공학 상위 문서: 알고리즘 설계와 분석 ==개요== 백트래킹은 탐색 공간(search space) 의 모든 가능한 구성을 체계적으로 탐색하는 방법dlek. 하지만 모든 문제에 똑같이 적용되는 알고리즘이 아니라, 각 문제에 맞게 커스터마이징해야 하는 일반적인 틀(general framework)이다. 이때 백트래킹은 결...)
2025년 10월 24일 (금)
- 14:412025년 10월 24일 (금) 14:41 Shortest Paths (역사 | 편집) [14,452 바이트] Pinkgo (토론 | 기여) (새 문서: 분류:알고리즘 설계와 분석 분류:컴퓨터 공학 상위 문서: 알고리즘 설계와 분석 ==개요== 해당 문서에서는 그래프에서의 최단 경로(shortest path)를 찾는 알고리즘을 설명한다. ==Applications for Shortest Paths== 그래프 상 두 노드 간 최단 경로를 찾는 문제는 실제 여러 분야에서 나타나며, 아래와 같다: * 교통 문제(Transportation prob...)
- 01:562025년 10월 24일 (금) 01:56 청나라 (역사 | 편집) [9,776 바이트] Pinkgo (토론 | 기여) (새 문서: 분류:교양 문서 분류:중국 문화와 역사 상위 문서: 중국 문화와 역사 ==개요== 해당 문서에서는 명(明, Ming)나라가 어떻게 형성되고, 세계에 어떤 영향을 미쳤는가를 설명한다. ==역사== ==각주==)
2025년 10월 17일 (금)
- 19:122025년 10월 17일 (금) 19:12 Grammars (역사 | 편집) [10,363 바이트] Pinkgo (토론 | 기여) (새 문서: 분류:계산 이론 개론 분류:컴퓨터 공학 상위 문서: Regular Languages ==개요== ==각주==)