[이산수학] 논리

1. 명제참과 거짓을 구별할 수 있는 문장이나 수학적 식을 명제라고합니다. 즉 주관적인 값이 아닌 객관적인 값이 명제가 됩니다.명제가 타당한 경우 참 또는 T(True)라고 하고 명제가 타당하지 않은 경우 거짓 또는 F(False)라고 합니다.2. 논리연산자1) 논리합(or, ∨)진리표는 아래와 같습니다. pqp ∨ qTTTTFTFTTFFF  위의 진리표를 해석해보자면 p,q중 하나만 참이여도 결과는 참이 나옵니다. 즉 모두가 거짓이 아니라면 결과는 참이 됩니다. 2) 논리곱(and, ∧ )진리표는 아래와 같습니다.pqp ∧ qTTTTFFFTFFFF 위의 진리표를 해석하면 p,q 모두가 참이여야 결과가 참이 됩니다. 그 외에는 모두 거짓이 됩니다. 3) 부정(~, ᄀ)진리표는 아래와 같습니다.p~pTFF..

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

[알고리즘] 탐색

탐색이란 여러개의 원소로 구성된 데이터에서 원하는 값을 갖는 원소를 찾는 것을 의미합니다. 이때 주어진 데이터의 형태는 리스트, 트리, 그래프 등이 있고, 탐색 중에서도 내부탐색, 외부탐색이 있습니다.  그리고 탐색을 할때는 초기화, 삽입, 삭제 등 관련 연산등도 고려해야 합니다. 이러한 탐색방법에는 리스트형태(순차 탐색, 이진탐색), 트리형태(이진탐색트리, 2-3-4 트리, 레드-블랙 트리, B-트리), 해시테이블(해시 함수) 등이 있습니다. 1. 순차탐색리스트 형태로 주어진 원소들을 처음부터 하나씩 차례로(순차) 비교하면서 원하는 값을 갖는 원소를 찾는 방법입니다.1) 탐색연산의 알고리즘 SequentialSearch(A[],n,x) // A[] : 입력배열, n: 입력크기(탐색할 데이터의 개수), ..

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

[알고리즘] 데이터 분포 기반 알고리즘

데이터 분포기반 알고리즘은 이미 얻어진 데이터 분포정보를 활용하는 정렬 알고리즘입니다. 이러한 데이터 분포 기반 알고리즘에는 계수정렬, 기수정렬, 버킷정렬 등이 있으며 선형시간 O(n)이 가능합니다. 데이터 분포기반 알고리즘의 단점으로는 입력값의 범위를 미리 알아야 하며 특정조건에 맞게 제한적으로만 사용 가능하기 때문에 보편적이지 못한 정렬 알고리즘이 됩니다.1. 계수정렬주어진 데이터 중에서 자신보다 작거나 같은 값을 같는 데이터의 개수를 계산하여 정렬할 위치를 찾아 정렬하는 방식입니다. 계수정렬은 입력값이 어떤 작은 정수 범위내에 있다는 것을 알고있는 경우에만 적용가능합니다. k보다 작거나 같은 값을 갖는 데이터의 개수를 알고 있을 때 이 데이터의 개수의 의미는 정렬 순서상 k의 마지막 위치를 의미합니..

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

[알고리즘] 비교 기반 알고리즘

내부정렬이란 정렬 중 전체데이터를 주기억 장치에 저장한 후 정렬을 수행하는 방식의 정렬입니다. 이러한 내부정렬에는 정렬방식에 따라 비교 기반 알고리즘과 데이터 분포 기반 알고리즘으로 나눌 수 있습니다. 비교 기반 알고리즘은 직접적인 데이터 비교를 통해 알고리즘을 수행하는 방식입니다. 이러한 비교 기반 알고리즘의 종류에는 선택정렬, 버블정렬, 삽입정렬, 셸정렬, 퀵정렬, 합병정렬, 힙정렬 등이 있습니다. 비교 기반의 알고리즘의 성능을 측정하는 방법은 키값의 비교횟수가 적으면 성능이 좋다고 할 수 있습니다. 비교 기반 알고리즘 중 선택정렬, 버블정렬, 삽입정렬, 셸정렬은 시간복잡도가 O(n^2)이며 퀵 정렬, 합병정렬, 힙정렬의 시간복잡도는 O(nlogn)입니다. 1. 선택정렬선택정렬은 입력배열에서 가장 작..

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

