[단과_자료구조] 2020.07.13

1. 자료구조 & 알고리즘에서 앞으로 배울 내용
 : 배열, 구조체, 리스트, 스택, 큐, 트리
   교환, 최대값, 정렬, 탐색, 순회

 

 

2. cmd 창이 안나올때?

 : 프로젝트 > 속성 > 링커 > 시스템 > 하위 시스템 콘솔로 변경

 

 

3. Visual Studio에서 scanf() 함수 사용하기

 

 

4. 포인터, call by value, call by reference, 동적할당

#include<stdio.h>
#include<stdlib.h>		// malloc 함수를 사용하기 위해 필요한 헤더파일

// 1. call by value 값에 의한 호출
void swap(int a, int b) {
	int tmp = a;		// 임시 저장 변수
				// a의 값을 기억할 임시 저장 변수가 필요함
	a = b;
	b = tmp;
}

// 포인터? 주소를 받는다
// 2. call by reference
void swap2(int* a, int* b) {
	// 주소를 받았다 = 포인터
	// 1. 함수의 인자로 주소를 보낼때
	// 2. 외부함수(사용자정의함수)에서 main()에 영향을 주고 싶을때
	// 3. 함수의 리턴값으로 2개 이상을 보내고 싶을때

	// [교환] 알고리즘
	int temp = *a;	// 임시 저장 변수
			// a의 값을 기억할 임시 저장 변수가 필요함
	*a = *b;
	*b = temp;
}
void show(int* arr, int n) {
	printf("show() 함수 실행 : ");
	for (int i = 0; i < n; i++) {
		printf("%d ", arr[i]);
	}
}


int main() {

	int a = 10;
	int b = 20;

	printf("원래 들어 있는 값 : %d %d\n", a, b);
	swap(a, b);	// 값이 변함이 없다
	printf("swap() 후 %d %d\n", a, b);

	// 우리는 main에 있는 a, b의 값을
	// 바꾸기 위해서는 주소 값을 줘서
	// 그 주소가 참조하고 있는 값을 변경해야 한다
	swap2(&a, &b);
	printf("swap2() 후 %d %d\n", a, b);

	// 가변적인 타입(자료형) -> 포인터
	// 4. 동적할당(동적메모리)을 할때 사용
	// 5. 함수의 인자로 배열을 보낼때 사용
	int n;
	scanf("%d", &n);
	int* arr = ((int*)malloc(n * sizeof(int)));
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}

	show(arr, n);	// arr == &arr[0]

	printf("\n\n");
	char str[10];
	scanf("%s", str);	// 배열의 이름은 배열의 &arr[0](즉, 첫 번째 방)주소다

	return 0;
}

 

 

5. 문제푸는 방법
1) 독해

2) 컴퓨터 없이 문제 풀이

3) 코드로 작성

 

 

6. [첫번째 문제] 미어켓 문제
 : 큰 수를 만나기 전까지 카운팅, 카운팅한 값을 누적
   예) [ _ _ _ _ _ ] >[ 3 1 5 2 6 ] > [ 2 1 2 1 0] > 출력값 6 

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

int main() {

	int n;
	scanf("%d", &n);
	int* arr = (int*)malloc(n * sizeof(int));
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}

	int cnt;
	int sum = 0;
	for (int i = 0; i < n; i++) {
		cnt = 0;
		for (int j = i + 1; j < n; j++) {
			cnt++;
			if (arr[i] < arr[j]) { break; }
		}
		sum += cnt;
		printf("%d %d\n", cnt, sum);
	}
	printf("%d", sum);

	return 0;
}

 

 

7. 동적할당 2차원 배열

#include<stdio.h>
#include<stdlib.h>
int main() {

	// 다차원배열==이차원배열 -> 동적할당
	int a, b;
	scanf("%d%d", &a, &b);
	int **arr = (int **)malloc(a * sizeof(int *));
	for (int i = 0; i < a; i++) {
		arr[i] = (int *)malloc(b * sizeof(int));
	}
	// 이차원배열 생성완료
	for (int i = 0; i < a; i++) {
		for (int j = 0; j < b; j++) {
			scanf("%d", &arr[i][j]);
		}
	}
	for (int i = 0; i < a; i++) {
		for (int j = 0; j < b; j++) {
			printf("%d ", arr[i][j]);
		}
		printf("\n");
	}

	return 0;
}

 

 

8. 오름차순으로 배열된 숫자들이 입력될 때, 숫자들 간 거기들 중, 가장 짧은 거리를 출력 
   (단, 오름차순으로 배열된 숫자들이 입력되지 않을 경우,

   숫자가 2개 이상이 아닐경우,

   배열되는 숫자가 음수일 경우에 ERROR를 출력)

** 내코드

[문제점] 니즈 파악 오류, 오름차순으로 배열된 숫자들이 입력되지 않을 경우 ERROR 출력이 구현되지 않음

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

