[자료구조] ep7++) 결정 트리(decision tree) - 양자택일식 문답시스템

 

ㅇ결정 트리(decision tree): 의사결정 과정과 연관된 이진트리

- 내부노드: yes/no로 답 할 수 있는 질문

- 외부노드(리프): 결정

 

 

 

 

활용) 프로그램 요구사항

다음과 같이 한 프로그램 내에서 양자택일식 문답시스템의 구축과 사용을 연속하여 지원하는 프로그램을 작성하라.

 

1) 문답시스템 구축 지원 기능

-  결정트리는 배열 또는 연결리스트 가운데 하나를 이용하여 구축되어야 한다.

-  1회의 상담은 최소 3회 ~ 최대 5회의 문답을 통해 완료되도록 제한하라(즉, 상담설계자가 이 시스템을 이용하여 최소 8개 ~ 최대 32개의 결정을 포함하는 결정트리의 구축을 지원할 수 있어야 한다).

-  설계된 결정트리를 프로그램을 통해 구축하라(즉, buildDecisionTree를 1회 호출).

 

2) 상담 지원 기능

-  앞서 구축된 테스트 결정트리를 이용한 테스트 상담 3회 수행을 지원하도록 하라(즉, runDecisionTree를 3회 호출).

-  3회의 상담에서, 상담 내용이 상이한 3인의 상담고객(즉, 최종사용자)을 모의수행함으로써 3개의 상이한 결정이 출력되는지 확인하라.

 

 

의사 코드

 

주의

1)  주함수 예시처럼 한 프로그램 내에서 시스템 구축과 이를 이용한 상담을 연속하여 진행하도록 작성하라.

2)  프로그램은 상담설계자의 필요에 따라 최소 3회에서 최대 5회까지의 문답을 지원하도록 작성되어야 한다. 즉, 1~2회의 문답만 진행해도 결정을 해주는 경우가 있거나, 5회의 문답까지 진행해도 결정을 해주지 못하는 경우가 있다면, 요구조건을 충족하지 못한 것이 된다.

3) 문답 횟수는 고정적인 것이 아니다. 즉, 1회의 상담에서, 상담설계자의 필요에 따라, 문답 3회, 4회, 또는 5회 만에 결정을 해줄 수도 있어야 한다.

 

 

 

 

음료수 추천에 대한 결정 트리를 짜 보았다

 

모식도

 

 

 

 

(전체 코드)

// 양자택일식 문답시스템
// 음료수 추천 결정트리
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 노드 구조체 정의
typedef struct NODE {
    char question[100];       // 질문을 저장할 문자열
    struct NODE *nextYes;     // 예(yes)로 대답할 경우의 다음 노드
    struct NODE *nextNo;      // 아니오(no)로 대답할 경우의 다음 노드
} NODE;

NODE* createNode(char* question); // 노드 생성 함수
NODE* buildDecisionTree(); // 결정 트리 구축 함수
void runDecisionTree(NODE* node); // 상담 수행 함수

int main() {
    // 결정 트리 구축
    NODE* root = buildDecisionTree();
    printf("Tree complete. Now Running!!\n\n");
    
    // 3회 테스트 상담 수행
    for (int i = 0; i < 3; i++) {
        printf("Test Run %d)\n", i);
        runDecisionTree(root);
    }
    
    // 노드의 메모리 해제를 위해 트리를 순회하며 free 호출 필요
    free(root);
    return 0;
}

// 노드 생성 함수
NODE* createNode(char* question) {
    NODE* newNode = (NODE*)malloc(1 * sizeof(NODE)); // 새로운 노드 동적 할당
    strcpy(newNode->question, question);             // 질문을 노드에 복사
    newNode->nextYes = NULL;                         // 예(yes) 대답 노드 초기화
    newNode->nextNo = NULL;                          // 아니오(no) 대답 노드 초기화
    return newNode;                                  // 생성된 노드 반환
}

// 결정 트리 구축 함수
NODE* buildDecisionTree() {
    // 루트 노드 생성 및 질문 설정
    NODE *root = createNode("탄산을 원하시나요?");
    
    // 1번째 수준 질문
    root->nextYes = createNode("단 것을 원하시나요?");
    root->nextNo = createNode("과일음료를 원하시나요?");
    
    // 2번째 수준 질문
    root->nextYes->nextYes = createNode("제로음료를 원하시나요?");
    root->nextYes->nextNo = createNode("술을 원하시나요?");
    root->nextNo->nextYes = createNode("커피를 원하시나요");
    root->nextNo->nextNo = createNode("단 것을 원하시나요?");
    
    // 3번째 수준 질문
    root->nextYes->nextYes->nextYes = createNode("[제로콜라를 추천합니다]");
    root->nextYes->nextYes->nextNo = createNode("[콜라를 추천합니다]");
    root->nextYes->nextNo->nextYes = createNode("[맥주를 추천합니다]");
    root->nextYes->nextNo->nextNo = createNode("[탄산수를 추천합니다]");
    root->nextNo->nextYes->nextYes = createNode("[바나나라떼를 추천합니다]");
    root->nextNo->nextYes->nextNo = createNode("술을 원하시나요?");
    root->nextNo->nextNo->nextYes = createNode("[초코우유를 추천합니다]");
    root->nextNo->nextNo->nextNo = createNode("[생수를 추천합니다]");
    
    // 4번째 수준 질문
    root->nextNo->nextYes->nextNo->nextYes = createNode("와인을 원하시나요?");
    root->nextNo->nextYes->nextNo->nextNo = createNode("[오렌지 주스를 추천합니다]");
    
    // 5번째 수준 질문 및 리프 노드
    root->nextNo->nextYes->nextNo->nextYes->nextYes = createNode("[와인을 추천합니다]");
    root->nextNo->nextYes->nextNo->nextYes->nextNo = createNode("[사과주를 추천합니다]");

    return root; // 트리의 루트 노드 반환
}

// 상담 수행 함수
void runDecisionTree(NODE* node) {
    char answer[100] = {0}; // 사용자의 응답을 저장할 문자열
    while (node != NULL) {
        printf("%s (yes/no): ", node->question); // 현재 노드의 질문 출력
        scanf("%s", answer);                     // 사용자로부터 응답 입력 받음
        
        // 사용자의 응답에 따라 다음 노드로 이동
        if (strcmp(answer, "yes") == 0) {
            node = node->nextYes;
        } 
        else if (strcmp(answer, "no") == 0) {
            node = node->nextNo;
        } 
        else {
            printf("Invalid answer. Please respond with 'yes' or 'no'.\n");
        }
        
        // 현재 노드가 리프 노드인 경우, 결과 출력 후 종료
        if (node->nextYes == NULL && node->nextNo == NULL) {
            printf("%s\n\n", node->question);
            break;
        }
    }
}

 

 

 

 

 

 

 

 

 

참고 및 출처: 데이터 구조 원리와 응용(국형준교수님)