[이산수학] 그래프

1. 주요 용어G = (V,E) → 그래프 G는 꼭지점(V)와 변(E)들로 구성되어있다는 의미입니다. 변은 두 꼭지점을 연결하는데 이를 이산수학에서는 변에 의해 발생되었다고 표현합니다.연결된 두 꼭지점은 서로 인접한다고 표현합니다.벙렬변이란 두 꼭지점을 연결하는 변이 복수개 있을 때입니다.루프란 동일한 꼭지점을 연결하는 변입니다. 즉 꼭지점(V1) 에서 꼭지점(V1)으로 갈 때입니다.고립된 꼭지점이란 어떠한 변도 연결되지 않은 꼭지점을 의미합니다. 예제는 아래와 같습니다. 예제2)1) 방향 그래프와 무향그래프변이 방향을 가지고 있는 그래프를 방향 그래프라고 하며 변이 방향을 가지고 있지 않은 그래프를 무향 그래프라고합니다.위 그림에서 좌측이 방향그래프, 우측이 무향그래프입니다.2) 단순 그래프와 다중 그..

• format_list_bulleted CS(Computer Science) 이론/이산수학
• · 2024. 5. 22.
• textsms

[알고리즘] 그래프 알고리즘

1. 최소 신장 트리1) 정의신장트리란 가중 무방향 그래프에서 모든 정점을 포함하는 트리를 의미합니다. 즉 정점이 n개라면 트리에는 n-1개의 간선이 존재합니다.  이 중 최소(비용) 신장 트리는 아래와 같은 정의를 만족하는 트리입니다.2) 최소 신장 트리를 구하는 알고리즘모든 간선 중에서 정점을 모두 연결하면서 가중치의 합을 가장 작게 만드는 (n-1)개의 간선을 고르는 과정이라고 할 수 있습니다. Greedy_MST ( G ) { T ← Ø ; // 최소 신장 트리의 간선 집합 while ( T가 신장 트리를 만들지 않았음 ) { 최선의 간선 (u, v) 선택; T ← T ∪ { (u, v) }; } return (T); }위 코드에서 최선의 간선이라는 것은 사이클을 형성하지 않으며 ..

• format_list_bulleted CS(Computer Science) 이론/알고리즘
• · 2024. 5. 20.
• textsms

[디자인 패턴] MVVM 패턴

1. MVVM 패턴이란?MVVM은 Model-View-ViewModel의 약자로, 디자인 패턴 중 하나입니다. 주로 WPF 및 Xamarin과 같은 XAML 기반의 UI 프레임워크에서 사용되며, 사용자 인터페이스를 개발하는 데 유용합니다. 이 패턴은 UI를 비즈니스 로직과 분리하여 관리하기 위해 만들어졌습니다.2. 구성 요소1) Model애플리케이션의 비즈니스 로직과 데이터를 처리하는 부분입니다. 데이터의 유효성 검사, 저장 및 검색 기능 등을 담당합니다.2) View사용자에게 표시되는 UI 부분으로, XAML 파일이 주로 담당합니다. 데이터 바인딩을 통해 ViewModel의 상태를 보여주고, 사용자 입력을 ViewModel에 전달합니다.3) ViewModelView와 Model 사이에서 중개자 역할을 ..

• format_list_bulleted CS(Computer Science) 이론/디자인패턴
• · 2024. 5. 17.
• textsms

[알고리즘] 그래프의 기본 개념과 순회

1. 그래프란? 1) 그래프에서 사용되는 주요 용어1] 인접, 부수두 정점 x,y 사이에 간선이 있으면 정점 x와 y는 인접한다고 하며, 해당간선은 정점 x와 y에 부수되었다고 합니다.2] 부분 그래프원래의 그래프에서 일부의 정점이나 간선을 제외하여 만든 그래프를 부분 그래프라고 합니다. 위 그림에서 G2는 G1의 부분 그래프라고 할 수 있습니다.3] 경로그래프에서 정점 v1으로부터 vn까지의 경로란 간선 (v1,v2), (v2,v3),....,(v(n-1),vn) 으로 연결된 v1,v2,...,vn을 의미하며 이 때 경로상의 존재하는 간선의 개수를 경로의 길이라고 합니다.4]차수해당 정점에 부수된 간선의 수를 의미하며, 방향 그래프에서는 이러한 차수를 세분화하여 정점으로 들어오는 간선의 수를 진입차수라..

• format_list_bulleted CS(Computer Science) 이론/알고리즘
• · 2024. 5. 13.
• textsms

[이산수학] 부울대수

1. 논리게이트1) 기본 논리게이트1] AND 게이트2] OR 게이트3] NOT 게이트2) 응용 논리게이트1] NAND 게이트2] NOR 게이트3] XOR 게이트4] XNOR 게이트2. 부울대수1) 부울식부울식은 다음과 같이 순환적으로 정의합니다.2) 부울대수의 기본정리 쌍대에 대한 내용은 아래에서 나옵니다. 앞선 글에서 이산수학 논리부분과도 연결되는 부분이 있습니다. 논리에 대한 글은 아래를 참고하시면 됩니다.[이산수학] 논리 (tistory.com) [이산수학] 논리1. 명제참과 거짓을 구별할 수 있는 문장이나 수학적 식을 명제라고합니다. 즉 주관적인 값이 아닌 객관적인 값이 명제가 됩니다.명제가 타당한 경우 참 또는 T(True)라고 하고 명제가 타당하지 않zero-week.tistory.com 위..

• format_list_bulleted CS(Computer Science) 이론/이산수학
• · 2024. 5. 9.
• textsms

[이산수학] 함수

