하지만, a테이블이 생성되면 b테이블이 자동 생성되는건 jpa가 지원하는 기능이 아니다.. 사람 손으로 직접 만들어 줘야하는 것이었던 것이다.

유저가 존재하면 유저의 누적점수는 필히 존재한다. ( 상식 ) 그러나 java는 그렇게나 친절하지는 않아서 유저가 생성되면 누적점수도 같이 생성되고, 어떻게 생성되는지 써 주라고 한다.

@PostPersist
    public void createPersonalScore() {
        if (this.personalScore == null) {
            this.personalScore = new CopyOfPersonalScore();
            this.personalScore.setUser(this);
            this.personalScore.setTotalPlays(0);
            this.personalScore.setTotalScoreSum(0);
            this.personalScore.setHighScore(0);
        }
    }

이렇게 작성하면 유저id와 1ㄷ1로 매핑되는 점수 테이블도 같이 생성되게 된다.

또한, 실수한 것이 있는데, Cascade와 같은 부분이다. 만약 cascade 설정을 하게 되어서, 회원이 삭제가 되면, 게임 내용도 삭제되는 것이다.

만약 프로그램이 더 발전하게 되면, 프로그램 내부에서 전적을 볼 수 있게 된다면, 프로그램 내부 전적 확인에서 한 회원탈퇴를 한 유저가 있다면 오류가 발생하고 말 것이다. 이점 또한 유의하여 조심해야 할 것이다.

또한 이전까지 모든 pk(fk)를 int로 설정하곤 했는데, BIGINT로 설정하는 것이 더 합리적이다. 일단 기본으로 Long 타입으로 설정하는 것이 context에 부합하기 때문이다.

chatgpt나 copilot이 그런 식으로 써서 그런건 안비밀이다.

1. 우선 application.properties와 같은 git업로드가 안되는 가려진 파일에 api key를 작성을 한다. 보안을 위해

--> 이 부분에서 미스를 하게 되면 이후에 상당한 고생을 하게 된다. 추후에 설명하겠음

2. 서비스의 구현 방식마다 차이가 있지만 Spring Boot에서 가장 흔하게 할 법한 방식은 따로 구성된 디렉토리 config / dto / controller / service에 각각의 role을 만들어 주는 것이다.

config에는 OpenAI를 이루는 구성요소, http 클라이언트 템플릿 빈을 이용하여 호출하므로

''' @Bean public RestTemplate restTemplate(){ return new RestTemplate(); } '''

이런 식으로 구성하면 http 통신을 시킬 수 있겠지.

다음은 dto와 service를 한꺼번에 설명하겠다.

dto는 데이터 전송 객체들을 정의하는 단락이다. openAI api의 경우 request(요청),과 response(응답)이 있다. 먼저 request의 경우 응답할 데이터의 구조를 설명하고 있습니다. 모델명은 뭔지, 역할은 어떻게 설정했는지

해당 모두의 객체들을 적절히 구성해주어야 한다.

그리고 response의 경우, 반환된 내용들을 가져옵니다. 어떠한 내용들을 가져올지 또한 구조체 내에서 구성할 수 있습니다.

그리고 service 단에서 해당 service를 구현하는 것이다. 먼저 모델의 요청 구조를 세팅한다. 응답 구조 또한 원하면 세팅할 수 있다. 예를들어서 model은 davinci-003을 사용하고 프롬포트는 받아오고, 토큰의 최대 갯수는 150개, 창의성은 0.7정도로 조정하자면,

코드는 이렇게 짤 수 있는 것이다.

''' OpenAIRequest request = new OpenAIRequest(); // 요청 데이터를 담는 dto request.setModel("text-davinci-003"); // 사용 모델 설정 request.setPrompt(prompt); // 사용 프롬포트 설정 request.setMaxTokens(150); request.setTemperature(0.7); '''

이러한 서비스의 작성으로 유추할 수 있듯이 controller는 쉽게 작성 가능하다. 그냥 prompt에 맞춰서 작성해달라고 controller에 쓰면 되는것이다.

기존의 http 요청을 통해 클라이언트가 서버에 데이터를 요청하면 서버에서 데이터를 받아옵니다.

그러나, 이러한 경우에는 클라이언트가 서버에 요청한 경우에만 데이터를 받아옵니다.

