파일 입출력 2

간단하게 파일에서 읽고 쓰는 것은 이제 알겠습니다.

하지만 단순히 파일을 처음부터 차례대로 읽는 것이 아니라, 어떤 위치 이후에서 읽고 쓰는 것도 가능할까요?

할 수 있습니다. 바로 fseek함수를 이용해서 말이죠.

fseek

int fseek(FILE *stream, long int offset, int origin);

fseek함수는 파일의 위치를 임의로 조작할 수 있습니다. 파일은 순차적으로 읽고 씁니다. 하지만 특정위치에 있는 데이터를 읽거나 쓸 필요가 있는 것이죠.

stream은 파일을 의미합니다.

offset은 origin에서 얼마만큼 이동할 것인지 나타냅니다.

origin은 기준 위치를 지정합니다.

우리가 fread를 여러번 호출해도 순차적으로 읽어올 수 있는 이유는 파일포인터때문입니다. 파일포인터는 현재 파일의 위치를 기억하고 있습니다. 그렇기 때문에 순차적으로 읽을 수 있는 거지요.

우리는 파일포인터의 위치를 임의로 지정하여 특정 위치의 데이터를 읽고 쓰는 것이 가능합니다. 파일포인터에 관해서는 세가지 매크로가 있는데요.

SEEK_SET : 파일의 처음

SEEK_CUR : 지금 현재 파일포인터 위치

SEEK_END : 파일의 끝

특정 위치에서 읽기

특정 위치에 값을 읽어오는 코드를 한 번 보겠습니다.

text.txt

파일의 처음위치부터 5를 건너뛰면 파일포인터는 F 앞을 가리키고 있습니다.

결과

반면에 파일 끝에서 4칸 앞은 offset이 음수가 됩니다. 처음 fseek을 주석처리하고 밑의 주석을 해제하고 실행해보세요. 결과는 이렇습니다.

특정 위치에 쓰기

반면 특정 위치에 쓰는 것도 가능합니다. 단! 파일을 열때 r+모드로 여세요. 

text.txt

파일 끝에서 5칸 앞에 _INSERT_라는 문자열을 추가하는 코드입니다. F 앞의 위치입니다. 

하지만 그 자리를 덮어쓰게 됩니다. 그래서 결과는 이렇습니다.

text.txt

ftell

파일 포인터의 위치를 알아옵니다. 

long int ftell(FILE *stream)

열었던 파일을 매개변수로 넣어주면 끝입니다.

성공시 0을 포함한 양수를 반환합니다.

text.txt

결과

ftell을 응용해서 파일의 크기도 알아올 수 있습니다.

파일 속성에서 알아본 크기는 10바이트입니다. 위의 코드의 결과는 어떨까요?

바이트 단위로 일치한다는 것을 알 수 있네요.

파일에 대해서는 다음에 또 이야기하도록 합시다.

배낭 알고리즘(Knapsack algorithm)

알고리즘에서 DP를 배울때 등장하는 유명한 문제가 있습니다. 제목과 같이 바로 배낭알고리즘이지요. 배낭알고리즘도 여러가지가 있지만, 우리는 조건이 가장 간단한 0/1 배낭 알고리즘 문제를 알아보도록 하겠습니다.

상황은 이렇습니다.

어떤 REAKWON이라는 이름의 도둑놈이 있습니다. 이 도둑은 새벽 늦은 시간 도둑질을 하기 위해서 남의 집에 들어가는데 까지는 성공했습니다. 그리고 훔쳐갈 물건들을 담기 위해 배낭도 챙겼지요. 데헷

하지만 이 도둑은 안타깝게도 아이큐가 70입니다. 배낭의 용량은 한정되어 있고 무거우면 들고갈 수도 없으므로 가장 값어치가 비싸고, 무게가 적은 물건들을 최대한 많이 담아가야합니다.

하지만 조건이 있습니다.

1) 물건을 부분적으로 담을 수는 없습니다.

2) 물건들은 모두 한개씩만 있습니다. 예를 들어 똑같은 반지가 2개일 수 없다는 이야기입니다.

도둑은 현재 15의 무게를 담을 수 있는 배낭을 가지고 있습니다. 그리고 아래와 같이 그 집의 물건이 있지요. 

이 상황에서 도둑이 훔쳐갈 수 있는 최대의 값을 구하는 것입니다.

어떻게 도둑을 도와줄것인가?

