[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개만큼을 뽑은 후
모든 원소의 값을 출력하는 프로그램을 작성하는 방법을 배워봤다!
오늘의 공부 끝 :)