2019 인터넷응용

IVIS wiki

Top

목차

강의 개요

  • 모바일 디바이스와 SNS, 사물인터넷 등의 서비스의 활성화로 인해 개발자가 다루어야할 데이터는 점점 증가하고 있다
  • 인터넷 응용 서비스를 비롯한 여러가지 컴퓨팅 응용분야에서 효율적이고 체계적인 프로그래밍 기법을 습득하는데 기본이 되는 자료구조와 알고리즘을 익힌다.
  • 컴퓨터 프로그래밍을 통해 문제해결을 할 수 있는 능력을 익힌다
  • 강의 진행 :
    • 강사의 강의와 토론 그리고 프로그래밍 실습을 통하여 프로그래밍 기법을 익힌다
    • 주당 3시간의 강의이며 이론 강의와 프로그래밍 실습을 병행한다.
  • 강의실 : 51호관 310호실
    • 강의시간 : 매주 화요일 12:00 -, 목요일 13:30 - (75분 강의)

수강생

  • 수강생들은 강의교재를 준비하여야 한다
  • 수강생들은 C 언어와 같은 기초적인 프로그래밍 언어과목에 대한 선수학습이 필요하다
  • 자료구조 교과목에 대한 이해가 필요하다

강의 내용

  • 기존에 학습한 프로그래밍 관련 교과목을 바탕으로 효율적인 프로그래밍을 위한 자료구조와 알고리즘에 대하여 알아보도록 하자.

강의 교재

  • 교재명 : 알기쉬운 알고리즘(생능출판사)
    • 저자 양성봉 지음

2017 IT IA textbook.jpg

과제관련

  • 과제제출시 반드시 과제번호를 달아서 제출한다
    • 과제번호는 #1, #2, #3,... 과 같이 달도록 한다
  • 과제제출기간은 제출일로부터 일주일입니다

1주차 강의(3월 5일, 7일)

  • 인터넷응용과 강의내용, 교재등에 대한 소개
    • 자료구조와 알고리즘을 알아야 하는 이유
    • 컴퓨터를 이용한 문제해결에서 자료구조가 중요한 이유
    • 강의의 방향
    • 수강생이 알아야할 내용들
      • 수강생들은 C 혹은 C++ 프로그래밍을 학습하여야 함
      • 연결리스트, 포인트, 동적 자료구조에 대한 이해가 반드시 필요함
  • 나의 겨울방학 해외탐방 이야기(14김동욱 학생)

강의 자료 : 강의소개, 1장

2주차 강의(3월 12일, 14)

  • 알고리즘의 첫 걸음
    • 알고리즘의 유래
      • 알고리즘은 문제를 해결하기 위한 단계적인 절차를 의미한다.
      • 유클리드의 최대공약수 알고리즘
    • 시간복잡도 - Big-Oh의 개념

강의 자료 : 2장

과제 #1

수강 : 홍길동
수강평 : 0000000 에 대해 자세히 알게되었으며, 000에 대해서 0000라고 생각합니다.
궁금한점 : 0000000에 관한 부분이 잘 이해가 안됩니다. 0000000는 0000이 아닌가요? “등
형식으로 질문을 해 주시면 됩니다.

과제 #2

  • 제목 : 교재 2장 연습문제 풀이, 보간탐색에 대한 조사
  • 제출일 : 3월 26일
    • 1,2,3,4,5,7,8,17,18,19,20,21,23번 풀이하기
    • 보간 탐색이란 무엇인가?
      • 보간 탐색에 대하여 조사하고 그 시간 복잡도를 설명하시오
    • 참고 : 보간탐색 youtube

3주차 강의(3월 19일, 21일)

  • 분할정복 알고리즘
    • 합병정렬
    • 퀵정렬
  • 3월 21일은 개교기념일 휴교입니다.

강의 자료 : 3장 분할정복

코드 : 합병정렬

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 10

// list[] 배열의 원소를 출력함
void print_list(int list[], int n)
{
    int i;
    for (i = 0; i<n; i++)
        printf(" %d ", list[i]);
    printf("\n");
}

// list[]의 원소를 나누어서 임시 배열에 넣은 후, 이 원소들을 합병한다
void merge(int list[], int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;
    // 빈 배열 만들기, 이 배열은 list 배열의 부분 배열임
    int left_list[n1], right_list[n2];
    
    // 임시 배열 left_list, right_list에 list 배열의 원소를 나누어 넣음
    for (i = 0; i < n1; i++)
        left_list[i] = list[l + i];
    for (j = 0; j < n2; j++)
        right_list[j] = list[m + 1 + j];
    
    // 임시 배열 left_list, right_list의 원소를 합병하며 list에 넣음
    // 이 때문에 합병 정렬은 임시 배열이 필요하다
    i = 0; // left 부분 배열의 초기 인덱스
    j = 0; // right 부분 배열의 초기 인덱스
    k = l; // 합병된 배열의 초기 인덱스
    while (i < n1 && j < n2)
    {
        if (left_list[i] <= right_list[j])
        {
            list[k] = left_list[i];
            i++;
        }
        else
        {
            list[k] = right_list[j];
            j++;
        }
        k++;
    }  // 합병이 완료될때까지 loop를 수행하며
    
    // 합병 후 left_list에 남아있는 원소가 있을 경우 이를 list에 넣기
    while (i < n1)
    {
        list[k] = left_list[i];
        i++;
        k++;
    }
    // 합병 후 right_list에 남아있는 원소가 있을 경우 이를 list에 넣기
    while (j < n2)
    {
        list[k] = right_list[j];
        j++;
        k++;
    }
}

// 합병 정렬 함수
void merge_sort(int list[], int left, int right)
{
    int mid;
    if (left < right) {
        mid = (left + right) / 2;     // 배열의 중간 인덱스 값을 구한다
        merge_sort(list, left, mid);    // 앞의 절반을 정렬
        merge_sort(list, mid + 1, right); // 뒤의 절반을 정렬
        merge(list, left, mid, right);    // 두 개를 합병
    }
}