1. 함수의 정의이산수학에서 함수의 정의는 아래와 같습니다. 이를 그림으로 표현하면 아래와 같습니다.1) 상수함수와 항등함수함수의 상등이란 아래를 만족하는 것을 의미합니다. 2. 전사, 단사, 역함수, 합성함수1) 전사함수전사 함수란 공역과 치역이 같은 경우를 의미합니다.공역은 치역의 부분 집합인데치역이 가장 커질 수 있는 경우가 공역과 치역이 같은 경우입니다. 쉽게 말해서 X의 집합의 전체를 Y의 부분집합 전체에 보낸다고 생각하시면 됩니다. 이를 그림으로 표현하면 아래와 같습니다.구체적으로 표현하면 아래와 같습니다. 2) 단사함수단사 함수의 정의는 아래와 같습니다. 즉 X집합에 있는 임의의 원소 x에 대해 f(x)는 모두 달라야 한다는 뜻입니다.구체적인 예는 아래와 같습니다.3) 전단사 함수전단사 함수..

• format_list_bulleted CS(Computer Science) 이론/이산수학
• · 2024. 5. 6.
• textsms

[이산수학] 관계

1. 곱집합집합 A와 B의 곱집합 A x B는 A의 원소와 B의 원소의 모든 순서쌍들의 집합입니다.즉 A의 원소와 B의 원소를 하나의 집합에 넣은 것입니다.따라서 아래처럼 표현할 수 있습니다.2. 관계 3. 관계의 표현1) 화살표 도표 예제1)y>x라는 것은 B의 원소가 A원소보다 큰 값의 집합을 의미합니다. 따라서 (1,2)이며 화살표 도표에서는 위처럼 표시합니다. 예제2)이 예제도 A의 원소와 B의 원소 중 동일한 값을 찾으라는 문제이기 때문에 (1,1),(2,2)가 됩니다.  예제3) 2) 방향그래프그래프 G = (V,E)에서 방향을 가지면 G는 방향 그래프가 되고 방향을 가지지 않으면 G는 무향그래프가 됩니다. 예제)위 그래프를 해석하면 1 → 1, 1 → 2, 2 → 1, 2 → 2, 3 →1,..

• format_list_bulleted CS(Computer Science) 이론/이산수학
• · 2024. 5. 5.
• textsms

[이산수학] 행렬

1. 행렬이란행렬이란 행과 열로 구성되는 사각형 형태로 수를 배열한 것을 의미합니다.  위와 같은 형태를 행렬이라고 합니다. 이때 일반적으로 괄호를 사용하지만 대괄호[]를 사용하여 표현할 수도 있습니다. 이러한 행렬은 다양한 프로그래밍언어, 자료구조, 컴퓨터 그래픽스, 패턴인식, 로봇동작, 인공지능 등 여러가지 컴퓨터 분야에서 활용됩니다. 1) 일반행렬일반행렬은 우리가 흔히 알고있는 행렬의 형식을 의미합니다. 정의는 'm,n이 양의 정수일 때, m개의 행과 n개의 열로 구성된 직사각형의 수 배열을 m x n 행렬이라 한다'입니다.행렬의 원소표시는 아래처럼 합니다.2)영행렬행의 개수와 열의 개수와 상관없이 모든 원소가 0인 행렬을 영행렬이라고 합니다.2. 행렬의 연산1) 행렬의 합, 차, 스칼라곱크기가 같..

• format_list_bulleted CS(Computer Science) 이론/이산수학
• · 2024. 5. 5.
• textsms

[이산수학] 집합론

1. 기본개념1) 논리학과 집합론논리합(or) 이 합집합이 되며 논리곱(and)은 교집합이라고 합니다. 2) 집합과 원소집합은 무정의 용어라고도 합니다.즉 정의없이 사용하는 용어이며, 직관적으로 이해할 수 있으나 다른용어로 정의하기 힘든 대상을 표현하기 위해 사용됩니다. 3) 집합의 표기법집합의 표기법은 아래와 같습니다. 4) 부분집합위에서 a는 집합의 원소를 얘기하지만 아래에서 A는 집합을 얘기합니다. 5) 진부분집합진부분 집합이란 A가 B에 완전히 속해있을 때 진부분집합이라고 합니다.6) 상동상동은 집합A와 집합B가 동일한것을 의미합니다.표기는 아래처럼 합니다. 𝑨 =𝑩 ⇔ 𝑨⊆𝑩 𝒂𝒏𝒅 𝑩⊆𝑨 7) 서로소와 쌍으로 서로소서로소는 집합 두개를 비교했을 때 교집합이 공집합일 경우이고, ..

• format_list_bulleted CS(Computer Science) 이론/이산수학
• · 2024. 5. 1.
• textsms

[이산수학] 증명

1. 증명 관련 기본 용어1) 공리어떤 다른 명제들을 증명하기 위해 전제로 사용되는 가장 기본적인 가정으로 별도의 증명없이 참으로 이용되는 명제를 공리라고 합니다. 공리의 예로서는 아래 이론등이 있습니다.1) 유클리드 기하학 : 두 점이 주어졌을 때 두점을 통과하는 직선을 그릴 수 있다.2) 페아노의 공리 : 어떤 자연수도, 그 수의 다음 수가 존재한다.3) 공리적 집합론 : 어떤 것도 포함되지 않는 집합이 존재한다.2) 증명특정한 공리들을 가정하고, 그 가정하에 제안된 명제가 참입을 입증하는 작업을 증명이라고 합니다.3) 정리공리로부터 증명된 명제를 정리라고 합니다.이 정리에는 여러가지가 있습니다. 1) 보조정리 :  정리를 증명하는 과정 중에 사용되는 증명된 명제2) 따름정리 : 정리로부터 쉽게 도출..

• format_list_bulleted CS(Computer Science) 이론/이산수학
• · 2024. 4. 28.
• textsms