CS를 위한 이산수학 정리

이산수학

 

실수처럼 연속성이 있는 것들이 아니라 주로 정수, 논리 연산같이 서로의 값들이 연속적이지 않고 뚝뚝 떨어져 있거나 구분되어 '셀 수 있는' 것들을 주로 연구하는 학문.  이산수학에 포함된 개념과 기호들은 컴퓨터과학에서 알고리즘, 프로그래밍 언어 이론, 암호학, 계산이론 등의 문제를 연구하는 데 유용함.  이산수학이 컴퓨터과학의 언어인만큼 습득하고 정리할 필요가 있음

 

 

집합론

 

그룹의 정의: 일련의 원소와 이들 원소 간의 연산이 특정 규칙을 만족할 때 형성되는 수학적 개념.  그룹은 집합과 연산이 다음 조건을 만족할 때 형성됨.

1. 닫힘(Closure): 모든 연산의 결과가 집합에 속함.
2. 결합법칙(Associativity):  (a⋅b)⋅c=a⋅(b⋅c)가 모든 a,b,c에 대해 성립.
3. 항등원(Identity Element): 항등원이 존재. e⋅a=a⋅e=a가 모든 a에 대해 성립.
4. 역원(Inverse Element): 모든 원소 a에 대해 a⋅a^−1 = a−1⋅a = e인 역원이 존재.

항등원과 역원의 존재는 그룹의 안정성을 더해줌.

 

어떤 연산을 포함하는 방정식이 있을때, 각 항에 역원을 결합시키면, 항등원이 발생하며,닫혀있다면 이로인해 해당 연에는 해가 있음을 보장받을 수 있음. (갈루아 이론)

 

2^0 = 1인 것은, 2^m*2^n = 2^m+n인 법칙을 유지하기 위해서, 덧셈의 항등원 0을 포함한 2^0이 곱셈의 항등원인 1의 값을 가짐이 타당하기 때문

 

후위표현식

 

 

 

그래프이론

• 그래프 : 꼭짓점(vertex, node)과 간선(edge)으로 이루어진 도식. 객체 간의 관계를 모델링하는 기법.
• 벡터와의 관계성 : 서로 다른 수학적 개념으로 그래프 이론은 객체 간의 관계를 모델링, 벡터는 방향과 크기를 가진 데이터 구조. 하지만, 선형대수적으로 표현과 연산할 수 있다는 공통분모가 있음.
  • 벡터 : The main need for using vectors arises from the desire to represent and manipulate quantities that possess both magnitude and direction in a concise and unified manner. Vectors allow us to combine multiple attributes or components into a single mathematical entity

• 주요개념
  • 연결성(connectivity): 그래프의 두 꼭짓점을 연결하는 경로가 있는지 여부를 나타냅니다.
  • 경로(path): 두 꼭짓점을 연결하는 간선들의 순서열입니다.
  • 사이클(cycle): 시작 꼭짓점과 끝 꼭짓점이 같은 경로입니다.
  • 트리(tree): 사이클이 없는 연결 그래프입니다
• 그래프의 표현
  • 꼭짓점의 집합 V와 변의 집합 E라고할때 그래프 G는 아래와 같은 튜플이다. 
    • G=(V,E) /  ​V={1,2,3,4,5,6}  / E={{1,2},{1,5},{2,3},{2,5},{3,4},{4,5},{4,6}}​

•  오일러회로
• 한붓그리기

 

확률과 조합

 

• 중복순열 : 서로 다른 n개의 원소를 가지는 어떤 집합에서 중복과 상관없이 순서에 상관있게 r개의 원소를 선택하거나 혹은 나열하는 것이며

<중복순열을 모두 출력하는 코드>

import java.util.*;

class Solution{  Stack<Integer> pm = new Stack<>(); // 중복순열을 차례로 저장할 자료구조

public void DFS(int L, int n, int r){

if(L == r){for(int x : pm) System.out.print(x+" "); System.out.println();} }} // level이 목표치 까지 도달하면 stack을 출력

else{{

for(int i = 1; i <= n; i++){

pm.push(i);

DFS(L+1, n, r); // level별로 새로운 숫자를 추가하고 backtracking할때 pop하여 원복시키기

pm.pop();

} }}

 

• 순열(Permutation) :  서로 다른 n개의 원소를 가지는 어떤 집합에서 '중복 없이' '순서에 상관있게' r개의 원소를 선택하거나 혹은 나열하는 것.서로 다른 n개를 r개의 격자에 배열하는 경우의 수와 동일. n*n-1*n-2 ... *n-r