그렇기에, 클라이언트와 서버가 지속적으로 소통을 하려면 클라이언트와 서버를 핸드셰이크라는 과정을 과정을 통해서 웹 소켓 형태가 된다. 그래서 클라이언트와 서버가 실시간 통신 상태가 된다.

but. WebSocket만 쓰면 여러 클라이언트가 있는 상황에서 메시지를 정리하고 나눠주는 게 어려워짐

• stomp라는 메시지 기반 프로토콜을 통해서 전달하는 것도 추가하여서 클라이언트 간 소통을 쉬이 하도록 함

하는 과정

1. 클라이언트가 주소의 메시지를 받음(/topic/chat) (subscribe)
2. 메시지 보내기(/app/message)(Send)
3. 서버가 메시지 전달(topic/chat)

클라이언트가 어떤 주제를 구독할지 정의함 / 클라이언트가 특정 경로로 발행하는 것으로 지원 / 메세지 형식 정의

메세지 구조

1. 명령(메시지의 동작을 정의 (예: CONNECT, SEND, SUBSCRIBE, MESSAGE)
2. 헤더( 메시지의 속성을 정의 (예: destination, content-type)
3. 본문 ( 실제 메시지 내용)

Spring Boot에서 처리하는 방식

1. 의존성 추가.
2. 웹소켓 설정 구성 파일과 구성 파일 요소 설명

• 웹소켓 설정은 configuration으로 설정. 메시지 처리는 controller, 클라이언트 코드는 프론트 단에서 처리..

지인이랑 대충 겹치는 요소인 Spring Boot(Java 21), mysql, 타임리프를 사용해서 만들기로 했다.

뭐 대강 이렇게 erd를 짜고,

만들어야 하는것을 구상했다. 만들어야 하는 것은

만들어야하는 서비스

1. 로그인/ 회원가입 기능
2. 게임 관리 서비스

• 게임 방 생성
• 게임 방 참여
• 게임 방 나가기
• 게임 상태 업데이트
• 게임 결과 저장

1. 점수 관리 서비스

• 사용자 점수 및 순위 관리
• 게임 결과 기반 점수 계산

1. openai api 호출

• 답변 제출
• 번역 문장 생성
• 번역 평가
• 호출 로깅

1. 메세지 처리

• 메세지 보내기
• 연결되고 연결 해제될 때

1. 기록 조회

• 사용자 기록 조회

만들어야 되는 컨트롤러

1. 메시지를 처리하는 컨트롤러
2. 결과를 저장하는 컨트롤러
3. 로그인/회원 가입 컨트롤러
4. OpenAI API 컨트롤러
5. 게임 방 관리 컨트롤러
6. 기록 조회 컨트롤러

만들어야 하는 페이지(프론트)

1. 회원 가입 페이지
2. 로그인 페이지
3. 내 정보 페이지(개인기록)
4. 게임 방 만들기 페이지
5. 방 찾기 페이지(메인 페이지)
6. 게임 시작 전 대기실 페이지
7. 게임 내부 페이지

다음과 같이 만들기로 했다.

먼저 왼쪽으로 이동 후 방문 후 다시 오른쪽을 preorder, 왼쪽으로 이동 후 오른쪽으로 다시 가서 읽는 것을 inder, 그리고 오른쪽으로 간 뒤 읽고 왼쪽으로 가는 것은 postorder라고 합니다.

stack과 queue를 사용하지 않아도, 물론 구현할 수 있다. 해당 코드들은 재귀형식으로 구현 가능하다.

이번에는 stack을 활용하여 작성하여 보겠습니다.

먼저 stack을 사용하는 건 postorder과 inorder이 있습니다.

먼저 inorder을 작성해보겠습니다

typedef struct Node{ //노드 하나를 선언합니다
  int data;
  struct Node* left; // 좌하행 간선입니다
  struct Node* right; // 우하행 간선입니다
};
struct Node* createNode(int data){ // 노드를 생성하는 함수입니다
  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); // malloc을 이용해 메모리를 할당합니다
  newNode-> data = data; // 인자에 들어가는 값을 데이터로 사용합니다
  newNode -> left = NULL; // 좌하행 간선을 NULL로 연결시킵니다
  newNode -> right = NULL; // 우하행 간선을 NULL로 연결시킵니다
  return newNode;

}
void inorderTraversal(struct Node* root){ // 코드를 출력하는 함수입니다
  if(root == NULL){
    return; // 스택이 비어있다면 리턴합니다
  }
  struct Node* stack[100]; // 스택을 선언합니다.
  int top = -1; // 스택을 초기화합니다
  struct Node* current = root; // 스택의 첫번째 값
  while (current != NULL || top >= 0) { current가 널이 아닐때까지
      while (current != NULL) { // 현재가 null일 때까지
          stack[++top] = current; // current를 스택에 집어넣음
          current = current->left; // left로 집어넣음
      }
      current = stack[top--]; // 이전 스택에 있는 값
      printf("%d ", current->data); // 값을 출력함
      current = current->right; // 
  }
}


int main(void) {
  struct Node* root = createNode(1);
  root-> left = createNode(2);
  root-> right = createNode(3);
  root -> left -> left = createNode(4);
  root->left->right =createNode(5);
  root -> right ->left = createNode(6);
  root -> right -> right = createNode(7);
  inorderTraversal(root);


  return 0;
}

위의 코드를 분석해 보겠습니다. 코드는 stack을 활용한 것으로, current에 하나씩 저장합니다. 일단 left를 전부 이동하여 저장 후 없으면 right, 그리고 다시 이전 스택에 있는 값을 불러오도록 합니다. 그래서 inorder을 만들었습니다. 그렇다면 postorder는 어떻게 만들까요? struct 선언까지는 앞과 같습니다.

void postorderTraversal(struct Node* root){ // 후위 순회를 하는 알고리즘
  if(root == NULL){ 
    return;
  }
  struct Node* stack[100]; // 스택을 정의
  int top = -1; // 초기화
  struct Node* lastVisited = NULL; // 이전 값을 저장할 배열을 정의
  struct Node* current = root; // 값을 넣을 배열 포인터선언
  while(current != NULL || top >=0){ // 반복
    while(current != NULL){ // 현재값이 널이 아닐때까지 반복
      stack[++top] = current; // 스택에 값을 저장
      current = current -> left; // 값을 왼쪽으로 이동

    }
    struct Node* peekNode = stack[top]; // pop되는 값을 저장함
    if(peekNode -> right != NULL && lastVisited != peekNode -> right){ // 우하향 노드가 널이고 이전에 방문한 노드에 right가 있을때
      current = peekNode-> right; // right로 향함
    }
    else{
      printf("%d ", peekNode->data); // data를 찍음
      lastVisited = stack[top--]; // 이전 값으로 
    }
  }

이 코드를 해석하겠습니다. tree의 postorder를 순회하는 코드입니다. 스택에서 null일때까지 쭉 갑니다. 그리고 pop된 값을 출력하도록 포인터를 작성해줍니다. 그 포인터의 right가 널이고 전에 방문한 값이 이전 값이 right로 향하는 간선이 null이 아니라면 right로 향합니다. 그리고 data를 찍습니다. 그리고 이전 값으로 이동합니다.

응용 프로그램에서 송신하는 정보를 전달 -> 안정적인 송신을 위해 정보를 더하고 뺌 -> 송신하려는 정보의 송수신지를 결정 -> 송수신라는 매체를 유무선으로 주고받음 -> 수신하려는 정보의 송수신지를 결정 -> 안정적인 수신을 위해 정보를 더하고 뺌 -> 응용 프로그램에서 수신하려는 정보를 전달

위를 보면 내용이 대칭적이다.

왜 이렇게 설계해야 할까?

1) 네트워크 구성과 설계에 용이하다.

• 각 계층이 수행할 역할
• 각 계층별 목적에 복한하는 장비 사용에 적합함.(모든 장비가 호환되는 건 아니나. 참조모델은 훌륭한 가이드라인을 제시함)

2) 네트워크 문제 진단과 해결이 용이함

