[C언어] 동적할당으로 조합 원소 출력하기

 정적할당과 동적할당

---

​(1) 정적할당

- 변수 선언을 통해 필요한 메모리를 할당

- 많은 양의 메모리는 주로 배열을 사용            ex) int arr[100]

​

그러나 필요한 양이 예측되지 않는 경우 프로그램 작성 시에 할당받을 수 없다.

이런 경우에 "동적할당"을 사용한다!

​

 

(2) 동적할당

- 프로그램 실행 중에 운영체제로부터 사용할 메모리 공간을 할당

- 힙(heap)으로부터 할당

- 사용자가 메모리 할당을 해제하기 전까지 계속 유지

​

※ 힙 : 운영체제가 소유/관리하는 메모리

​

​

 

 

 

 

동적할당 사용 방법

---

- malloc() / free() 라이브러리 함수 사용

- 라이브러리 함수 사용하기 위해 <stdlib.h> include 해야 함

 

​

(1) malloc() / free() 함수 사용 방법

- malloc() : 크기만큼 메모리 할당

- free() : 메모리 반환

- malloc 함수 데이터 타입 *포인터변수 = ( 데이터타입* )malloc( 메모리크기 ); ex) int *p = ( int* )malloc( sizeof(int) ); // int 타입 메모리 동적 할당 ex) int *pArr = ( int* )malloc( sizeof(int) * k); // 배열의 크기가 k인 int 타입 배열 동적 할당 ​ ​ - free 함수 free(포인터변수); ex) free(p); // 할당 받은 int 타입 메모리 반환

​

(2) malloc() 예제

Q. 사용자로부터 입력할 정수의 개수를 입력 받아 배열을 동적 할당 받고 정수를 입력받아 합을 출력

​

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

int main(void){
	int n, sum, i;
	int *p;
	scanf_s("%d", &n); //정수의 개수 입력

	if(n <= 0)
		return 0;
	
	p = (int*)malloc(sizeof(int) * n); // 크기가 n인 정수배열 동적할당으로 생성
	if(!p){
		printf("메모리를 할당할 수 없습니다.");
		return 0;
	}

	for(i = 0; i < n; i++)
		scanf_s("%d", &p[i]); // 키보드로부터 정수 입력

	sum = 0;
	for(i = 0; i < n; i++)
		sum += p[i];

	printf("평균 = %d\n", sum/n);
	free(p); // 배열 메모리 반환
}

 

 

결과 화면 (밑줄은 입력) 4 4 20 -5 9 평균 = 7

​

(3) free() 주의사항

- 적절치 못한 포인터로 free하면 실행 시간 오류 발생

ex) 동적으로 할당 받지 않는 메모리 반환 오류

ex) 동일한 메모리 두 번 반환 오류

 

int *p = (int*)malloc(sizeof(int)); free(p); // 정상적인 메모리 반환 free(p); // 실행 시간 오류. 이미 반환한 메모리를 중복 반환할 수 없음

​

​

​

 

동적할당으로 조합 원소 출력하기

---

​

Q. 배열의 동적할당을 이용하여 0부터 n까지의 원소 중 m개를 뽑아 모든 원소를 출력

​

- 동적할당과 조합 알고리즘을 적절히 사용하면 쉽게 풀 수 있는 문제 유형

- 동적할당 malloc 함수를 사용 / pick 함수 사용

→ 조합 알고리즘 작성

; }

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

/*
    n - 1 = 뽑을 수 있는 원소의 최대값
    bucket = 원소를 뽑은 후에 담을 곳(값 자체를 저장)
    bucketSize = m, k = 앞으로 뽑아야 할 원소의 개수 
*/
void pick(int n, int* bucket, int bucketSize, int k) {
	int i, lastIndex, smallest;
	lastIndex = bucketSize - k - 1; // 현재까지 값이 있는 배열의 인덱스

	if (k == 0) { // m개만큼 다 뽑았다면 모든 원소를 출력
		for (i = 0; i < bucketSize; i++)
			printf("%d ", bucket[i]);
		printf("\n");
		return;
	}

	if (bucketSize == k) // 아직 하나도 뽑지 않은 경우
		smallest = 0;
	else // 하나 이상의 값을 뽑은 경우
		smallest = bucket[lastIndex] + 1; 

	for (i = smallest; i < n; i++) {
		bucket[lastIndex + 1] = i; 
		pick(n, bucket, bucketSize, k - 1); 
	}
	return;
}
int main(void) {
	int n, m; 
	printf("Enter n and m : ");
	scanf_s("%d %d", &n, &m); // 0 ~ n까지의 원소 중에서 m개를 뽑기 위해 n, m을 입력 받는다.

	// m개 만큼의 원소를 뽑은 후에 bucket에 담기 크기가 m인 배열을 동적할당
	int* bucket = (int*)malloc(sizeof(int) * m);

	pick(n, bucket, m, m); //nCm 조합 알고리즘
	free(bucket);
	return;
}

 

​

결과 예시

 

 

n과 m의 값을 입력하면 0~(n-1)까지의 값에서 m개만큼을 뽑은 후

모든 원소의 값을 출력하는 프로그램을 작성하는 방법을 배워봤다!

​

​

오늘의 공부 끝 :)