// 합병 정렬 프로그램
int main()
{
    int n = MAX_SIZE;
    int list[MAX_SIZE];
    
    for (int i = 0; i<n; i++)      	// 난수 생성 및 출력
        list[i] = rand() % 100 ; // 난수 발생 범위 0~100
    
    printf("합병 정렬 전 데이터 \n");
    print_list(list, MAX_SIZE);
    
    merge_sort(list, 0, MAX_SIZE-1); // 합병 정렬함수 호출
    
    printf("\n합병 정렬 후 데이터 \n");
    print_list(list, MAX_SIZE);
    
    return 0;
}
  • 수행결과(위의 코드를 C 통합개발 도구를 이용해서 작성해 봅시다)

2017 MergeSort.png

코드 : 퀵정렬

#include <stdio.h>

#define MAX_SIZE 9

void swap(int *x, int *y)
{
    int temp = *x;
    *x = *y;
    *y = temp;
}

// list 배열의 원소를 출력하는 함수
void print_list(int list[], int n)
{
    int i;
    for (i = 0; i<n; i++)
        printf("%d ", list[i]);
    printf("\n");
}

// list에는 정렬전 원소들이 있으며, left, right 값은 정렬할 데이터의 인덱스가 있다
int partition(int list[], int left, int right)
{
    int pivot;
    int low = left, high = right+1;
    
    pivot = list[left]; 	// 피벗은 list의 첫값으로 정한다
    do {
        do
            low++;    // 리스트의 왼편에서 피벗 값보다 큰 레코드1을 선택
        while (low <= right && list[low] < pivot);
        do
            high--;   // 리스트의 오른쪽에서 피벗보다 작은 레코드2를 선택
        while (high >= left && list[high] > pivot);
        if (low<high) // low값이 high보다 작으면 레코드1, 레코드2를 서로 교환
            swap(&list[low], &list[high]);
    } while (low < high);	  // 인덱스의 high 값이 low보다 크면 반복수행
    
    swap(&list[left], &list[high]); // 리스트의 제일 첫 값과 high 값을 교환
    
    return high;
}

// 퀵정렬은 재귀적인 기법을 사용하면 간결하게 구현할 수 있다
void quick_sort(int list[], int left, int right)
{
    if (left<right) {     // 분할가능한 상태이면
        // 피벗을 중심으로 작은 값은 왼쪽 부분리스트로 큰 값은 오른쪽 부분리스트로 보낸다
        int q = partition(list, left, right);
        //printf("pivot = %d\n", q);
        //print_list(list, MAX_SIZE);
        quick_sort(list, left, q - 1);      // 왼쪽 부분리스트를 퀵정렬
        quick_sort(list, q + 1, right);     // 오른쪽 부분리스트를 퀵정렬
    }
}

//
int main()
{
    // 퀵정렬은 미리 정렬된 데이터에 대한 정렬이 비효율적이다
    //int list[MAX_SIZE] = { 1, 2, 3, 4, 5, 6, 7, 8, 9};
    int list[MAX_SIZE] = { 18, 14, 17, 20, 25, 13, 16, 22, 40 };
    
    printf("퀵정렬 전 데이터 \n");
    print_list(list, MAX_SIZE);
    printf("\n");
    
    printf("퀵정렬 과정 \n");
    quick_sort(list, 0, MAX_SIZE-1);
    printf("\n");
    
    printf("퀵정렬 후 데이터 \n");
    print_list(list, MAX_SIZE);
    printf("\n");
}
  • 수행결과

2017 QuickSort.png

코드 : 라이브러리를 사용한 퀵정렬

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE    9

// list 배열의 원소를 출력하는 함수
void print_list(int list[], int n)
{
    int i;
    for (i = 0; i<n; i++)
        printf("%d ", list[i]);
    printf("\n");
}

// 퀵정렬을 위한 비교함수
// 이 프로그램은 정수값을 비교하므로 void형 포인터 변수의 형은 int형 포인터로
// 형을 변환하여 비교한다
int compare(const void *a, const void *b)
{
    // a가 b보다 크면 양수, 같으면 0, 작으면 음수를 반환
    //return ( *(int *)a - *(int *)b);
    return ( *(int *)b - *(int *)a );
}

//
int main()
{
    int list[MAX_SIZE] = { 18, 14, 17, 20, 25, 13, 16, 22, 40 };
    
    printf("퀵정렬 전 데이터 \n");
    print_list(list, MAX_SIZE);
    printf("\n");
    
    qsort((void *)list, (size_t)MAX_SIZE, sizeof(int), compare);
    
    printf("퀵정렬 후 데이터 \n");
    print_list(list, MAX_SIZE);
    printf("\n");
}
  • 수행결과

2017 IA QuickSortLib.png

코드 : 선택문제

#include <stdio.h>
#include <limits.h>

int partition(int list[], int left, int right);

// list 배열의 원소를 출력하는 함수
void print_list(int list[], int n)
{
    int i;
    for (i = 0; i<n; i++)
        printf("%d ", list[i]);
    printf("\n");
}

// 이 함수는 배열 list[l..r] 내의 원소중에서 k번째 작은 원소를 반환합니다
// 널리 알려진 정렬 알고리즘인 QuickSort 방식과 유사합니다
// 가정 : list[l..r] 내의 모든 원소들이 서로 다른 수라고 가정함
int Selection(int list[], int left, int right, int k)
{
    // 만일 k가 배열 내의 원소의 수보다 더 작다면
    if (k > 0 && k <= right - left + 1) {
        // 배열을 마지막 원소를 이용해서 배열을 분할한다
        // 그리고 정렬된 배열에서 피봇이 몇번째 있는지 위치를 구한다
        int pos = partition(list, left, right);
        
        // 만일 피봇 위치가 k와 같다면 이를 반환하면 됨
        if (pos-left == k-1)
            return list[pos];
        // 만일 피봇의 위치가 k보다 크다면 재귀적인 방법으로 왼쪽 배열에서 k번째 값을 구한다
        if (pos-left > k-1)
            return Selection(list, left, pos-1, k);
        
        // 그렇지 않다면 재귀적인 방법으로 오른쪽 배열에서 k번째 값을 구한다
        return Selection(list, pos+1, right, k-pos+left-1);
    }
    
    // 혹시 k가 배열원소의 수보다 더 큰 값이면 해 없음(INT_MAX)를 반환
    return INT_MAX;
}

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