• 몇계층에서 발생한 문제인지 순차적으로 환인 가능

네트워크 참조 모델인 OSI 모델과 TCP/IP

OSI 모델

OSI 모델은 7개의 계으로 구성됩니다. 응용, 표현, 세션, 전송, 네트워크, 데이터링크, 물리 계층으로 구성됩니다.

(1) 물리 계층 물리 계층은 OSI의 최하단에 있는 계층입니다. 1과 0의 비트 신호를 주고 받는 계층입니다. 1과 0으로 이루어진 비트 데이터는 다양한 매체를 통해 변환이 이루어지고 송수신합니다.

(2) 데이터 링크 계층 데이터링크 계층은 내 주변 장치 간 정보를 주고받는 계층이고 '이더넷'은 포함한 LAN 기술이 데이터링크 계층에 녹아있습니다. MAC주소라는 주소 체계를 통해 송수신지를 틍정할 수 있습니다. 전송 과정에서 발생하는 문제를 해결하빈다.

(3) 네트워크 기술 네트워크 기술은 메시지를 수신지까지 전달하는 계층입니다. 네트워크 계층에서는 IP주소라는 주소 체계를 통해 통신하고 하는 수신지 호스트와 네트워크 간의 통신이 이루어집니다.

(4) 전송 계층 신뢰성 있고 안정성 있는 전송을 할 때 필요한 계층입니다. 유실된 정보라던가, 순서가 뒤바뀌거가 하는 것을 검사합니다. PORT라는 정보를 통해 응용프로그램의 식별이 이루어지기도합니다.

