2023 1학기/자료구조

Using Dfs to print Equivalence Relation n^2 짜리 배열을 만들고 입력받아서 1로 마킹 1차원 배열의 작은 번호부터 dfs() 호출 (수정중)

Definition of Equivalence Relation First, Definition for Relation 집합 A 의 관계 : 집합R 1R3 : (1,3) 이 R에 포함된다는 것으로 표현한다. 그렇다면 동치 관계는 어떤 것일까? 아래 그림에서 볼 수 있듯이 R,S,T 세 조건이 모두 성립하면 동치 관계이다. 위 설명을 처음에는 이해하지 못했지만, 작년 이산수학에 나왔던 집합에서의 "동치 관계"를 의미하는 것을 알 수 있었다. Relflexive :반사 Symmetric :대칭 Transitive :전이 Induced Partition and How to find it 이렇게 동치관계를 이용하면, 각 원소를 연결하여 partition이 생길 수 밖에 없게된다. Induced Partition을..

naive 알고리즘, DFA 알고리즘 처음에는 어려웠다. 그렇지만 코드로 구현해보니, 괜찮았다. #define max(a,b) ((a) < (b) ? (a) : (b)) #include #include void naivematch(char T[], int n, char P[], int m, int* output) { int i, j; for (i = 0; i < n; i++) { j = 0; while (j < m && P[j] == T[i + j]) { output[i + j] = max(output[i + j], j + 1); j++; } } } int main() { char T[] = { 'a','b','a','b','a','b','c','a','b','c','a','b','c','d','a','..

1) 재귀함수의 시간복잡도를 구해보자 int main() { int n; scanf("%d", &n); //대입연산 1회 printf("%d", sum(n)); //연산 cn (c : 더하는 비용) return 0; } int sum(int x) { if (x

명제와 수학적 귀납법을 재귀함수를 통해서 이해해보자. #define _CRT_SECURE_NO_WARNINGS #include //수학적 귀납법 + 명제 int sum(int x) { if (x Q TTT TFF FTT FFT 의 진리값을 갖는다. 수학적 귀납법의 정의에서 노란배경색 부분이 "참이면 참" 을 보는 이유는 앞 부분의 명제가 거짓일 때는 뒤 부분의 명제의 진리값에 관계없이 전체 명제가 참이 되기 때문에 의미가 없다. 따라서 참이면 참이라는 부분만 보게 된다. 이에 따라 sum함수를 보면, base) x = 1일때, sum함수는 return 1 + sum(0)이고, sum(0) = 0이므로, sum함수는 결과적으로 1을 리턴한다. seep) sum(x-1)이 1+2+ ... + x-1 의 값을..

하드웨어 기초: 메모리와 CPU 1. CPU 0과1로의 계산을 어떻게 어떤 순서로 할지(제어) 결정하는 부분 2. 메모리 CPU가 프로그램을 실행시키기 위해 참조하기 위한 필요한 정보들을 저장해두는 공간 위 그림 설명 : 메모리 상에 "2037" , "37"이라는 데이터를 담는 주소가 각각 900~903 , 2016 이 있다.CPU로 BUS의 역할(control, data, add-address) 을 거쳐 옮겨진다. IP에는 주소값이, Registers에는 실제 값이 들어간다. 포인터와 정수형 변수를 어떻게 저장하는지를 위의 그림을 이용해서 아래와 같이 표현할 수 있다. 위 이미지에 대해 간단한 설명을 붙인다면, int a, int* p, int** q 가 있고, p = &a, q = *p, **q = ..