[자료구조] 2020.08.05

1. 이진트리 구현 예제

 : 저번 시간에 배우지 못한 void del() 함수 마저 구현했으나 작동은 되지 않는다.

  Why? 현재 트리는 루트노드가 메인에서 NULL로 설정되어있기 때문에
          (즉, 현재 트리는 루트가 포인터로 (malloc()없이) 정의되어있어서 삭제가 되지 않는다)

   만약, 현재 상태에서 삭제를 진행하고 싶다면 리스트처럼 루트를 만들어 주어야 한다.

   예)
       (빈 루트노드)
              |
             10
          20   30

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

// 노드 생성을 위한 구조체 선언
typedef struct NODE {
	int data;
	struct NODE* left;
	struct NODE* right;
}N;

// 노드 생성
N* create(N* node, int data) {
	if (node == NULL) {
		node = (N*)malloc(sizeof(N));
		node->data = data;
		node->left = NULL;
		node->right = NULL;
	}
	else {
		if (node->data > data) {
			node->left = create(node->left, data);
		}
		else {
			node->right = create(node->right, data);
		}
	}
	return node;
}

// 전위순회
void preorder(N* node) {
	if (node != NULL) {
		printf("%d ", node->data);
		preorder(node->left);
		preorder(node->right);
	}
}
// 중위순회
void inorder(N* node) {
	if (node != NULL) {
		inorder(node->left);
		printf("%d ", node->data);
		inorder(node->right);
	}
}
// 후위순회
void postorder(N* node) {
	if (node != NULL) {
		postorder(node->left);
		postorder(node->right);
		printf("%d ", node->data);
	}
}

// 노드 삭제
void del(N* node, int data) {
	N* c = node;
	N* p = NULL;		// 비주얼 스튜디오에서는 초기화하지 않은 포인터의 사용을 지양함
	while (c != NULL && c->data != data) {
		p = c;
		c = data < c->data ? c->left : c->right;
	}
	if (c == NULL) {
		printf("삭제할노드가없음!\n");
		return;
	}
	if (c->left == NULL && c->right == NULL) {
		// 삭제할 노드가 리프노드일때
		if (p->left == c) {
			p->left = NULL;
		}
		else {
			p->right = NULL;
		}
	}
	else if (c->left == NULL || c->right == NULL) {
		// 삭제할 노드가 하나의 자식노드를 갖는 경우
		if (p->left == c) {
			c = c->left != NULL ? c->left : c->right;
			p->left = c;
		}
		else {
			c = c->left != NULL ? c->left : c->right;
			p->right = c;
		}
	}
	else {
		// 삭제할 노드가 두 개의 자식노드를 갖는 경우->오른쪽 자식들 중에서 가장 작은노드를 찾기!
		N* subp = c;
		N* subc = c->right;
		while (subc->left != NULL) {
			subp = subc;
			subc = subc->left;
		}
		if (c == subp) {
			c->right = subc->right;
		}
		else {
			subp->left = subc->right;
		}
		c->data = subc->data;
	}
}

int main() {
	N* root = NULL;

	int act;
	while (1) {
		printf("1.노드생성 2.전위순회 3.중위순회 4.후위순회 5.노드삭제 6.종료\n");
		scanf("%d", &act);
		if (act == 1) {
			int data;
			printf("데이터입력: ");
			scanf("%d", &data);
			root = create(root, data);
		}
		else if (act == 2) {
			preorder(root); // 전위순회
			printf("\n");
		}
		else if (act == 3) {
			inorder(root); // 중위순회
			printf("\n");
		}
		else if (act == 4) {
			postorder(root); // 후위순회
			printf("\n");
		}
		else if (act == 5) {
			int data;
			printf("삭제할데이터입력: ");
			scanf("%d", &data);
			del(root, data);
		}
		else {
			printf("프로그램종료\n");
			break;
		}
	}

	return 0;
}

 

 

2. 문제를 잘 푸는 방법

   ① 독해 => input / output
   ② 문제의 입출력에 맞춰서 코딩
   ③ 알고리즘 -> 일반적인 경우 => 예외
   ④ 배열 구조체 리스트 스택 큐

 

 

3. [문제] 성애는 이번 학기에 전공을 정말 많이 듣는다. 이로 인해 거의 매일을 과제를 하면서 보내고 있다.

            그런데도 과제가 줄어들 기미가 보이지 않는데, 바로 분단위로 과제가 추가되고 있기 때문이다.

            다행히 과제 제출 기한은 학기가 끝날 때까지이다.

            너무나도 많은 과제를 하다가 미쳐버린 성애는 아래와 같은 규칙으로 과제를 해 나가고 있다.
            
            과제는 가장 최근에 나온 순서대로 한다. 또한 과제를 받으면 바로 시작한다.
            과제를 하던 도중 새로운 과제가 나온다면, 하던 과제를 중단하고 새로운 과제를 진행한다.
            새로운 과제가 끝났다면, 이전에 하던 과제를 이전에 하던 부분부터 이어서 한다.

            (성애는 기억력이 좋기 때문에 아무리 긴 시간이 지나도 본인이 하던 부분을 기억할 수 있다)
            성애는 과제를 받자마자 이 과제가 몇 분이 걸릴지 정확하게 알 수 있고,

            성애가 제출한 과제는 무조건 만점을 받는다.
            
            성애는 이번 학기에 자기가 받을 과제 점수를 예상해보고 싶다.

            하지만 과제 점수를 예상하는 지금도 과제가 추가되고 있기에 여유를 부릴 수가 없다.

            여러분이 성애가 받을 과제 점수를 구해주자!
            
            입력)
            첫째 줄에 이번 학기가 몇 분인지를 나타내는 정수 N이 주어진다. (1 ≤ N ≤ 1,000)
            두번째 줄부터 N줄 동안은 학기가 시작하고

            N분째에 주어진 과제의 정보가 아래의 두 경우 중 하나로 주어진다.

            1 A T : 과제의 만점은 A점이고, 성애가 이 과제를 해결하는데 T분이 걸린다.

                      A와 T는 모두 정수이다. (1 ≤ A ≤ 100, 1 ≤ T ≤ 1,000)
            0 : 해당 시점에는 과제가 주어지지 않았다.

            

            출력)
            성애가 받을 과제 점수를 출력한다.

 

            입력 예)

            3
            1 100 3
            0
            0

            출력 예)
            100

 

            입력 예)
            5
            1 10 3
            0
            1 100 2
            1 20 1
            0

            출력 예)
            120

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

int main() {
	int N;
	scanf("%d", &N);

	int res = 0;
	int act;
	int* A = (int*)malloc(N * sizeof(int));
	int* T = (int*)malloc(N * sizeof(int));
	int index = 0;
	for (int i = 0; i < N; i++) {
		scanf("%d", &act);
		if (act) {
			// push
			scanf("%d%d", &A[index], &T[index]);
			T[index]--;
			index++;
		}
		else {
			T[index - 1]--;
		}
		if (T[index - 1] == 0) {
			// pop
			res += A[index - 1];
			index--;
		}
	}
	printf("최종점수: %d\n", res);

	return 0;
}