룰루랄라 알고리즘

Graph 완전 그래프 Edge의 수가 최대인 그래프 n개의 vertex 일 때 최대 edge 수 : n(n-1)/2 경로의 길이 경로 상에 있는 edge의 수 단순 경로(simple path) 처음과 마지막을 제외한 vertex가 다른 경로 그래프 표현 방법 분석 G에 존재하는 edge 수 검사, or G가 연결되었는지 검사 인접 행렬 : n(n-1)/2 개의 항 조사 -> O(n^2) 인접 리스트 : O(n+e) Digraph에서 vertex의 in-degree 조사 인접 행렬 : O(n) 인접 리스트 : O(n+e) DFS (깊이 우선 탐색) 로직 1. 출발 정점 v의 인접 리스트부터 방문 2. v에 인접하면서 아직 방문하지 않은 정점 w를 선택 3. w를 시작점으로 하여 다시 dfs 시작 4. r..

전 세계 컴퓨터의 70%는 정렬을 하는데 시간을 보내고 있다 할 정도로 중요하고, 값 비싼 연산인 정렬을 파헤쳐보자. 전 세계 컴퓨터 공학자들의 Bible로 불리는 C로 쓴 자료구조의 높은 퀄리티의 코드를 하나하나 씹어 먹어보자! (Y 대학 Prof. Cho의 강의력과 학생들을 향한 헌신에 감사하며 작성하는 글입니다.) Insertion Sort (삽입 정렬) Time Complexity 최선 평균 최악 Space Complexity Stable Insertion n n^2 n^2 1 Yes 대부분의 데이터가 sorting 되어 있을 경우 효과적이다. 데이터가 역순으로 sorting 되었을 때 최악의 성능 데이터 수가 n개일 때 성능 최선 최악 비교 n n^2 / 2 교환 0 n^2 / 2 삽입 정렬의 ..

미로찾기 2차원 배열을 이용한 미로의 구현 maze[row][column]: 0 – 길, 1 – 벽 이동 방향 : 8방향(N, NE, E, SE, S, SW, W, NW) 경계 지역 : 8방향이 아님. (모서리: 3방향, 변: 5방향) m x p 미로를 (m + 2) x (p + 2) 미로로 변환 각 경계 영역의 maze 배열값은 1로 설정 입구: maze[1][1], 출구: maze[m][p] #include #include #define MAX_STACK_SIZE 100 // = m x p #define FALSE 0 #define TRUE 1 #define EXIT_ROW 4 // 출구 좌표 #define EXIT_COL 4 struct element{ short int row; short int ..

이중 연결 리스트 한 노드에 이전 노드, 다음 노드를 가리키는 포인터 두 개를 가지고 있다 덕분에 단일 연결리스트 처럼 한 방향이 아닌 양 방향으로 이동 가능하다 이중 연결 리스트 노드 생성 struct node { struct node *llink; // 이전 노드를 포인트 int data; struct node *rlink; // 다음 노드를 포인트 }; 이중 연결 리스트의 종류 원형 이중 연결 리스트에 노드 추가 newnode를 node의 오른쪽에 추가하는 연산 void dinsert(struct node *node, struct node *newnode) { // newnode를 node의 오른쪽에 추가 newnode->llink = node; newnode->rlink = node->rlink;..

동치 관계 동치 관계를 이용하여 집합 S를 "동치 클래스"로 분할함 ex) 0=4, 3=1, 4=3, 5=6 동치 클래스 : {0, 1, 3, 4}; {5, 6} 배열을 통해 paris[n][n] 구조로 구현해보자. 가 입력될 경우, pairs[i][j]와 pairs[j][i]를 1로 설정하는 방식으로 구현할 수 있다. 하지만 이경우에 원소의 수에 비해 동치항의 수가 적을 경우 즉 희소 행렬이 될 경우에 메모리의 낭비가 심해진다. n개의 연결 리스트 seq[n] 구조로 구현해보자가 입력될 경우 노드 j를 seq[i]가 가리키는 리스트에 추가노드 i를 seq[j]가 가리키는 리스트에 추가하는 방식으로 구현할 수 있다. 일차원 boolean 배열 out[n] : 해당 원소가 출력되었는지 check 하는 배열..

원형 리스트 마지막 노드의 link가 처음 노드를 가리키는 연결 리스트 리스트의 모든 노드를 효율적으로 반환할 수 있다 원형 리스트와 단일 연결 리스트의 연결 void cerase(struct poly** ptr) { //ptr이 가리키는 원형 리스트를 반환 (ptr이 가리키는 원형 리스트와 가용노드 avail을 합침 ) struct poly* temp; if (*ptr) { temp = (*ptr)->link; (*ptr)->link = avail; avail = temp; *ptr = NULL; } } 원형 리스트로 구현한 다항식 더하기 struct poly* cpadd(struct poly* a, struct poly* b) //원형 리스트로 구현한 다항식의 더하기 { /* 다항식 a와 b: sin..

가용 노드 리스트 malloc과 free() 함수는 운영체제에 요청하는 함수이므로 실행시간이 길다. 따라서 malloc과 free()를 사용하지 않고 쓰지 않는 노드들을 내가 가지고 있다가 재활용하는 방법을 사용해서 운영체제에 요청하는 함수들의 호출 빈도수를 줄여보자! 리스트의 모든 노드 삭제 리스트의 모든 노드를 삭제 Time complexity : O(노드의 수) void erase(struct poly** ptr) { //ptr이 가리키는 다항식 리스트를 삭제 struct poly* temp; while (*ptr != NULL) { temp = *ptr; *ptr = (*ptr)->link; free(temp); } } get_node() 만약 aviail이 사용 가능한 노드를 가지고 있다면 그 ..

다항식 구현 struct poly { int coef; //차수 int expon; //지수 struct poly* link; }; struct poly* a, * b, * d; // 다항식 d = a + b 다항식의 합 Time complexity : O(m+n) 다항식 d의 항 추가는 리스트의 끝에서 발생하므로 Queue 형식으로 구현 지수를 비교하여 지수가 같다면 차수끼리 덧셈 후 다항식 d에 추가, 어느 한쪽 지수가 크다면 다항식 d에 큰 지수를 가진 노드를 추가하는 방식으로 진행. #include #include #define COMPARE(x,y) ((xexpon, b->expon)) { case -1: // a->expon expon attach(b->coef, b->expon, &..

배열을 이용한 스택과 큐의 구현 방법에는 메모리 낭비, Stack Full의 발생 가능성이라는 문제점이 있다. 따라서 연결 리스트를 이용해 스택과 큐를 구현해 유동적으로 메모리를 관리해보자. 리스트를 이용한 스택과 큐의 구현 Stack 스택 선언 스택의 초기 조건 : top = NULL; 경계 조건 : top = NULL if stack is empty. IS_FULL(temp) if the memory is full. struct element { int key; }; struct stack { element data; struct stack* link; }; struct stack *top; 스택에 노드 추가 (push) 스택의 제일 앞부분에 push 하는 연산은 time complexity O(1)..