// list에는 정렬전 원소들이 있으며, left, right 값은 정렬할 데이터의 인덱스가 있다
int partition(int list[], int left, int right)
{
    int pivot;
    int low = left, high = right+1;
    
    pivot = list[left]; 	// 피벗은 list의 첫값으로 정한다
    do {
        do
            low++;    // 리스트의 왼편에서 피벗 값보다 큰 레코드1을 선택
        while (low <= right && list[low] < pivot);
        do
            high--;   // 리스트의 오른쪽에서 피벗보다 작은 레코드2를 선택
        while (high >= left && list[high] > pivot);
        if (low<high) // low값이 high보다 작으면 레코드1, 레코드2를 서로 교환
            swap(&list[low], &list[high]);
    } while (low < high);	  // 인덱스의 high 값이 low보다 크면 반복수행
    
    swap(&list[left], &list[high]); // 리스트의 제일 첫 값과 high 값을 교환
    //print_list(list, 12);
    
    return high;
}

// 위에서 구현한 함수를 검사하는 프로그램
int main()
{
    int list[] = {6, 3, 11, 9, 12, 2, 8, 15, 18, 10, 7, 14};
    int n = sizeof(list)/sizeof(list[0]), k = 7;
    
    printf("원본 데이터\n");
    print_list(list, n);
    
    printf("\n데이터 중에서 %d번째 작은 수는 %d 이다.\n\n", k,
           Selection(list, 0, n-1, k));
    return 0;
}
  • 수행결과

2017 IA kthSelection.png

4주차(3월 26일, 28일)

  • 분할정복 알고리즘 - 코드 리뷰
  • 합병정렬, 퀵정렬, 선택문제와 최근접 점 쌍을 찾는 분할정복 알고리즘
  • 그리디 알고리즘
    • 그리디 알고리즘은 최적화 문제를 해결하는 알고리즘의 하나이다
    • 최적화 문제는 가능한 해들 중에서 가장 좋은(최대 또는 최소)해를 찾는 문제이다

강의자료 4장 : 그리디 알고리즘

과제 #3

  • 제목 : 3장 연습문제 풀이
    • 연습문제 1,5,7,8,10,11,14,16번
      • 5번 문제의 경우 각 과정의 결과를 손으로 함께 적고 프로그램수행 결과도 함께 보이시오
      • 문제를 적고 그 답과 이유를 적으시오
    • 연습문제 16번의 Closest Pair 알고리즘을 C 언어나 C++를 이용하여 직접 구현하여라
      • 문제 16번의 데이터를 points.inp라는 텍스트 파일을 만들어서 이를 이용하여 문제를 해결하시오.
      • 이 입력을 이용하여 Closest Pair 알고리즘을 적용하여 가장 근접한 두 점을 구한다음 두 점 사이의 거리도 구하여라
      • 각단계별 과정을 손으로 그리고 그림으로 함께 설명하시오
      • 프로그램 코드와 실행결과를 함께 제출하여라
      • 프로그램에 대하여 주석을 충분히 많이 달도록 한다
      • 프로그램 작성 후 문제 해결시의 어려웠던 점과 해결과정에서 자신의 느낀점을 반드시 적으시오
      • 교재의 방법으로 문제해결이 어려울 경우 O(n^2) 알고리즘을 사용하더라도 반드시 구해보세요
  • points.inp 파일 예시
    • 파일의 첫 줄은 입력될 점의 개수(16개의 점이 입력임)가 있음, 출력은 다음과 같이 가장 가까운 두 점과 거리를 출력하시오
16
10 15
5 15
...

출력결과(예시)

가장 가까운 두 점
(43, 23) (44, 34)
거리 = 4.34

5주차 강의(4월 2일, 4일)

  • 그리디 알고리즘의 의미-동전 거스름도 문제를 통해서 이해하기
  • 그리디 알고리즘 - 최소 신장트리 구하기
    • Kruskal 알고리즘 코드 설명
    • Disjoint set 구하기
    • Prim의 최소 신장트리 알고리즘

강의자료(good programmer)

관련 자료들

코드 : 거스름돈 문제 1

#include <stdio.h>
int minCoin(int change)
{
    int n500, n100, n50, n10, n1;
    n500 = n100 = n50 = n10 = n1 = 0;
    // n500, n100, n50, n10, n1은 각각의 동전 카운트
    while ( change >= 500 ) {
        change = change-500; n500++ ;     // 500원짜리 동전 수를 1 증가
    }
    while ( change >= 100 ) {
        change = change-100; n100++;      // 100원짜리 동전 수를 1 증가
    }
    while ( change >= 50 ) {
        change = change-50; n50++;          // 50원짜리 동전 수를 1 증가
    }
    while ( change >= 10 ) {
        change = change-10; n10++;          // 10원짜리 동전 수를 1 증가
    }
    while ( change >= 1 ) {
        change = change-1; n1++;              // 1원짜리 동전 수를 1 증가
    }

    printf("500원동전 = %d, 100원동전 = %d, 50원동전 = %d, 10원동전 = %d, 1원동전 = %d\n",
           n500, n100, n50, n10, n1);
    
    return (n500+n100+n50+n10+n1); // 총 동전 수를 리턴한다.
}

int main(int argc, const char * argv[]) {
    // 잔돈의 개수 구하는 함수 호출
    printf("760원에 필요한 최소의 잔돈은 %d 개 입니다\n", minCoin(760));
    return 0;
}
  • 수행결과

2017 IA minCoin1.png

코드 : 거스름돈 문제 2 - 최적이 아닌 경우

// 160원 동전이 추가된 경우 200원을 거슬러 주는 거스름돈 문제 - 최적의 해가 아님
#include <stdio.h>
int minCoin(int change)
{
    int n500, n160, n100, n50, n10, n1;
    n500 = n160 = n100 = n50 = n10 = n1 = 0;
    // n500, n100, n50, n10, n1은 각각의 동전 카운트
    while ( change >= 500 ) {
        change = change-500; n500++ ;     // 500원짜리 동전 수를 1 증가
    }
    while ( change >= 160 ) {           // 160원짜리 동전이 추가된 경우의 해
        change = change-160; n160++;      // 160원짜리 동전 수를 1 증가
    }
    while ( change >= 100 ) {
        change = change-100; n100++;      // 100원짜리 동전 수를 1 증가
    }
    while ( change >= 50 ) {
        change = change-50; n50++;          // 50원짜리 동전 수를 1 증가
    }
    while ( change >= 10 ) {
        change = change-10; n10++;          // 10원짜리 동전 수를 1 증가
    }
    while ( change >= 1 ) {
        change = change-1; n1++;              // 1원짜리 동전 수를 1 증가
    }
    
    printf("500원동전 = %d, 160원 동전 = %d, 100원동전 = %d, 50원동전 = %d, 10원동전 = %d, 1원동전 = %d\n",
           n500, n160, n100, n50, n10, n1);
    
    return (n500+n160+n100+n50+n10+n1); // 총 동전 수를 리턴한다.
}