(5) 세션 계층 세션을 관리하는 계층입니다. 세션이라는 용어는 폭넓게 사용되나, 응용 프로그램 간 연결 상태를 의해합니다. 연결상태를 생성하거나 유지하거나 종료하거나 등의 역할을 담당합니다.

(6) 표현 계층 번역가와 같은 역할입니다. 사람이 이해할 있도록 변환합니다.

(7) 응용 계층 최상단에 있는 계층으로 사용자가 이용하는 응용 프로그램과 맞닿아 있습니다. 실질적 네트워크 서비스 제공을 하는 계층입니다.

TCP/IP모델

'실용적 구현'에 중심을 준 네트워크 참조모델입니다. TCP/IP 모델은 TCP/IP 4계층, internet protocol suite, TCP/IP 프로토콜 스택으로도 부릅니다.

IP는 인터넷 프로토콜의 약자입니다. (IP주소의 IP와 같습니다)

TCP/IP 4계층는 응용계층, 전송계층, 인터넷 계층, 네트워크 액세스 계층이 존재하는데,

먼저 네트워크 액세스 계층은 OSI 모델의 데이터 링크 계층과 매우 유사합니다 둘째로 인터넷 계층은 OSI 모델의 네트워크 계층과 매우 유사합니다 셋째로 전송 계층은 OSI 모델의 전송 계층 계층과 매우 유사합니다 마지막으로 응용 계층은 OSI 모델의 세션계층 + 표현 계층 + 응용 계층과 매우 유사합니다

일단 첫번째로 row, col, value의 데이터가 들어간 Node를 뒤의 Node로 link시켜서 만드는.. 연결 리스트가 생각납니다. 그러나 더 효과적인 방법은 없을까요?

2차원 형식으로 작성하는 건 어떨까요? 코드의 기본 틀을 작성하면 이렇게 됩니다.

typedef enum {head, entry} tagfield;

// 데이터를 저장하는 노드 구조체
struct entry_node {
    int row;
    int col;
    int value;
};

// 매트릭스의 노드를 나타내는 구조체
struct matrix_node {
    struct matrix_node *down;  // 아래쪽 노드를 가리키는 포인터
    struct matrix_node *right; // 오른쪽 노드를 가리키는 포인터
    tagfield tag;              // 노드의 유형 (head 또는 entry)
    union {
        struct entry_node entry; // 데이터를 저장하는 노드
        struct matrix_node *next; // 다음 헤드 노드를 가리키는 포인터
    } u;
};

matrix 형태의 데이터를 2차원으로 해석하는 것입니다.

위의 코드에서 확인할 수 있듯이, 노드는 head와 entry로 구분됩니다. head에는 null값이 들어가고 다음에 들어갈 entry를 가리킵니다. 그리고 union을 통해 데이터를 저장, 다음 헤드 노드로를 처리시킵니다.

행에서의 head 노드는 right 노드로 연결됩니다. 열에서의 head 노드는 down 노드로 연결됩니다. 비제로 요소가 있으면 노드에 연결합니다.

typedef struct matrix_node *matrix_pointer;

matrix_pointer hdnode[MAX_SIZE];

// 새로운 노드를 동적으로 생성하는 함수
matrix_pointer new_node() {
    matrix_pointer temp = (matrix_pointer)malloc(sizeof(struct matrix_node));
    if (!temp) {
        printf("Memory allocation error\n");
        exit(1);
    }
    return temp;
}