아 그냥 무게가 가장 적은거 순서대로 훔쳐가면 되지 않을까요?

라고 생각하신다면 다시 한번 생각해봅시다.

위의 물건들을 가장 작은 무게가 나가는 것을 훔쳐가게 된다면 items[4], items[2], items[3], items[0]만 가져갈 수 있고, 총 가치는 21이 되고 총 용량은 14가 됩니다.

하지만 items[0], items[1], items[4]를 선택한다면 총 가치는 23이 되고, 용량은 15로 더 비싼물건을 훔칠 수 있습니다.

그렇기 때문에 무게가 덜 나가는 순으로 정렬해서 문제를 해결할 수가 없는것이죠.

그래서 단순 무식하게 한번 접근해봅시다.

도둑은 그 물건을 훔쳐갈 수 있느냐, 훔쳐갈 수 없느냐 이 둘만 고려합니다. 

1) 훔쳐갈때 

만약 어떤 물건을 훔쳐갈 수 있다고 한다면 현재 무게가 그 물건의 무게만큼 무거워지요. 하지만 배낭 용량을 초과할 수는 없습니다. 그럴땐 그 물건을 배낭에 담을 수가 없습니다.

현재 그 물건들을 배열로 표현(items)하고, 어떤 물건을 고려 할때 그 아이템의 인덱스를 pos라고 합시다. 그리고 현재 용량을 capacity라고 해봅시다. V는 그 물건의 가치, W는 그 물건의 용량이라고 친다면 우리는 이런 식을 쓸 수 있습니다.

 knapsack(pos + 1, capacity - items[pos][W]) + items[pos][V]

knapsack이라는 함수는 현재 물건 이후 가장 큰 값을 반환합니다. 그러니까 당연히 용량(capacity)는 그 물건의 무게(items[pos][W])만큼 줄어들 것이고, 그 반환된 가장 큰 값에서 현재 물건의 가치를 더함으로써 지금 이 물건을 훔쳤을때 얻을 수 있는 값을 얻을 수 있습니다.

2) 훔쳐가지 않을 때

그리고 또 그냥 그 물건을 안가져갈 수도 있습니다. 그럴때는 현재 무게가 그대로 유지되면서 다음 물건을 고려하는 겁니다.

그러니 아래의 식이 가능합니다.

knapsack(pos + 1, capacity )

1)훔쳐갈 경우와 2)훔쳐가지 않을 경우 중에서 가장 큰 값이 우리가 원하는 답이 되는 것이죠.

코드

이런 프로그램을 구현한 것이 바로 아래 소스 코드입니다.

#include <stdio.h>
#define W 0
#define V 1
#define N 5
#define MAX(a,b) a>b ? a:b;

int items[N][2] = {
	,
	,
	,
	,
	
};

int knapsack(int pos,int capacity) {
	if (pos == N) return 0;
	
	int ret = 0;
	if (items[pos][W] <= capacity) //지금 pos의 물건을 훔칠 수 있을때
		ret = knapsack(pos + 1, capacity - items[pos][W])
		+ items[pos][V];
        //지금 pos의 물건을 훔치지 않을때와 ret 중에 큰 값
	ret = MAX(ret, knapsack(pos + 1, capacity)); 
	return ret;
}
int main() {
	int capacity = 15;
	printf("knapsack(%d,%d)=%d\n",0,capacity, knapsack(0, capacity));
	return 0;
}

답은 원하는 결과대로 나옵니다.

허나 이런 무식한 해결방법을 원한 것을 아닙니다.

만약 물건의 수가 많게 된다면 답을 구하기 전에 도둑은 감방으로 직행하게 될 것입니다. knapsack함수는 분명 같은 값을 여러번 중복해서 계산합니다. knapsack(pos,capacity)에서 같은 pos와 같은 capacity가 이전에 계산했었음에도 불구하고 또 다시 한번 더 계산한다는 것이죠.

그래서 DP가 사용됩니다. 단지 계산된 결과를 기억하고 있다가, 같은 계산을 수행할때 바로 값을 반환해주면 됩니다.

아래의 수정된 코드처럼 말입니다.

#include <stdio.h>
#include <stdlib.h>
#define W 0
#define V 1
#define N 5
#define MAX_CAPACITY 1000
#define MAX(a,b) a>b ? a:b;

int dp[N][MAX_CAPACITY];
int items[N][2] = {
	,
	,
	,
	,
	
};