int main(int argc, const char * argv[]) {
    // 잔돈의 개수 구하는 함수 호출
    printf("200원에 필요한 최소의 잔돈은 %d 개 입니다\n", minCoin(200));
    return 0;
}
  • 수행결과

2017 IA minCoin2.png

코드 : 그래프 구조를 위한 인접 리스트 프로그램

  • 파일로부터 정점의 갯수와 연결정보를 받아들이는 프로그램
#include <stdio.h>
#include <stdlib.h>

#define maxV 100    //  최대 100개의 정점을 가지는 그래프를 가정함

typedef struct graphnode{
    int vertex;
    struct graphnode *next;
} Node;
Node **node;
Node **nodeT;

FILE *fp;

void initial(int nv);
void AdjList();
void PrintAdjList(int nv);
void CreateAdjList();

int main()
{
    int nv;
    
    if( (fp = fopen("input.txt","r")) == NULL ) {
        fprintf(stderr, "Cannot find file\n");
        return 0;
    }
    
    fscanf(fp,"%d",&nv);
    printf("vertex의 수 = %d\n", nv);
    initial(nv);
    CreateAdjList();
    PrintAdjList(nv);
    
    return 0;
}

void initial(int nv)
{
    node = (Node **)malloc((nv+1)*sizeof(Node *));
   for(int i = 0; nv >= i; i++)
      node[i] =NULL;
}

//CREATE ADJACENCY  LIST -
void CreateAdjList(void)
{
    int v1,v2;
    Node *ptr;
    
    while(fscanf(fp,"%d %d",&v1,&v2)!=EOF){
        
        ptr = (Node *)malloc(sizeof(Node));
        ptr->vertex = v2;
        ptr->next =NULL;
        
        if (node[v1]==NULL) {
            node[v1] = (Node *)malloc(sizeof(Node));
            node[v1]->vertex = v1;
            node[v1]->next = NULL;
        }
        
        Node *list = node[v1];
        while (list->next!=NULL)
            list = list->next;
        
        list->next = ptr;
    }
    
    fclose(fp);
}

//PRINT LIST
void PrintAdjList(int nv)
{
    int i;
    Node *ptr;
    
    for(i=1; i<=nv; i++){
        ptr = node[i]->next;
        printf("node[%2d]  ",i);
        while(ptr != NULL){
            printf("  -->%2d", ptr->vertex);
            ptr=ptr->next;
        }
        printf("\n");
    }
    printf("\n");
    
}
  • input.txt 파일
8
1 2
2 3
2 5
2 6
3 4
3 7
4 3
4 8
5 1
5 6
6 7
7 6
7 8
8 8
  • 수행결과

2017 IA AdjList.png

코드 : Kruskal의 알고리즘으로 구현한 최소 신장트리

// input example
// no. of vertices : 5
// adjacency matrix : 0 2 3 0 0 2 0 15 2 0 3 15 0 0 13 0 2 0 0 9 0 0 13 9 0

#include<stdio.h>

#define MAX 30

typedef struct edge
{
    int u,v,w;
} edge;

typedef struct edgelist
{
    edge data[MAX];
    int n;
} edgelist;

edgelist elist;

int G[MAX][MAX],n;
edgelist spanlist;

void kruskal();
int find(int belongs[],int vertexno);
void union1(int belongs[],int c1,int c2);
void sort();
void print();

int main()
{
    int i,j;
    
    printf("\nEnter number of vertices:");
    scanf("%d",&n);
    
    printf("\nEnter the adjacency matrix:\n");
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            scanf("%d",&G[i][j]);
    
    kruskal();
    print();
    
    return 0;
}

void kruskal()
{
    int belongs[MAX],i,j,cno1,cno2;
    elist.n=0;
    
    for(i=1;i<n;i++)
        for(j=0;j<i;j++) {
            if(G[i][j]!=0) {
                elist.data[elist.n].u=i;
                elist.data[elist.n].v=j;
                elist.data[elist.n].w=G[i][j];
                elist.n++;
            }
        }
    
    sort(); // 에지의 weight에 따른 정렬
    
    for(i=0;i<n;i++)
        belongs[i]=i; // vertex 인덱스를 belongs[] 배열의 초기값으로 설정
    
    spanlist.n=0;  // Spanning Tree의 초기 edge 갯수를 초기화함
    
    for(i=0;i<elist.n;i++) {
        // 오름차순으로 정렬된 elist에서 edge를 하나하나 꺼낸다
        cno1=find(belongs, elist.data[i].u);
        cno2=find(belongs, elist.data[i].v);
        if(cno1!=cno2) {  // 동일한 정점이 아니면 스패닝리스트에 추가
            spanlist.data[spanlist.n]=elist.data[i];
            spanlist.n=spanlist.n+1;
            union1(belongs,cno1,cno2);
        }
    }
}

int find(int belongs[], int vertexno)
{
    return(belongs[vertexno]);
}

void union1(int belongs[], int c1, int c2)
{
    for(int i=0;i<n;i++) // 모든 정점을 검사해서
        if(belongs[i]==c2)
            belongs[i]=c1;
}

// edgelist를 그 weight에 값에 따라서 정렬함
void sort()
{
    edge temp;
    
    // 간단한 버블 정렬수행
    for(int i=1;i<elist.n;i++)
        for(int j=0;j<elist.n-1;j++)
            if(elist.data[j].w>elist.data[j+1].w) {
                temp=elist.data[j];
                elist.data[j]=elist.data[j+1];
                elist.data[j+1]=temp;
            }
}

// 결과 출력
void print()
{
    int i,cost=0;
    
    for(i=0;i<spanlist.n;i++)
    {
        printf("\n(%d, %d)  %d",spanlist.data[i].u,spanlist.data[i].v,spanlist.data[i].w);
        cost=cost+spanlist.data[i].w;
    }
    
    printf("\n\nCost of the spanning tree = %d\n",cost);
}
  • 수행결과