// 매트릭스를 읽어들이는 함수
matrix_pointer mread() {
    int num_rows, num_cols, num_nonzeros, num_heads;
    int row, col, value, current_row;
    matrix_pointer temp, last, node;

    // 행, 열, 0이 아닌 값의 개수를 입력받음
    printf("Enter the number of rows, columns, and nonzeros: ");
    scanf("%d %d %d", &num_rows, &num_cols, &num_nonzeros);

    num_heads = (num_rows > num_cols) ? num_rows : num_cols;

    // 헤드 노드를 생성
    node = new_node();
    node->tag = entry;
    node->u.entry.row = row;
    node->u.entry.col = col;

    if (!num_heads) {
        node->right = node;
    } else {
        // 헤드 노드들을 초기화
        for (int i = 0; i < num_heads; i++) {
            temp = new_node();
            hdnode[i] = temp;
            hdnode[i]->tag = head;
            hdnode[i]->right = temp;
            hdnode[i]->u.next = temp;
        }
    }

    current_row = 0;
    last = hdnode[0];

    // 각 비제로 요소를 읽어들이고 노드로 변환하여 연결
    for (int i = 0; i < num_nonzeros; i++) {
        printf("Enter the row, column, and value: ");
        scanf("%d %d %d", &row, &col, &value);

        if (row > current_row) {
            last->right = hdnode[current_row];
            current_row = row;
            last = hdnode[row];
        }

        temp = new_node();
        temp->tag = entry;
        temp->u.entry.row = row;
        temp->u.entry.col = col;
        temp->u.entry.value = value;

        last->right = temp;
        last = temp;
        hdnode[col]->u.next->down = temp;
        hdnode[col]->u.next = temp;
    }

    last->right = hdnode[current_row];

    // 각 헤드 노드들을 연결
    for (int i = 0; i < num_heads - 1; i++) {
        hdnode[i]->u.next->down = hdnode[i + 1];
    }

    hdnode[num_heads - 1]->u.next->down = hdnode[0];

    return node;
}

// 매트릭스를 출력하는 함수
void mwrite(matrix_pointer node, int num_rows, int num_cols) {
    matrix_pointer temp, head = node->right;

    printf("Sparse Matrix:\n");
    for (int i = 0; i < num_rows; i++) {
        temp = head->right;
        for (int j = 0; j < num_cols; j++) {
            if (temp != head && temp->u.entry.col == j) {
                printf("%d ", temp->u.entry.value);
                temp = temp->right;
            } else {
                printf("0 ");
            }
        }
        head = head->u.next;
        printf("\n");
    }
}

int main() {
    int num_rows, num_cols, num_nonzeros;

    // 매트릭스 읽기
    matrix_pointer matrix = mread();


    // 매트릭스 출력
    mwrite(matrix, num_rows, num_cols);

    return 0;
}

뒤의 코드를 전부 해체분석 해보겠습니다. 먼저 행의 head = 열의 head는 동일하게 취급합니다. 어차피 사용법은 똑같기 때문이죠. 그러나 어떤 한 쪽이 더 길 수도 있으므로 그 긴 쪽으로 맞춰줍니다.

그리고 행렬의 길의를 받아오고 희소행렬을 받아옵니다.

먼저 비제로 요소들을 초기화 시킨뒤, 비제로 요소들을 right, down으로 서로 link시킵니다. 또한 head node를 서로 원형 리스트로 연결시켜 순환, 탐색할 수 있습니다

프로그램은 방식에 따라 실행 시간을 줄일 수도 있다. 그리고 big-o표기법에 대해서 잘 관찰하면 보통 반복과 같은 형태에서 나타난다. 한 줄의 실행에 n으로 표기하고, O(n)으로 표기한다. 그리고 n은 큰수라고 가정하기 때문에 O(an+b)와 O(n)은 같은 것으로 간주한다. 주요한 것은 실행시간이 선형적이라는것뿐이다. 보통 O(logn) < O(n) < O(n^2) < O(2^n) 으로 표기하곤 한다. 입력크기 n이 커질때 알고리즘의 실행 시간이 어떻게 변하는지를 나타내므로 최악의 경우를 나타냅니다. 그러므로 n이 충분이 클때로 생각합니다.

희소 행렬과 그 표기

희소행렬이란 행렬의 원소값들 중 0이 많은 행렬을 희소행렬이라 합니다. 대부분의 요소가 0이므로, 메모리 절약에 도움이 됩니다. 따라서 일반 행렬과는 표기도 다르게 함이 옳습니다. 그러므로 <행,열,원솟값> 으로 표기한다. 코드로 표기하면 다음과 같다.

