분류 전체보기 (143) 썸네일형 리스트형 66. Inclusion-Exclusion Principle 포함-배제의 원리(Inclusion-Exclusion Principle)는 각 집합의 원소의 수를 이용하여 그것들의 합집합의 원소의 수를 구할 때 사용되는 원리이다. 포함-배제의 원리에 따르면 n개의 집합 A1,A2,…An의 합집합의 원소의 개수는 다음과 같이 구할 수 있다. |n⋃i=1Ai|=∑I⊂U(−1)|I|+1|⋂i∈IAi| 이것을 해석하면, n개의 집합의 합집합의 원소의 개수는 (집합 1개의 원소의 개수의 합)−(집합 2개의 교집합의 원소의 개.. 63. Nim Game & Sprague-Grundy Theorem 님 게임(Nim Game)은 간단하면서도 게임 이론에서 중요한 역할을 하는 게임으로, 여기서 사용된 전략을 다른 많은 게임에 응용해서 적용할 수 있다. 님 게임은 0개 이상의 돌이 있는 n개의 더미에서 번갈아 가면서 돌을 가져가는 방식으로 차례를 진행한다. 가져가는 돌의 개수에는 제한이 없지만 한 차례에는 하나의 더미에서만 돌을 가져갈 수 있다. 더이상 돌을 가져갈 수 없는 플레이어가 게임에서 지게 된다. 님 게임에서 각각의 더미에 남아 있는 돌의 개수를 [x1,x2,…xn]이라고 하면 이 게임의 상태를 님 합(Nim Sum)으로 분류할 수 있다. 님 합 s=x1⊕x2⊕…⊕xn이며, ⊕는 XOR 연산을 .. 62. Game Theory 게임 이론(Game Theory)은 상호 의존적이고 이성적인 의사 결정을 다루는 이론이다. 게임(Game)은 각각의 행위자들이 일정한 전략을 가지고 최고의 보상을 얻기 위해 벌이는 행위를 말하며, 알고리즘 문제에 적용할 경우 게임에서 승리하거나 최대한 좋은 결과를 얻기 위해 적절한 전략을 가지고 플레이하는 것을 의미한다고 할 수 있다. 게임 이론에서 모든 참가자는 최선의 선택을 하며 다른 참가자들 역시 최선의 선택을 할 것이라는 사실을 알고 있다고 간주한다. 또한 다음과 같은 사항이 존재한다. 모든 참가자는 정보를 가지고 있다. 게임의 초기 상태가 존재한다. 게임의 순서와 정해진 규칙이 존재한다. 참가자는 가능한 선택 중 어떤 것이든지 할 수 있다. 대부분의 게임은 다음과 같은 추가적인 제한을 갖는다. .. 61. Sum of Squares 이번 글에서는 임의의 자연수 p를 최소 개수의 제곱수의 합으로 나타내는 문제를 살펴본다.먼저 p를 제곱수 1개의 합으로 나타낼 수 있으려면 x2=p를 만족하는 정수 x가 존재해야 한다는 사실은 쉽게 알 수 있다. p가 처음부터 제곱수였다면 p를 제곱수 1개의 합으로 나타낼 수 있다.다음으로 p를 제곱수 2개의 합으로 나타낼 수 있는 경우를 알아본다. 먼저 임의의 제곱수를 4로 나눈 나머지를 구하면 다음과 같다:(2k)2=4k2(2k+1)2=4k2+4k+1=4k(k+1)+1그 밖의 경우가 존재하지 않으므로 제곱수를 4로 나눈 나머지는 0 또는 1이고, 제곱수 2개를 더한 결과를 4로 나눈 나머지는 0,1,2가 될 수 있다. 따.. 60. Strassen's Algorithm 스트라센 알고리즘(Strassen's Algorithm)은 행렬 곱셈을 Θ(n3)보다 빠른 시간에 하는 알고리즘이며 카라츠바 알고리즘과 유사하게 분할 정복을 이용하여 시간복잡도를 줄인다. 크기가 n×n인 두 행렬 A와 B가 존재하고, A와 B의 곱이 행렬 C일 때 스트라센 알고리즘의 작동 방식은 다음과 같다. 먼저 각 행렬을 4등분해서 다음과 같이 나눈다. $$A = [A1,1A1,2A2,1A2,2], B = [B1,1B1,2B2,1B2,2], C = \begin.. 59. Gaussian Elimination 가우스 소거법(Gaussian Elimination)은 연립일차방정식의 해를 구할 때 사용되는 행렬 연산이며, 그밖에도 다양한 방법으로 응용이 가능하다. 가우스 소거법은 행렬에 다음과 같은 세 가지 연산을 수행한다. 첫 번째 연산을 두 번째 연산과 세 번째 연산의 조합으로 대체할 수 있기 때문에 두 가지 연산이라고 해도 상관없지만 편의상 세 가지로 구분했다.i행과 j행을 서로 바꾼다.i행의 각 성분에 0이 아닌 실수 k를 곱한다.i행에 j행을 더한다.가우스 소거법의 목표는 행렬의 랭크와 독립이 아닌 열 사이의 상관관계를 유지하면서 행렬을 행사다리꼴로 만드는 것이다. 이와 관련하여 다음 용어들을 알아 두는 것이 좋다.피벗(Pivot, Leading Entry)은 각 행에서 처음으로.. 58. Rank of Matrix 행렬의 랭크를 쉽게 이해하기 위해서는 벡터의 독립에 대해서 알 필요가 있다. 두 벡터 →u,→v가 다음과 같은 조건을 만족할 경우 서로 독립(Independence)이라고 한다.a→u+b→v=→0→a=b=0이것을 다르게 해석하면 두 개의 벡터가 독립일 때 그 벡터들을 이용해서 공간 내의 모든 좌표를 나타낼 수 있는 2차원 공간이 존재한다는 의미가 된다. 이와 비슷하게 n개의 벡터 →v1,→v2,…→vn가 다음과 같은 조건을 만족할 경우 서로 독립이라고 한다.$$a_1\vec{v_1}+a_2\vec{v_2}+\ldots+a_n\vec{v_n}=\vec{0} \to a_1=a_2=\ldo.. 57. Matrices 이번 글에서는 선형대수학(Linear Algebra)에 대한 내용을 다룬다. 선형대수학은 덧셈과 곱셈을 통한 변화에 초점을 두는 수학의 한 분야이며, 적절한 표현을 이용하여 선형방정식의 해를 구하는 것을 핵심으로 하고 있다. 선형대수학에서 중요하게 다뤄지는 개념으로 행렬(Matrices)과 벡터(Vectors)가 존재하는데, 벡터에 관한 자세한 내용은 카테고리 G에서 다루고 여기서는 행렬에 관한 내용 위주로 다루기로 한다. 행렬은 수나 식을 직사각형 모양으로 배열한 것으로 행(Row, 가로줄)의 수가 n, 열(Column, 세로줄)의 수가 m인 경우 n×m 행렬이라고 한다. 또한 각각의 수나 식을 행렬의 성분(Entry)이라고 하고, 각각의 행을 행벡터(Row Vector), 각각.. 이전 1 ··· 8 9 10 11 12 13 14 ··· 18 다음 목록 더보기