2017 IA kruskal.png

코드 : Prim의 알고리즘으로 구현한 최소 신장트리1

#include <stdio.h>

#define M 999   // Infinite 값
#define MAX 5

typedef struct EDGE {
    int pair1;
    int pair2;
} EDGE;

EDGE T[MAX-1];   // Prim 알고리즘으로 해결한 MSP의 edge 집합
// 초기화된 그래프
int G[MAX][MAX] = {
    { 0, 1, 3, M, M },
    { 1, 0, 3, 6, M },
    { 3, 3, 0, 4, 2 },
    { M, 6, 4, 0, 5 },
    { M, M, 2, 5, 0 }};

void prim(int start);

// 모든 정점에 대하여 이 정점이 방문된 정점인지 검사함
int IsVertex(int vertex[], int a) {
    for(int i=0; i<MAX; i++)
        if(vertex[i] == a) return 1;
    return 0;
}

int minimum(int v) {
    int min, temp = M;
    
    for(int i=0; i<MAX; i++)
        if(G[i][v] > 0 && G[i][v] < temp) {
            min = i;
            temp = G[i][v];
            return i;
        }
    return 0;
}

void prim(int start)
{
    int vertex[MAX] = {0,}, index1 = 0;
    int v, k, nearst, index2 = 0;
    
    vertex[index1] = start;
    index1++;
    while(index1 < MAX) {   // 모든 점에 대하여 검사
        nearst = M;     //
        for(int i=0; i<index1; i++) {
            v = vertex[i];
            for(int j=0; j<MAX; j++) {
                k = G[j][v];
                // k값이 유효한 값이고 또한 vertex j가 방문되지 않은 경우
                if(k>0 && k<M && !IsVertex(vertex,j)) {
                    if(k < nearst) {    // k가 최근접 값 nearest보다 작으면 이를 갱산
                        nearst = k;
                        T[index2].pair1 = v; // v, j가 연결된 집함이 됨
                        T[index2].pair2 = j;
                    }
                }
            }
        }
        vertex[index1++] = T[index2].pair2;
        index2++;
    }
}

int main(void) {
    printf(">> Minimum Spanning Tree (using Prim Algorithm)");
    prim(0);
    
    for(int i=0; i<MAX; i++)
        printf("\n(v%d , v%d) weight = %d", T[i].pair1+1, T[i].pair2+1,
               G[T[i].pair1][T[i].pair2]);
    return 0;
}
  • 수행결과

2017 IA Prim.png

코드 : Prim의 알고리즘으로 구현한 최소 신장트리2

#include <stdio.h>
#include <limits.h>

// Number of vertices in the graph
typedef int bool;
#define V 5
#define true 1
#define false 0

// A utility function to find the vertex with minimum key value, from
// the set of vertices not yet included in MST
int minKey(int key[], bool mstSet[])
{
    // Initialize min value
    int min = INT_MAX, min_index =0;
    
    for (int v = 0; v < V; v++)
        if (mstSet[v] == false && key[v] < min)
            min = key[v], min_index = v;
    
    return min_index;
}

// A utility function to print the constructed MST stored in parent[]
void printMST(int parent[], int n, int graph[V][V])
{
    printf("Edge   Weight\n");
    for (int i = 1; i < V; i++)
        printf("%d - %d    %d \n", parent[i], i, graph[i][parent[i]]);
}

// Function to construct and print MST for a graph represented using adjacency
// matrix representation
void primMST(int graph[V][V])
{
    int parent[V]; // Array to store constructed MST
    int key[V];   // Key values used to pick minimum weight edge in cut
    bool mstSet[V];  // To represent set of vertices not yet included in MST
    
    // Initialize all keys as INFINITE
    for (int i = 0; i < V; i++)
        key[i] = INT_MAX, mstSet[i] = false;
    
    // Always include first 1st vertex in MST.
    key[0] = 0;     // Make key 0 so that this vertex is picked as first vertex
    parent[0] = -1; // First node is always root of MST
    
    // The MST will have V vertices
    for (int count = 0; count < V-1; count++)
    {
        // Pick the minimum key vertex from the set of vertices
        // not yet included in MST
        int u = minKey(key, mstSet);
        
        // Add the picked vertex to the MST Set
        mstSet[u] = true;
        
        // Update key value and parent index of the adjacent vertices of
        // the picked vertex. Consider only those vertices which are not yet
        // included in MST
        for (int v = 0; v < V; v++)
            
            // graph[u][v] is non zero only for adjacent vertices of m
            // mstSet[v] is false for vertices not yet included in MST
            // Update the key only if graph[u][v] is smaller than key[v]
            if (graph[u][v] && mstSet[v] == false && graph[u][v] <  key[v])
                parent[v]  = u, key[v] = graph[u][v];
    }
    
    // print the constructed MST
    printMST(parent, V, graph);
}

// driver program to test above function
int main()
{
    int graph[V][V] = {{0, 2, 3, 0, 0},
        {2, 0, 15, 2, 0},
        {3, 15, 0, 0, 13},
        {0, 2, 0, 0, 9},
        {0, 0, 13, 9, 0}
    };
    
    // Print the solution
    primMST(graph);
    
    return 0;
}
  • 수행결과

2017 IA Prim2.png

과제 #4

  • 다음 그래프의 최소신장트리를 Prim algorithm과 Kruskal Algorithm 을 이용하여 구하여라
    • 그림의 a,b,c..는 0,1,2 인덱스로 대치하라
    • 프로그램 입력은 input.txt 파일을 이용하도록 하고 프로그램 코드와 수행결과 화면을 제출하라
    • 이때 Prim algorithm과 Kruskal Algorithm의 간 단계별 그래프를 화면에 출력하여라
    • 그리고 프로그램에서 구한 최소 신장트리를 각 단계별로 강의자료와 같이 이해하기 쉽게 손으로 직접 그려서 제출하라
  • 제출일 : 4월 11일

2017 IA MST report.png

6주차 (4월 9일, 11일)

강의자료 5장 : 동적계획법