typedef struct {
  int row;
  int col;
  int value;
} term;

다음처럼 표기하여 value의 기본값을 0으로 저장한 뒤에 value의 값이 0이 아니면 (0,0,15)라면 1행1열의 원솟값은 15라는 것이다

희소행렬의 전치의 일반적 표기법과 시간 복잡도

희소행렬에서 시간 복잡도를 감안하지 않고 행렬을 전치시켜보자.

term a[MAX_COL];
term b[MAX_COL];
void transpose(term a[], term b[]){
  int n, i, j, currentb;
  n = a[0].value;
  b[0].row = a[0].col;
  b[0].col = a[0].row;
  b[0].value = n; // b값 처리
  if(n > 0){
    currentb = 1;
    for(i=0;i<a[0].col;i++){
      for(j=1;j<n;j++){
        if(a[j].col == i){
          b[currentb].row = a[j].col;
          b[currentb].col = a[j].row;
          b[currentb].value = a[j].value;
          currentb++;
        }
      }
    }
  }
}

코드를 이해하고, 코드의 시간 복잡도를 분석해보겠습니다. a에서 b로 전치시키는 것이 목적입니다. 값은 a[0].value = 총 0이 아닌 원소값의 합. b[i].col에는 a[i].row대입하고 row에는 col을 대입합니다. 그리고 a의 열갯수 * 배열의 총 원소 수 를 곱한 번 만큼 반복하여 a[j].col이 i와 같을 때, i와 값을 전치하여 terms b[]에 저장합니다. 이때는 column 수가 많을수록 시간복잡도가 커집니다. 시간복잡도는 다음과 같이 계산합니다. value = 총 원소수 총 원소수 = row * col 이므로 반복량은 row * row * col 이다.

조금 반복량이 많은 거 같다. 더 줄일 반복은 없을까? 한번 코드를 줄여보자.

희소행렬의 전치를 빠르게 실행시키는 방법과 그 시간 복잡도

term a[MAX_COL]; // 입력 행렬
term b[MAX_COL]; // 전치 행렬
void fast_transpose(term a[], term b[]){
  int row_terms[MAX_COL], starting_pos[MAX_COL]; 
  int i,j,num_cols,num_terms=a[0].value; // row_terms는 각 행렬의 원소 개수를 저장, starting_pos는 각 열의 시작 위치, num_cols는 열의 개수, num_terms는 행렬의 항의 수
  b[0].row = num_cols; b[0].col = a[0].row; // 전치행렬 선언
  b[0].value = num_terms;
  if(num_terms > 0 ) { // 항목이 하나 이상있을 경우에만 수행
    for(i=0; i<num_cols; i++){ // row_terms를 초기화
      row_terms[i] = 0;
    }
    for(i=1; i<=num_terms; i++){ // 값을 대입함
      row_terms[a[i].col]++; // row_terms에 각 행렬의 원소 개수를 저장
    }
    starting_pos[0] = 1; // starting_pos를 초기화 , 첫 항목을 1로 설정 왜냐? 
    for(i=1; i<num_cols; i++){ // starting_pos를 계산 값은 이전 열의 시작 위치와 항의 수를 더한 값
      starting_pos[i] = starting_pos[i-1] + row_terms[i-1];}
    for(i=1; i<=num_terms; i++){ // a를 탐색하여 전치된 위치에 b배열에 저장 적절한 위치를 결정하고 해당 위치에 값을 저장하고 시작 위치를 증가시킴
      j = starting_pos[a[i].col]++;// starting_pos를 사용하여 시작 위치를 증가시킴
      b[j].row = a[i].col;
      b[j].col = a[i].row;
      b[j].value = a[i].value;
    }
  }
}