[알고리즘] 정렬 관련 개념

1. 안정적 정렬안정적인 정렬이란 동일한 값을 갖는 데이터가 여러개 있을 때 정렬전의 상대적위치가 정렬후에도 그대로 유지되는 정렬을 의미합니다. 예컨대 입력데이터가 아래와 같이 존재한다고 가정해 보겠습니다.10,20,30,50,40,20,60 위에 정렬전 데이터에는 동일한 데이터인 20이 존재합니다. 앞의 20을 A 뒤의 20을 B라고 하겠습니다. 데이터를 정렬하면 아래의 두가지 케이스로 나뉠 수 있습니다.10,20(A),20(B),30,40,50,60 10,20(B),20(A),30,40,50,60 위의 첫번째 케이스를 '안정적'이라고 하고 두번째 케이스를 '불안정적'이라고 합니다. 따라서 안정적인 정렬이란 첫번째 케이스처럼 정렬되는 것을 의미합니다. 2. 제자리 정렬입력 배열이외의 별도로 필요한 저장..

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

[알고리즘] 분석

1) 정확성 분석유효한 입력에 대해 유한시간 내에 정확한 결과를 만들어 내는지 확인하는 것입니다.이러한 확인은 수학적 기법을 사용하여 이론적으로 증명합니다. 2) 효율성 분석효율성 분석은 알고리즘 수행에 필요한 컴퓨터 자원의 양을 측정, 평가하는 것입니다.이러한 효율성 분석에는 공간복잡도, 시간복잡도가 있습니다. 1. 공간복잡도컴파일하는 시점에서 발생하는 메모리와 알고리즘을 수행할때 필요한 메모리가 있는데 이러한 총 메모리양이 필요한지 측정하는 것입니다. 2. 시간복잡도시간 복잡도는 알고리즘의 실행부터 완료까지 걸리는 시간을 분석하는 것입니다. 알고리즘의 수행시간은 각 연산이 수행되는 횟수의 합이라고 볼 수 있습니다이러한 수행시간에 영향을 미치는 요인에는 여러가지가 있습니다. 첫번째로 입력크기 입니다.예..

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

알고리즘 개요

1. 알고리즘이란?주어진 문제를 해결하거나 함수를 계산하기 위해 따라야 할 명령어들을 단계적으로 나열한 것이라고 할 수 있습니다. 2. 알고리즘을 만족하기 위한 조건1. 입출력 : 0개 이상의 외부입력과 1개 이상의 출력을 생성해야 합니다.2. 명확성 : 각 명령은 모호하지 않고 단순 명확해야 합니다.3. 유한성 : 한정된 수의 단계를 거친 후에는 반드시 종료해야 합니다.4. 유효성 : 모든 명령은 컴퓨터에서 수행할 수 있어야 합니다.5. 효율성 : 효율성은 알고리즘을 만족하기 위한 필수 조건은 아닙니다. 그러나 실용적관점에서는 효율성도 상당히 중요합니다. 왜냐하면 알고리즘을 구성하더라도 무한한 시간이 걸린다면 문제해결을 할 수 없다고 볼 수 있기 때문입니다.3. 알고리즘의 생성단계1) 설계일반적/ 범용..

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

[디자인 패턴] MVC 패턴

MVC(Mode-View-Controller) 패턴은 소프트웨어 디자인 패턴 중 하나로, 애플리케이션의 구조를 세 가지 주요 구성 요소로 분리하여 개발하는 방법입니다. 이 패턴은 애플리케이션의 유지보수성, 확장성, 재사용성을 향상시킬 수 있으며, 개발자 간의 협업을 용이하게 만듭니다. 1. MVC 패턴의 구성요소1) 모델(Model)모델은 애플리케이션의 비즈니스 로직과 데이터를 담당합니다. 데이터의 상태를 관리하고 데이터의 변경을 처리합니다. 모델은 독립적으로 존재하며, 보통 데이터베이스, 파일 시스템, 외부 API 등과 상호 작용하여 데이터를 가져오거나 저장합니다.2) 뷰(View)뷰는 사용자에게 정보를 시각적으로 표시하는 역할을 합니다. 모델의 데이터를 표현하고 사용자 인터페이스를 구성하는 역할을 수..

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