int knapsack(int pos,int capacity) {
	if (pos == N) return 0;
	
	int ret = dp[pos][capacity];
	if (ret != -1) return ret;
	if (items[pos][W] <= capacity)
		ret = knapsack(pos + 1, capacity - items[pos][W])
		+ items[pos][V];
	ret = MAX(ret, knapsack(pos + 1, capacity));
	return dp[pos][capacity]=ret;
}
int main() {
	int capacity = 15;
	memset(dp, -1, sizeof(dp));

	printf("knapsack(%d,%d)=%d\n",0,capacity, knapsack(0, capacity));
	return 0;
}

우선 dp라는 2차원 배열을 -1로 셋팅합니다. 그리고 dp[pos][capacity]가 -1이 아니면 바로 그 값을 반환합니다. 배낭문제에서 음수는 나올 수 없습니다. 만약 계산되지 않은 값이라면 계산 후 dp[pos][capacity]에 값을 넣어주는 것입니다. 기억하고 있습니다.

결국 도둑은 가장 비싼 물건들을 훔쳐갈 수 있었지만, CCTV에 걸려 감방에 끌려가게 됩니다. 그걸 도와준 저도 같이 갑니다.

포인터배열

포인터라는 것은 조금 알겠는데 포인터배열은 무엇일까요... 포인터도 힘들게 배우는데 말이죠. 정말 산넘어 산입니다.

포인터배열이란 포인터를 원소로 갖는 배열을 의미합니다. 포인터 각각을 배열로 표현한 것이지요.

느낌이 오시나요?

코드와 그림으로 알아보도록 합시다.

#include <stdio.h>
int main() { 
        int a = 10; 
        int b = 20; 
        int c = 30; 
        int *pArr[3] = { &a,&b,&c };

        printf("%d\n", *pArr[0]);
        printf("%d\n", *pArr[1]);
        printf("%d\n", *pArr[2]);
}

여기, 포인터배열을 간단하게 알아볼 수 있는 코드입니다. pArr은 평소에 보던 배열과는 다르게 앞에 *(pointer)를 볼 수 있지요?

연산자 우선순위에 의하면 배열첨자([])가 포인터(*)연산보다 먼저입니다. 그렇기 때문에 배열 3개가 있고, 그 배열의 원소는 포인터라는 의미가 됩니다. 

따라서 배열의 원소인 pArr[0]은 a의 주소를 갖고있고, pArr[1]은 b의 주소를 갖고 있고, pArr[2]는 c의 주소를 갖고 있습니다.

이 코드의 상황을 그림으로 나타냈습니다.

만약 pArr[0]을 찍어보면 a의 주소가 나오게 됩니다. a의 값에 접근하고 싶다면 포인터 연산을 해주면 됩니다. 바로 *pArr[0], 이렇게요.

그렇게 포인터 원소를 배열로 나열했기 때문에 포인터배열이라 부릅니다.

포인터배열로 배열 가리키기

포인터가 배열의 시작주소를 가리킬 수 있다는 것은 이제 잘 알겁니다. 아닌가? 그렇다면 어떤 배열들을 포인터 배열로 가리킬 수도 있다는 느낌이 오시나요?

코드를 통해 느껴봅시다. 

#include <stdio.h>  
int main() { 
        int i, j; 
        int a[5] = { 1,2,3,4,5 };
        int b[6] = { 10,20,30,40,50,60 }; 
        int c[7] = { 100,200,300,400,500,600,700 };
        int *pArr[3] = { a,b,c }; 
        int sub_len[3] = 
        { sizeof(a) / sizeof(int), sizeof(b) / sizeof(int), sizeof(c) / sizeof(int) }; 
        int len = sizeof(pArr) / sizeof(int*);   

        for (i = 0; i < len; i++) { 
                for (int j = 0; j < sub_len[i]; j++) 
                        printf("%d ", pArr[i][j]); 
                printf("\n"); 
        } 
}

a,b,c 배열의 길이는 전부 다릅니다. 하지만 문제없지요. 왜냐면 포인터는 배열의 시작주소만 알면 되기 때문입니다.

각각의 포인터들(pArr[0], pArr[1], pArr[2])은 배열의 시작주소 a, b, c를 가리키고 있습니다.

포인터 역시 배열처럼 첨자를 쓸수도 있다는 것을 다들 아실겁니다.

배열포인터