중복순열과 동일한 로직으로 작성하나, chk list를 인수로 추가하여서 stack list에 add 할때마다 chk list에 1로 표시하고 stack list에서 pop할때마다 0으로 표시해서 돌림.

 

class Solution{

Stack<Integer> pm = new Stack<>();

public void DFS(int L, int n, int r, int[] ch){

if(L == r){
for(int x : pm) System.out.print(x+" "); System.out.println();

} }

} else{

for(int i = 1; i <= n; i++)

{ if(ch[i] == 0){

ch[i] = 1; pm.push(i); DFS(L+1, n, r, ch); ch[i] = 0; pm.pop()

 

}}}

 

 

 

• 조합(Combination) : 서로 다른 n개의 원소를 가지는 어떤 집합에서 '중복 없이' '순서에 상관없이' r개의 원소를 선택하거나 혹은 나열하는 것. 순열의 경우의 수에서 r개의 배열하는 경우의 수 r!로 나눈 것과 동일.

중복조합과 동일하게 작동하나, parameter에 for문 순회를 시작할 숫자를 추가하여 1. 레벨의 깊이 2. for문의 시작index를 조정하여 123,124,125...134,135...145 와 같이 tree를 조정한다.

 

class Solution{

Stack<Integer> combi = new Stack<>(); public void DFS(int L, int s, int n, int r){

if(L == r){
for(int x : combi) System.out.print(x+" "); System.out.println();

} }

} else{

} }

for(int i = s; i <= n; i++){ combi.push(i);

DFS(L+1, i+1, n, r); combi.pop();

 

• 이항정리(파스칼의 삼각형)

이항정리란, (a+b)^n(단, n은 음이 아닌 정수)의 꼴을 전개할 때 쓰이는 정리이다. 파스칼의 삼각형은 이항계수를 삼각형 모양으로 나열한 것. 이항정리에서 각 항은 a와 b 모두 돌아가면서 곱의 연산에 참여하게 되며 결과값이 요소 간 순서가 상관없으므로 같은 것이 있는 순열문제이다. 즉,  a^r*b^n−r의 계수는 곧 r개의 a와 (n−r)개의 b 이렇게 총 n개의 문자를 배열하는 경우의 수와 같다. 조합인 nCr과 같음. 그러므로 아래의 공식이 성립한다.

 

이항정리

 

파스칼의 삼각형

소수론

 

에라토스테네스의 체

특정 범위 내에서 모든 소수를 찾기 위한 간단하면서도 효율적인 알고리즘

1. 초기화: 2부터 n까지의 모든 정수를 포함하는 리스트를 만듭니다. 여기서 n은 소수를 찾고자 하는 범위의 최대값입니다.
2. 소수 찾기: 현재 리스트에서 가장 작은 수를 찾습니다. 이 수는 소수입니다.
3. 배수 제거: 찾은 소수의 모든 배수를 리스트에서 제거합니다.
4. 반복: 리스트에 더 이상 배수를 제거할 수 없을 때까지 2번과 3번 과정을 반복합니다.
5. 완료: 리스트에 남은 수들이 소수입니다.

for (int i = 2; i <= n; i++) { prime[i] = true; } / for (int p = 2; p * p <= n; p++) {  if (prime[p]) {. for (int i = p * p; i <= n; i += p) { prime[i] = false; } } }

 

 

유클리드 호제법

최대공약수(the greatest common divisor (GCD))를 구하는 알고리즘으로 반복문이나 재귀함수로 구현가능.

•  a=bq+r, gcd(a, b)=gcd(b, r),

1. 입력받은 두 수 중에서 큰 수를 작은 수로 나눕니다.
2. 나머지를 구합니다.
3. 나머지가 0이 되면, 나누는 수가 두 수의 최대공약수가 됩니다.
4. 나머지가 0이 아니라면, 나누는 수를 다시 나누어지는 수로 놓고, 나머지를 새로운 나누는 수로 놓고 1단계로 돌아가 반복합니다.

재귀함수 : public class GCD { public static int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); }

반복문 : public static int gcd(int a, int b) { while (b != 0) { int temp = b; b = a % b; a = temp; } return a; }

 

피보나치수열

<문제풀이법>

• 예상과 확인(시행착오법) :  문제의 답을 예상해 보고, 그 답이 문제의 조건에 맞는지 확인해 보는 과정을 반복하여 문제를 해결해 나가는 전략
• 규칙성을 갖는 수의 나열에서 천문학적인 순서에 있는 값 추론하기.
• Divide and conquer :  breaking down a problem into smaller subproblems, solving them independently, and then combining their solutions to solve the original problem
• 점화식 ; 함수의 결과값을 초기값으로 사용. 재귀함수 혹은 DP 사용