시간 복잡도를 줄여보았습니다. 코드를 해석해보겠습니다. 아까완 다르게 값을 n을 통해 선언하지 않고 starting_pos, num_terms 를 통해서 starting_pos에는 각 열에 시작 위치를 저장하고, num_terms 에 각 열에 몇개의 0이 아닌 원소가 들어가는지 저장합니다. terms a[]에 저장된 값을 전치하려면 행과 열을 행과 열을 서로 바꿔야 합니다. 시작 위치는 1입니다. 만약 4 x 3의 행렬 이라 가정합니다. 0 0 3 0 2 5 0 0
0 0 0 15
이라면 표기를 (0,2,3), (1,0,2),(1,1,5),(2,3,15) 로 표기합니다 그러면 row_terms의 초깃값이 {1,1,1,1} 이고 startring_pos의 초깃값을 1로 설정하고 합연산을 시키므로 {1,2,3,4}가 된다. num_term으로 반복하고 starting_pos(a[i].col)값을 하나씩 증가시켜 대입합니다. (0,2,3), (1,0,2),(1,1,5),(2,3,15) 이 경우에는 (0,2,3)을 먼저 실행하므로 (a,b,c,d)가 있을때 (a,b,c+1,d)가 되고 (a+1,b,c+1,d) .. (a+1,b+1,c+1,d+1)이 된다.

그럼 시간 복잡도를 분석해보겠습니다. for문이 4개 있고 각각 col반복이 두개, elements반복이 두개이므로 O(2(columns+elements))이다 elements = row x columns이다 어차피 계수는 무시하므로 O(columns+ row* columns)이다 O(columns * row)이므로 위의 값보다 시간 복잡도가 더 빠릅니다.

#include <stdio.h>
#include <stdlib.h>
#define MAX_DEGREE 100
typedef struct{
  int degree;
  int coef[MAX_DEGREE];
}polynomial;
polynomial add(polynomial, polynomial);
void polynomial_print(polynomial);
int main(void) {
  int i;
  polynomial p1,p2,p3;
  p1.degree=-1; 
  p2.degree=-1;
  p3.degree=-1;  // 코드에서 다항식의 최고차항을 -1로만들어 초기화합니다
  for(i=0;i<MAX_DEGREE;i++){
    p1.coef[i]=0; 
    p2.coef[i]=0; // 계수를 0으로 초기화시킴
  }
  p1.degree=2, p1.coef[2]=3,p1.coef[1]=2,p1.coef[0]=1; // p1 = 3x^2 + 2x + 1
  p2.degree=4, p2.coef[4]=1,p2.coef[2]=2,p2.coef[0]=3; // p2 = x^4 + 2x^2 + 3
  polynomial_print(p1);
  polynomial_print(p2);
  p3=add(p1,p2);
  polynomial_print(p3);
  return 0;
}
polynomial add(polynomial p1, polynomial p2){
  polynomial p3;
  int i, j;
  p3.degree=-1;
  if(p1.degree > p2.degree){ // p3의 최고차항값 알아내기
    p3.degree = p1.degree;
  }
  else
    p3.degree = p2.degree;
  for(i=0;i<=p3.degree;i++){ // 상수항부터 최고차항까지 반복
    p3.coef[i] = p1.coef[i] + p2.coef[i]; // 같은 항은 합합
  }
  return p3;
}
void polynomial_print(polynomial p){
  int i;
  for(i=p.degree;i>=0;i--){// 최고차항부터 상수항까지 순서로 출력
    if(i!=0){
      printf("%dx^%d + ",p.coef[i],i); 
    }
    else
      printf("%d",p.coef[i]);
  }
  printf("\n");
}

해당 프로그램은 두 다항식을 더하는 과정입니다. 결과는 3x^2 + 2x + 1 x^4 + 2x^2 + 3 x^4 + 0x^3 + 5x^2 + 2x + 4 로 출력됩니다. 왜냐하면 계수값이 0이라도 degree보다 작다면 저장되기 때문입니다. dense expression 같은 경우는 2x^1000 + 1과 같은 다항식을 표기할 때는 메모리 누수가 심합니다. 그럴 때는 Sparse Expression을 사용합니다. Sparse Expression은 두개의 값을 지니는 형태로 저장됩니다. 그리고 그 항이 하나하나 증가될때마다 avail을 증가시키는 방식을 사용합니다.