배열포인터는 무엇일까요? 아까 포인터배열은 포인터를 배열로 나열한 것이라고 설명했으니, 배열포인터는 배열을 가리키는 포인터가 아닐까요?

배열포인터는 다음과 같이 정의합니다.

int (*pArr)[3]

앞서 본 포인터배열과는 다르게 괄호가 추가 되었죠. 이 한 끗 차이에 의미가 변하게 됩니다. 우선 포인터이긴한데, 길이 3을 갖는 int형 배열만을 가리킬 수 있다는 점입니다. 우선 다음 기본적인 코드를 봅시다. 우리가 아는 내용입니다.

#include <stdio.h> 
int main() { 
        int i = 0; 
        int arr[5] = { 1,2,3,4,5 };
        int *pArr = arr; 

        for (i = 0; i < sizeof(arr)/sizeof(int); i++) 
                printf("%d ", pArr[i]);
        printf("\n");
}  
r

pArr은 일차원배열 arr의 시작주소를 가리키고 있다는 내용입니다. 그래서 배열처럼 인덱싱을 통하여 각 원소를 출력하고 있지요. arr의 길이 5는 신경쓰지 않습니다. 단지 가리키기만 하고 있습니다.

이제 위의 정의를 다시 봅시다. 

int arr[행][열] ={ {...}, {...}, {...}};

int (*pArr)[열]= arr;

(*pArr)은 arr의 가장 높은 차원의 길이 3(행)은 신경쓰지 않습니다. 단지 그 시작주소만 가리키기만 하면 되거든요. 하지만 그 보다 낮은 차원의 길이4(열)는 알아야만 합니다. 그래야만 다음 행을 구해낼 수 있기 때문이죠.

어떻게??

pArr[0]은 4개의 int배열을 가리키고 있는 포인터입니다. 따라서 sizeof(pArr[0])을 찍어보면 그 길이가 16이라는 것을 알 수 있습니다. 그래서 주소를 계산할때 지금 행의 주소에 16을 더해야 다음 행을 구할 수 있습니다. 위 코드에서는 1차원 배열이고 각 원소의 길이는 단순히 1이니까 쓰지 않는 것입니다.

이제 2차원 배열을 배열포인터로 구현해봅시다.

#include <stdio.h>
int main() { 
        int i,j; 
        int arr[3][4] = { {1,2,3,4}, {5,6,7,8}, {9,10,11,12} }; 
        int(*pArr)[4] = arr; 
        int row = sizeof(arr) / sizeof(arr[0]);
        int col = sizeof(arr[0]) / sizeof(arr[0][0]);

        for (i = 0; i < row; i++) { 
                for (j = 0; j < col; j++) 
                        printf("%d ", pArr[i][j]); 
                printf("\n"); 
        } 
}

arr의 각 행 길이와 pArr의 행의 길이를 맞추고 있다는 것을 보세요. 그리고 pArr[0:2]는 각각 사이즈가 16이며 마치 배열처럼 동작이 가능합니다. 

이것을 어디다가 활용할 수 있을까요??

함수에 전달인자로 배열을 받을때 주로 사용합니다.

#include <stdio.h>

void printArr(int(*pArr)[4],int row,int col) {
        int i, j; 
        for (i = 0; i < row; i++) { 
                for (j = 0; j < col; j++) 
                        printf("%d ", pArr[i][j]); 
                printf("\n"); 
        }
} 

int main() { 
        int arr[3][4] = { {1,2,3,4}, {5,6,7,8}, {9,10,11,12}}; 
        int row = sizeof(arr) / sizeof(arr[0]); 
        int col = sizeof(arr[0]) / sizeof(arr[0][0]);
        printArr(arr,row,col); 
}

매개변수를 받으려면 위와 같이 전달받고, 배열처럼 인덱싱을 편하게 사용할 수 있습니다.

더 간편한 방법으로는 int (*pArr)[4]를 int pArr[][4]로 바꿔줘도 실행이 가능합니다. 왜냐면 *pArr은 pArr[]과 거의 같은 의미이기 때문입니다.

void printArr(int pArr[][4],int row,int col) { 
        int i, j; 
        for (i = 0; i < row; i++) { 
                for (j = 0; j < col; j++) 
                        printf("%d ", pArr[i][j]);
                printf("\n"); 
        }
}

이상 끝~~~~~~~~~~~~~~~~~~~~~~~~~~~~