과제 #5

  • 교재 4장 연습문제 풀이
    • 1,2,3,4,5,6,8,,12,13번 문제
    • 문제와 답 그리고 그 풀이과정을 손으로 적으시오
  • 제출일 : 4월 18일

코드 : Dijkstra Algorithm

#include <stdio.h>
#include <limits.h>
#include <stdbool.h>

// Number of vertices in the graph
#define V 9

// A utility function to find the vertex with minimum distance value, from
// the set of vertices not yet included in shortest path tree
int minDistance(int dist[], bool sptSet[])
{
    // Initialize min value
    int min = INT_MAX, min_index =0;
    
    for (int v = 0; v < V; v++)
        if (sptSet[v] == false && dist[v] <= min)
            min = dist[v], min_index = v;
    
    return min_index;
}

// A utility function to print the constructed distance array
void printSolution(int dist[], int n)
{
    printf("Vertex   Distance from Source\n");
    for (int i = 0; i < V; i++)
        printf("%d \t\t %d\n", i, dist[i]);
}

// Funtion that implements Dijkstra's single source shortest path algorithm
// for a graph represented using adjacency matrix representation
void dijkstra(int graph[V][V], int src)
{
    int dist[V];     // The output array.  dist[i] will hold the shortest
    // distance from src to i
    
    bool sptSet[V]; // sptSet[i] will true if vertex i is included in shortest
    // path tree or shortest distance from src to i is finalized
    
    // Initialize all distances as INFINITE and stpSet[] as false
    for (int i = 0; i < V; i++)
        dist[i] = INT_MAX, sptSet[i] = false;
    
    // Distance of source vertex from itself is always 0
    dist[src] = 0;
    
    // Find shortest path for all vertices
    for (int count = 0; count < V-1; count++)
    {
        // Pick the minimum distance vertex from the set of vertices not
        // yet processed. u is always equal to src in first iteration.
        int u = minDistance(dist, sptSet);
        
        // Mark the picked vertex as processed
        sptSet[u] = true;
        
        // Update dist value of the adjacent vertices of the picked vertex.
        for (int v = 0; v < V; v++)
            // Update dist[v] only if is not in sptSet, there is an edge from
            // u to v, and total weight of path from src to  v through u is
            // smaller than current value of dist[v]
            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
                && dist[u]+graph[u][v] < dist[v])
                dist[v] = dist[u] + graph[u][v];
        // 중간과정 출력
        // printSolution(dist, V);
    }
    
    // print the constructed distance array
    printSolution(dist, V);
}

// driver program to test above function
int main()
{
    /* Let us create the example graph discussed above */
    int graph[V][V] = {{0, 4, 0, 0, 0, 0, 0, 8, 0},
        {4, 0, 8, 0, 0, 0, 0, 11, 0},
        {0, 8, 0, 7, 0, 4, 0, 0, 2},
        {0, 0, 7, 0, 9, 14, 0, 0, 0},
        {0, 0, 0, 9, 0, 10, 0, 0, 0},
        {0, 0, 4, 14, 10, 0, 2, 0, 0},
        {0, 0, 0, 0, 0, 2, 0, 1, 6},
        {8, 11, 0, 0, 0, 0, 1, 0, 7},
        {0, 0, 2, 0, 0, 0, 6, 7, 0}
    };
    
    dijkstra(graph, 0);
    
    return 0;
}
  • 수행결과

2017 IA Dijkstra.png

코드 : 배낭문제 fractionalKnapsack.cpp

  • 비고 C++로 작성된 코드임
// C/C++ program to solve fractional Knapsack Problem
#include <iostream>

using namespace std;

// Stucture for Item which store weight and corresponding
// value of Item
struct Item
{
    int value, weight;
    
    // Constructor
    Item(int value, int weight) : value(value), weight(weight)
    {}
};

// Comparison function to sort Item according to val/weight ratio
bool cmp(struct Item a, struct Item b)
{
    double r1 = (double)a.value / a.weight;
    double r2 = (double)b.value / b.weight;
    return r1 > r2;
}

// Main greedy function to solve problem
double fractionalKnapsack(int W, struct Item arr[], int n)
{
    // sorting Item on basis of ration
    sort(arr, arr + n, cmp);
    
    // Uncomment to see new order of Items with their ratio
    for (int i = 0; i < n; i++)
    {
     cout << "Value = " << arr[i].value << " " << " Weight = " << arr[i].weight
     << " Value/Weight = " << ((double)arr[i].value / arr[i].weight) << endl;
    }
    
    int curWeight = 0; // Current weight in knapsack
    double finalvalue = 0.0; // Result (value in Knapsack)
    
    // Looping through all Items
    for (int i = 0; i < n; i++)
    {
        // If adding Item won't overflow, add it completely
        if (curWeight + arr[i].weight <= W)
        {
            curWeight += arr[i].weight;
            finalvalue += arr[i].value;
        }
        // If we can't add current Item, add fractional part of it
        else
        {
            int remain = W - curWeight;
            finalvalue += arr[i].value * ((double) remain / arr[i].weight);
            break;
        }
    }
    
    // Returning final value
    return finalvalue;
}

// driver program to test above function
int main()
{
    int W = 40; // Weight of knapsack
    Item arr[] = {{50000, 50}, {600000, 10}, {100000, 25}, {750000, 15}};
    
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Weight of Knapsack = " << W << endl;
    int result = fractionalKnapsack(W, arr, n);
    cout << "Maximum value we can obtain = " << result << endl;
    return 0;
}
  • 수행결과

2017 IA FractionalKnapsack.png

#TOP - 위로 이동

7주차 강의(4월 16일, 18일)

  • 도시간의 거리를 계산하는 동적 계획법
    • All shortest path를 구하기 위한 Floyd-Warshall 알고리즘

코드 : Floyd-Warshall 알고리즘

// Floyd Warshall 알고리즘의 c 코드
#include<stdio.h>

// 그래프의 정점은 4개로 두자
#define V 4

/* 서로 연결되지 않은 정점간의 거리는 최대값으로 두자 */
#define INF 99999

// 그래프를 출력하는 함수
void printGraph(int dist[][V]);