#include <stdio.h>
#include <stdlib.h>
#define MAX 100
#define COMPARE(x,y) (((x)<(y))?-1:((x)>(y)?1:0))   
typedef struct {
  int coef;
  int expon;
} polynomial;
polynomial terms[MAX]; // 총 항의 계수 = MAX
int avail =0; // 초기의 항의 갯수 0개
void attach(int coefficient, int exponent){ // 해당문은 계수, 지수를 저장하는 함수
  if(avail >= MAX){
    fprintf(stderr, "Too many terms in the polynomial\n");
    exit(1); // 총 항의 계수가 넘어설 경우 예외처리
  }
  terms[avail].coef = coefficient;
  terms[avail].expon = exponent;
  avail++;
}
void polynomial_add(int starta, int finisha, int startb, int finishb, int *startd, int *finishd){ // 두개의 다항식을 더하는 함수
  float coefficient; // 두개의 다항식의 계수를 저장하는 변수
  *startd = avail; // 다항식의 시작 위치를 저장하는 변수
  while(starta <= finisha && startb <= finishb){ // 두개의 다항식의 시작 위치가 끝 위치를 넘어설 때까지
  switch(COMPARE(terms[starta].expon,terms[startb].expon)){ // starta와 startb의 지수를 비교합니다
  case -1: // 아닐때
    attach(terms[startb].coef,terms[startb].expon); // startb의 지수가 더 클 경우 startb의 지수를 저장합니다
    startb++; // startb의 지수의 위치를 1증가시켜 뒤에 위치시킵니다
    break;
  case 0: // 같을 때
    coefficient = terms[starta].coef + terms[startb].coef; // 더함
    if(coefficient != 0){ 
      attach(coefficient, terms[starta].expon);
    }
    starta++;
    startb++;
    break;
  case 1: // case -1 과 같음
    attach(terms[starta].coef,terms[starta].expon);
    starta++;
    break;
  }

}
  for(;  starta <= finisha; starta++){ // starta가 finisha를 넘어설 때까지
    attach(terms[starta].coef, terms[starta].expon); 
  }
  for(; startb <= finishb; startb++){ // startb가 finishb를 넘어설 때까지
    attach(terms[startb].coef, terms[startb].expon);
  }
  *finishd = avail -1; // 다항식의 끝 위치를 저장하는 변수
}
void polynomial_print(int start, int finish){ // 다항식을 출력하는 함수
  int i;
  for(i = start; i<=finish; i++){ // 시작점부터 끝점까지 출력
    if(i != finish){
      printf("%dx^%d + ", terms[i].coef, terms[i].expon); 
    }
    else {
        printf("%dx^%d", terms[i].coef, terms[i].expon); 
    }
  }
  printf("\n");
}
int main(void) {
  int starta, finisha, startb, finishb, startd, finishd;
  starta = avail; // 다항식의 시작 위치를 저장하는 변수
  terms[avail].expon = 100;
  terms[avail].coef = 2; // 계수와 지수 입력
  avail++; // 다음 위치로
  terms[avail].expon = 0;
  terms[avail].coef = 3;
  finisha = avail;
  avail++;

  startb = avail; // 다항식의 시작 위치를 저장하는 변수
  terms[avail].expon = 3;
  terms[avail].coef = 1;
  avail++;
  terms[avail].expon = 4;
  terms[avail].coef = 2;
  avail++;
  terms[avail].expon = 0;
  terms[avail].coef = 3;
  finishb = avail;
  avail++; // 
  polynomial_print(starta, finisha);
  polynomial_print(startb, finishb);
  polynomial_add(starta, finisha, startb, finishb, &startd, &finishd);
  polynomial_print(startd, finishd);
  return 0;
}

해당 프로그램은 Sparse 표현으로 두 다항식의 값을 출력하는 프로그램입니다.

typedef struct {
  int coef;
  int expon;
} polynomial;
polynomial terms[MAX]; // 총 항의 계수 = MAX
int avail =0; // 초기의 항의 갯수 0개

다음과 같이 기초적으로 선언을 합니다. terms에는 각각 하나하나의 항이 저장이 됩니다. 항에는 계수와 지수가 저장이 됩니다.

 starta = avail; // 다항식의 시작 위치를 저장하는 변수
  terms[avail].expon = 100;
  terms[avail].coef = 2; // 계수와 지수 입력
  avail++; // 다음 위치로
  terms[avail].expon = 0;
  terms[avail].coef = 3;
  finisha = avail;
  avail++;

  startb = avail; // 다항식의 시작 위치를 저장하는 변수
  terms[avail].expon = 3;
  terms[avail].coef = 1;
  avail++;
  terms[avail].expon = 4;
  terms[avail].coef = 2;
  avail++;
  terms[avail].expon = 0;
  terms[avail].coef = 3;
  finishb = avail;
  avail++; // 

해당 형식처럼 구조체 내부에 지수와 계수를 대입하여 선언합니다. 변수값은 (expon, coef)두개씩 필요합니다. 그러므로 해당 표현은 고차다항식과 많은 값이 0인 경우에 유리합니다