int main() {
	// 1. 몇개의 배열의 방을 만들지 사용자에게 입력 받기
	int n;
	scanf("%d", &n);

	// 7. 예외 조건
	// 숫자가 2 이상 아니거나 음수일때 ERROR 출력
	if (n >= 2) {
		// 2. 배열 만들고 어떤 값으로 채워 넣을지 사용자에게 입력 받기
		int* arr = (int*)malloc(n * sizeof(int));
		for (int i = 0; i < n; i++) {
			scanf("%d", arr + i);
		}
		// 3. 거리 구하는 값 저장할 배열 만들기
		// 입력받은것보다 하나 적게 왜냐? 거리 구하면 하나 입력 받은것보다 하나 부족함
		int* arDistance = (int*)malloc((n - 1) * sizeof(int));

		// 4. 거리 구해서 배열에 넣기
		for (int i = 0; i < n - 1; i++) {
			for (int j = 1; j < n; j++) {
				if (arr[j] < arr[i]) {
					arDistance[i] = arr[i] - arr[j];
				}
				else {
					arDistance[i] = arr[j] - arr[i];
				}
			}
			//printf("%d", arDistance[i]);
		}

		// 5. 짧은 거리 구하기
		// 0번 값을 저장하고 저장한 값들을 1번값부터 순차 비교
		// 작은 값 나오면 값 변경
		int min = arDistance[0];
		for (int i = 0; i < n - 1; i++) {
			if (min > arDistance[i]) {
				min = arDistance[i];
			}
		}

		// 6. 결과값 출력하기
		printf("%d\n", min);
	}
	else {
		printf("ERROR\n");
	}

	return 0;
}

 

** 강사님 코드

#include<stdio.h>
#include<stdlib.h>
int main() {

	int n;
	scanf("%d", &n);
	int *arr = (int *)malloc(n * sizeof(int));
	int sw = 0;
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
		if (arr[i] < 0) {
			sw = 1;
		}
		if (i != 0 && arr[i] < arr[i - 1]) {
			// 인덱스 구간이 유효한지 확인!!!
			sw = 1;
		}
	}
	if (n < 2) {
		sw = 1;
	}
	if (sw) { // sw==1
		printf("ERROR!\n");
		return 0;
	}
	int min = arr[1] - arr[0]; // [최대값]알고리즘
	for (int i = 0; i < n - 1; i++) {
		if (min > arr[i + 1] - arr[i]) {
			min = arr[i + 1] - arr[i];
		}
	}
	printf("%d", min);

	return 0;
}

 

 

9. 버블정렬

#include<stdio.h>
#include<stdlib.h>
int main() {
	// [대용량데이터]를 효과적으로 [탐색]하기 위해서,
	// [정렬]해 보관해야한다!

	int n;
	scanf("%d", &n);
	int *arr = (int *)malloc(n * sizeof(int));
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}
	for (int i = 0; i < n; i++) {
		printf("%d ", arr[i]);
	}
	printf("\n");
	// 버블정렬
	for (int a = 0; a < n; a++) {
		for (int x = 0; x < n - 1; x++) {
			// [비교]는 [데이터개수-1]번 수행됨!!!
			if (arr[x] > arr[x + 1]) {
				int tmp = arr[x];
				arr[x] = arr[x + 1];
				arr[x + 1] = tmp;
			}
		}
		for (int i = 0; i < n; i++) {
			printf("%d ", arr[i]);
		}
		printf("\n");
	}
	for (int i = 0; i < n; i++) {
		printf("%d ", arr[i]);
	}
	printf("\n");

	return 0;

}

 

 

10. 학생들 점수 평균 구하기

** 내코드

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

int main() {

	// 1. 이차원 배열 생성하기
	int a, b;
	scanf("%d %d", &a, &b);

	// 1)학생들 점수
	int** arr = (int**)malloc(a * sizeof(int*));
	for (int i = 0; i < a; i++) {
		arr[i] = (int*)malloc(b * sizeof(int));
	}

	// 2)합계, 평균
	int* sum = (int*)malloc(a * sizeof(int*));
	double* avg = (double*)malloc(a * sizeof(double*));

	// 2. 점수 입력 받기
	for (int i = 0; i < a; i++) {
		for (int j = 0; j < b; j++) {
			scanf("%d", &arr[i][j]);
		}
	}

	// 3. 각 학생별 합계 구하기
	for (int i = 0; i < a; i++) {
		sum[i] = 0;
		for (int j = 0; j < b; j++) {
			sum[i] += arr[i][j];
		}
		printf("sum[%d] = %d\n", i, sum[i]);
	}

	// 4. 각 학생별 평균 구하기
	for (int i = 0; i < a; i++) {
		avg[i] = sum[i] / (double)b;
	}

	// 5. 각 학생별 평균 출력하기
	for (int i = 0; i < a; i++) {
		printf("%.2f\t", avg[i]);
	}

	return 0;
}

 

** 강사님 코드

#include<stdio.h>
#include<stdlib.h>
int main() {

	// 다차원배열==이차원배열 -> 동적할당
	int a, b;
	scanf("%d%d", &a, &b);
	int **arr = (int **)malloc(a * sizeof(int *));
	for (int i = 0; i < a; i++) {
		arr[i] = (int *)malloc(b * sizeof(int));
	}
	// 이차원배열 생성완료
	for (int i = 0; i < a; i++) {
		for (int j = 0; j < b; j++) {
			scanf("%d", &arr[i][j]);
		}
	}
	for (int i = 0; i < a; i++) {
		printf("%d번 학생의 평균은 ", i + 1);
		int sum = 0;
		for (int j = 0; j < b; j++) {
			sum += arr[i][j];
		}
		printf("%.2lf점 입니다.\n", sum*1.0 / b);
	}

	return 0;
}