// Solves the all-pairs shortest path problem using Floyd Warshall algorithm
void floydWarshall (int graph[][V])
{
    /* dist[][] will be the output matrix that will finally have the shortest
     distances between every pair of vertices */
    int dist[V][V], i, j, k;
    
    for (i = 0; i < V; i++)
        for (j = 0; j < V; j++)
            dist[i][j] = graph[i][j];
    
    for (k = 0; k < V; k++)
    {
        // Pick all vertices as source one by one
        for (i = 0; i < V; i++)
        {
            for (j = 0; j < V; j++)
            {
                if (dist[i][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }
    
    printf("Solution Graph\n");
    printGraph(dist);
}

/* A utility function to print solution */
void printGraph(int dist[][V])
{
    for (int i = 0; i < V; i++)
    {
        for (int j = 0; j < V; j++)
        {
            if (dist[i][j] == INF)
                printf("%7s", "INF");
            else
                printf ("%7d", dist[i][j]);
        }
        printf("\n");
    }
}

// driver program to test above function
int main()
{
    /* Let us create the following weighted graph
          10
     (0)------->(3)
     |         /|\
   5 |          |
     |          | 1
    \|/         |
    (1)------->(2)
     3           */
    int graph[V][V] = { {0,   5,  INF, 10},
        {INF, 0,   3, INF},
        {INF, INF, 0,   1},
        {INF, INF, INF, 0}
    };
    
    printf("Original Weighted Graph\n");
    printGraph(graph);
    // Print the solution
    floydWarshall(graph);
    
    return 0;
}
  • 수행결과

2017 IA FloydWarshall.png

#TOP - 위로 이동

8주차 강의(4월 23일, 25일 ) : 중간시험

중간고사

  • 알립니다 - 중간고사
  • 날짜 : 4월 23일 화요일 12:00
      • 범위 : 교재 5장 동적계획법 AllPairsShortest 알고리즘과 MatrixChainMultiplication 문제까지
      • 문제유형 : 단답식 주관식문제와 간단한 프로그램 코딩 문제
      • 교재 Exercise 문제를 많이 풀어보기 바랍니다

Self study

  • ivis.kr 위키페이지의 Floyd-Warshall 알고리즘을 교재 5장 p145쪽의 예제에 대하여 적용시켜 보자
    • k = 1…5가 될때까지의 각 단계별로 Table의 변화 값을 출력시켜보도록 하자
    • (교재와 비교하여 제출하자)
    • 프로그램 작성후 느낀 점을 적어서 제출할 것

코드 : Matrix Chain Multiplication

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

// Matrix Ai has dimension d[i-1] x d[i] for i = 1..n
int MatrixChainOrder(int d[], int n)
{
	/* For simplicity of the program, one extra row and one
	extra column are allocated in m[][]. 0th row and 0th
	column of C[][] are not used */
	int **C = (int **)malloc(n * sizeof(int *));
	int i, j, k, L, temp;
	// calloc을 이용하여 행의 원소값을 0으로 초기화 함
	for (i = 0; i < n; i++)
		C[i] = (int *)calloc(n, sizeof(int));

	/* m[i,j] = Minimum number of scalar multiplications needed
	to compute the matrix A[i]A[i+1]...A[j] = A[i..j] where
	dimension of A[i] is p[i-1] x p[i] */

	// L is chain length.
	for (L = 1; L < n; L++) {  // 부분 문제의 크기는 1, 2, 3, ...
		for (i = 1; i < n - L; i++) {
			j = i + L;
			C[i][j] = INT_MAX;
			for (k = i; k <= j - 1; k++) {
				// d = cost/scalar multiplications
				temp = C[i][k] + C[k+1][j] + d[i-1] * d[k] * d[j];
				// 중간 과정을 출력하는 코드
				printf("L=%d : [i=%d, j=%d, k=%d], C[i,k]=%3d + C[k+1,j]=%3d + d[i-1]*d[k]*d[j]=%3d(%3d)\n", \
					L, i, j, k, C[i][k], C[k+1][j], d[i-1] * d[k] * d[j], temp);
				if (temp < C[i][j])
					C[i][j] = temp;
			}

			// 중간 행렬을 출력하는 코드
			for (int i2 = 1; i2 < n; i2++) {
				for (int j2 = 1; j2 < n; j2++)
					printf("%10d ", C[i2][j2]);
				printf("\n");
			}
			printf("\n");
		}
	}

	return C[1][n - 1];
}

int main()
{
	int arr[] = { 3, 4, 5, 2, 10 };
	int size = sizeof(arr) / sizeof(arr[0]);

	printf("Minimum number of multiplications is %d \n",
		MatrixChainOrder(arr, size));

	return 0;
}
  • 실행결과 - 윈도우즈
섬네일을 만드는 중 오류 발생:
Error code: 2

#TOP - 위로 이동

9주차(4월 30, 5월 2일)

  • 동적계획법에 대해 알아봅시다.
    • 편집거리 문제
    • 배낭 문제

코드 : Longest Common Subsequence

/* Dynamic Programming implementation of LCS problem */
#include <iostream>
#include <cstring>
#include <cstdlib>

#define max(x,y) ((x) >= (y)) ? (x) : (y)

using namespace std;

/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
void lcs(char *X, char *Y, int m, int n)
{
	//int L[m + 1][n + 1];
	int **L = (int **)malloc((m+1)*sizeof(int *));
	for (int i = 0; i <= m; i++)
		L[i] = (int *)malloc((n+1)*sizeof(int));
	
	/* Following steps build L[m+1][n+1] in bottom up fashion. Note
	that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */
	for (int i = 0; i <= m; i++)
	{
		for (int j = 0; j <= n; j++)
		{
			if (i == 0 || j == 0)
				L[i][j] = 0;
			else if (X[i - 1] == Y[j - 1])
				L[i][j] = L[i - 1][j - 1] + 1;
			else
				L[i][j] = max(L[i - 1][j], L[i][j - 1]);
		}
	}

	// Following code is used to print LCS
	int index = L[m][n];
	
	// Create a character array to store the lcs string
	//char lcs[index + 1];
	char *lcs = (char *)malloc((index + 1)*sizeof(char));

	lcs[index] = '\0'; // Set the terminating character

					   // Start from the right-most-bottom-most corner and
					   // one by one store characters in lcs[]
	int i = m, j = n;
	while (i > 0 && j > 0)
	{
		// If current character in X[] and Y are same, then
		// current character is part of LCS
		if (X[i - 1] == Y[j - 1])
		{
			lcs[index - 1] = X[i - 1]; // Put current character in result
			i--; j--; index--;     // reduce values of i, j and index
		}

		// If not same, then find the larger of two and
		// go in the direction of larger value
		else if (L[i - 1][j] > L[i][j - 1])
			i--;
		else
			j--;
	}

	// Print the lcs
	cout << "LCS of " << X << " and " << Y << " is " << lcs << endl;
}

/* Driver program to test above function */
int main()
{
	char X[] = "AGGTAB";
	char Y[] = "GXTXAYB";
	int m = strlen(X);
	int n = strlen(Y);
	lcs(X, Y, m, n);
	return 0;
}

코드 : Edit Distance

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

// 세 수 중에서 가장 작은 값을 반환하는 유틸리티 함수
int min(int x, int y, int z)
{
    int m;
    if (x > y)
        m = y;
    else
        m = x;
    
    if (m > z)
        return z;
    else
        return m;
}

int editDistDP(char str1[], char str2[], int m, int n)
{
    // Create a table to store results of subproblems
    //int dp[m + 1][n + 1];
    int **dp = (int **)malloc((m+1)*sizeof(int *));
    
    for (int i = 0; i <= m; i++) // 각 열의 원소를 초기화 함
        dp[i] = (int *)calloc((n+1), sizeof(int));
    
    for (int i = 0; i <= m; i++) {// 0번 열 초기화
        dp[i][0] = i;
        printf("i = %d ", i);
    }
    
    for (int j = 0; j <= n; j++) // 0번 행 초기화
        dp[0][j] = j;
    
    // Fill d[][] in bottom up manner
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            // If last characters are same, ignore last char
            // and recur for remaining string
            if (str1[i - 1] == str2[j - 1])
                dp[i][j] = dp[i - 1][j - 1];
            // If last character are different, consider all
            // possibilities and find minimum
            else
                dp[i][j] = 1 + min(dp[i][j - 1],  // Insert
                                   dp[i - 1][j],  // Remove
                                   dp[i - 1][j - 1]); // Replace
            
            printf("\n== step(각 단계별 상황) %d ==\n",i);
            for (int a = 0; a <= m; a++) {
                for (int b = 0; b <= n; b++)
                    printf("%2d", dp[a][b]);
                printf("\n");
            }
        }
    }
    
    return dp[m][n];
}

// Driver program
int main()
{
    // your code goes here
    char str1[100] = "strong";
    char str2[100] = "stone";
    
    printf("Edit distance of %s, %s is %d\n", str1, str2,
           editDistDP(str1, str2, (int)strlen(str1), (int)strlen(str2)));
    
    return 0;
}
섬네일을 만드는 중 오류 발생:
Error code: 2

과제 #6

  • 제목 : 5장 연습문제 풀이 1, 2, 5, 6, 7, 8, 9, 10번
    • 각 동적계획법 문제의 풀이과정과 정답을 손으로 적도록 하시오

10주차(5월 7일 9일)

  • 동적계획법
    • 0/1 Knapsack 문제

코드 : 0/1 Knapsack 문제

#include <stdio.h>

int max(int a, int b)
{
    if( a > b)
        return a;
    else
        return b;
}

// Returns the maximum value that can be put in a knapsack of capacity W
int knapSack(int C, int wt[], int val[], int n)
{
    int i, w;
    int K[n+1][C+1];
    
    // Build table K[][] in bottom up manner
    for (i = 0; i <= n; i++)
    {
        for (w = 0; w <= C; w++)
        {
            if (i==0 || w==0)
                K[i][w] = 0;
            else if (wt[i-1] > w)
                K[i][w] = K[i-1][w];
            else
                K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]);
        }
        printf("\ni = %d \n", i);
        for(int a=0; a <= n; a++) {
            for(int b=0; b <= C; b++)
                printf("%2d ", K[a][b]);
            printf("\n");
        }
    }
    
    return K[n][C];
}

int main()
{
    int val[] = {10, 40, 30, 50};
    int wt[] = {5, 4, 6, 3};
    int  W = 10;
    int n = sizeof(val)/sizeof(val[0]);
    printf("\nMax value = %d \n", knapSack(W, wt, val, n));
    return 0;
} 

정렬 알고리즘

강의자료 : 6장 정렬알고리즘

#TOP - 위로 이동

11주차 (5월 14, 16일)

  • 정렬 알고리즘

강의자료 : 7장 NP완전문제

과제 #7

  • 교재 6장 연습문제 풀이
    • 1-15번 문제
    • 문제와 답 그리고 그 풀이과정을 손으로 적으시오
  • 제출일 : 5월 28일

12주차 강의( 5월 21일, 23일 )

  • P문제와 NP완전 문제
  • NP 완전 문제
    • P 문제와 NP 문제의 차이점과 특징에 대하여 알아본다
    • NP 완전 문제의 활용에 대해 알아본다
    • 알고리즘에서 Reduction의 중요성을 이해한다
  • 8장의 근사 알고리즘에 대해 알아봅시다
    • 여행자 문제, 정점 커버 문제, 통 채우기 문제, 작업 스케줄링 문제, 클러스터링 문제

13주차 강의(5월 28일, 30일 )

  • 근사 알고리즘에 대해 알아봅시다

강의자료 8장

과제 #8

  • 제목 : 교재 7장 연습문제 풀이
    • 1번 - 13번 문제 풀이
  • 제출일 : 6월 3일 수업시간까지

과제 #9

  • 동영상 내용 요약하기
  • 제출일 : 6월 7일 금요일
  • 제출방법 : 학과 사무실 우편함에 넣어두세요

#TOP - 위로 이동

14주차(6월 4일, 6일)

강의자료 9장

15주차(6월 11일 13일)

  • 보충강의 기간

기말 평가

  • 날짜 : 2019년 6월 18일 화요일 오후 12:00-2:00
    • 평가범위 : 알고리즘 교재의 5장 - 8장
    • 문제유형 : 중간시험과 유사함 단답식 주관식문제와 간단한 단계별 풀이문제등
      • 논술형 에세이 문제도 출제됩니다( 예:P 와 NP문제를 설명하고 그 차이점을 서술하시오등)
    • 과제와 교재 Exercise 문제를 많이 풀어보기 바랍니다.
    • 한학기동안 수고하셨습니다.