C언어 포인터란?  포인터라쓰고 탈모라 읽는다

C언어에서 포인터는 프로그래밍을 하면서 아주 어렵게 배우는 주제이기도 합니다. 어렵다기보다는 헷갈리는 경우가 많아서 멘탈붕괴가 오고는 하죠. 포인터는 말 그대로 무엇을 가리키는 놈입니다. 무엇을 가리킬까요??

다른 변수의 주소를 가리킵니다! 

모든 변수는 그 데이터가 저장되는 공간의 주소를 갖고 있습니다.

그것을 어떻게 표현할까요??

int B = 4;

int *A = &B;

이렇게 표현하게 됩니다. A는 B의 주소를 값으로 갖고 있다는 의미랍니다. 만약 B의 주소가 0x20이고 B의 값은 4라고 할때 A의 값은 0x20이 됩니다.

만약 B가 가지고 있는 값을 가져오고 싶다고 할때는 *A로 값을 참조할 수 있습니다.

그림으로 나타내면 이런 식으로 나타낼 수 가 있겠지요.

정말 제 말대로 되는 지 코드로 살펴보도록 하지요.

#include <stdio.h> 
int main() { 
        int B = 4;   
        int *A = &B;    
        printf("B의 값:%d\n", B);
        printf("B의 주소 :%p\n", &B);   
        printf("A의 값:%p\n", A);       
        printf("A가 참조하는 값 :%d\n", *A);     
}

 

A는 B를 가리키고 있고, B는 C를 가리키고 있습니다.

int C = 10;

int *B = &C;

int **A = &B;

이렇게 쓸 수 있다는 거지요. A에 **(포인터의 포인터, 이중포인터)가 붙어있는 것을 확인 할 수 있네요

A는 B의 주소값을 값으로 가지고 있고, B는 C의 주소값을 값으로 갖고 있습니다. 그렇다면 A가 B의 값을 참조하려고 한다면 *A가 되겠죠?? 그러면 무슨 값이 나올까요??

바로 B가 가지고 있는 값, C의 주소입니다. A가 C의 값을 참조하기 위해서는 한 번 더 가리켜야하는데요.

그때 더블포인터가 사용이 되는 것입니다.  **A는 10을 확인할 수 있을 겁니다.

코드로 확인해 보도록 하죠.

#include <stdio.h>

int main() { 
        int C = 10; 
        int *B = &C;
        int **A = &B;

        printf("C의 값 : %d\n", C); 
        printf("C의 주소 : %p\n", &C); 
        printf("B의 값 : %p\n", B); 
        printf("B의 주소 : %p\n", &B); 
        printf("B가 참조하는 값 : %d\n", *B);
        printf("A의 값 : %p\n", A); 
        printf("A가 참조하는 값 : %p\n", *A); 
        printf("A가 참조하는 값이 참조하는 값 : %d\n", **A);
}

결과는 아래와 같습니다.

앞서 말한 대로 C의 주소를 B가 값으로 가지고 있고, B의 주소를 A가 값으로 가지고 있는 걸 확인할 수 있겠죠?? *A는 C의 주소값을 갖고 있습니다. 왜냐면 *A는 B의 값을 가리키고 있는 데 B의 값은 C의 주소이니까요!

그렇다면 삼중포인터는 어떻게 될까요??

뭐하러 어려운 포인터를 쓰나?

포인터는 언제 써먹을 수 있을까요? 대표적으로 다음과 같은 상황일때 사용합니다. 

어떤 함수가 있다고 칠게요. 아주 단순합니다. 그저 매개변수인 a와 b의 값을 교환하는 swap이라는 함수입니다.

void swap(int a, int b) {
        int temp; 
        temp = a; 
        a = b;
        b = temp;
}  

int main() {
        int x = 10;
        int y = 20; 
        swap(x, y); 
        printf("x: %d, y: %d\n", x, y); 
}

call-by-value

우리는 x와 y의 값을 바꾸고 싶다 이겁니다. 그 과정을 살펴보지요.

1. 우선 temp에 a의 값을 넣습니다. 그렇다면 10이 temp의 값에 들어있겠네요.

2. 그리고 b의 값을 a에 집어 넣습니다. 그렇다면 a의 값은 b의 값인 20이 들어가겠군요.

3. 마지막으로 변수 b에 temp값을 넣습니다. temp는 10이었으니까 b는 10이 되어지겠군요.

이제 함수에서 빠져나옵니다. 그 값이 바뀌어있을까요? 아닙니다. 이 함수는 a와 b를 함수 내부에서만 교체할 뿐이지, 함수 호출이 끝나고 반환되서도 x와 y의 값은 변함이 없습니다. 왜 그럴까요?

함수인자 a와 b는 전달받은 매개변수의 값(x, y)만 복사해오기 때문입니다.

예를 들면 졸업증명서 원본이 있고, 그걸 복사해서 사본을 갖고 있습니다. 사본을 불에 태워도 원본이 같이 탈까요? 동시에 같이 태우지 않는 한 원본은 살아있습니다. 이렇기 때문에 main에서 swap을 호출하고 나서도 x와 y의 값은 변함이 없습니다.

이런 함수 호출 방법을 Call-By-Value라고 부르는 것입니다.

call-by-reference

그렇다면 우리는 어떻게 함수를 변경해야 할까요?

그럴때 포인터가 사용이 됩니다.

void swap(int *a, int *b) { 
        int temp; 
        temp = *a; 
        *a = *b; 
        *b = temp;
}

int main() { 
        int x = 10; 
        int y = 20; 

        swap(&x, &y);
        printf("x: %d, y: %d\n", x,y);
}

a는 x의 주소를 가리키고 있고, b는 y의 주소를 가리키고 있습니다. a는 x의 주소를 참조하고 있기 때문에 x에 영향이 주게 되는 겁니다. b 역시 마찬가지가 되겠구요.

그림을 통해서 설명해보도록 하지요.

1.  temp = *a

temp에 a가 가리키는 값을 대입합니다. a가 가리키는 값은 10입니다.

2.  *a = *b

a가 가리키는 값에 b가 가리키는 값을 넣습니다. 그림과 같이 x의 값이 변경됩니다.

3. *b = temp

b가 가리키는 값에 temp의 값을 저장합니다. temp는 방금전 10이었기 때문에 b가 가리키는 곳(y)의 값은 10으로 변경됩니다.

결과는 어떨까요?

결과 역시 우리가 예상했던 대로군요. 우리는 이와 같이 함수에서의 조작이 외부 변수에 조작이 가해질때, 그럴때를 Call-By-Reference라고 합니다.

1932번 정수 삼각형

문제가 이해되셨나요?

맨 위 삼각형 꼭지점에 있는 숫자부터 시작해서 아래까지 계속하여 더합니다. 그 중 가장 큰 수를 구하는 것입니다. 

하지만 조건이 걸려있지요! 바로 위에서 아래로 내려올때 대각선 왼쪽, 또는 오른쪽으로 내려오면서 그 숫자를 더하는 겁니다. 

문제에 있는 예제부터 보겠습니다.

#include <stdio.h>
#include <string.h>
#define N 501
#define max(a,b) a>b ? a:b

int triangle[N][N], dp[N][N];
int n;
int solve(int y, int x) {
	if (y>n || x>n ) return -99999999;
	if (y == n) return triangle[y][x];
	if (dp[y][x] != -1) return dp[y][x];
	int ret = 0;
	ret = max(triangle[y][x] + solve(y + 1, x),
		triangle[y][x] + solve(y + 1, x + 1));
	return dp[y][x] = ret;
}
int main() {
	int i;
	scanf("%d", &n);
	for (i = 1; i <= n; i++)
		for (int j = 1; j <= i; j++)
			scanf("%d", &triangle[i][j]);
	memset(dp, -1, sizeof(dp));
	printf("%d\n", solve(1, 1));
	
}

DFS(Depth First Search : 깊이 우선 탐색)

그래프, 어렵습니다. 그래프에 대한 이론은 많은 걸로 알고 있습니다. 그중에서 대표적인 것이 바로 탐색 기법인데요. DFS와 BFS라는 녀석, 이 둘이 가장 대표적입니다. 먼저 DFS(Depth First Search)라고 하는 놈이 있어요. 깊이 우선 탐색이라고 우리는 말하더군요! 이런 거는 역시 그림으로 한 방에 이해를 해버리는 게 좋거든요? 그래서 제가 그림을 하나 준비해왔답니다. 아래와 같은 무향그래프가 있다고 칩시다! 0에서부터 시작해서 모든 정점을 방문하려고 합니다. DFS탐색기법을 사용해서 정점을 방문할때 어떤 순서로 방문하게 될까요?

단, 규칙은 작은 노드순으로 방문한다는 조건으로요

이름답게 그 정점에서 아주 깊숙히 들어갑니다. 들어가서 더 이상 들어 갈 곳 없을 때까지 깊숙히 말입니다. 하지만 이미 방문된 노드라면 그 노드는 다시 방문하지 않습니다. 그럼 이제부터 탐색을 시작해 보겠습니다.

0에서부터 시작해서 노드번호가 작은 순으로 가려면 1을 방문해야겠지요?? 1과 인접한 가장 작은 노드 번호를 갖고 아직 방문하지 않은 노드는 2가 있네요. 2와 인접한 노드 중 가장 작고 방문하지 않은 노드는 4가 있습니다. 4는 더 이상 갈 곳이 없으므로 다시 돌아옵니다.

이제 3을 방문할 차례입니다. 1에 인접한 노드는 2와 3이었는 데 방금 2쪽 노드를 모두 방문했으니까요. 3은 인접한 노드가 1이 있는 데 이미 방문을 했답니다.

1로 다시 돌아와서 그 다음으로 인접한 노드를 찾아봅시다. 5가 있네요. 5에서 인접한 노드 중 방문하지 않고 가장 작은 노드는 6이 있습니다. 6은 이제 마지막 노드가 되겠습니다. 왜냐면 0도 방문했고 5도 방문했으니까요.

이것으로 모두 방문을 해보았습니다. 순서는 0 - 1 - 2 - 4 - 3 - 5 - 6 이렇게 되겠네요.

그림을 그려보면 이런 순서랍니다.

그렇다면 다음은 DFS를 코드로 구현해볼까요? 우리는 g라는 2차원 배열 변수로 그래프를 표현하게 됩니다. 바로 위와 같은 그래프입니다. 그리고 한가지 더 말씀드리자면 visited라는 변수를 통해서 그 정점이 방문이 되었는지 기록합니다. 이미 방문이 되면 더 이상 그 정점을 방문하면 안되니까요.

c 소스코드는 바로 아래와 같답니다.

#include <stdio.h>

#define N 7

int g[N][N]=
{
	{0,1,0,0,0,1,1},
	{1,0,1,1,0,0,0},
	{0,1,0,0,1,0,0}, 
	{0,1,0,0,0,0,0},
	{0,0,1,0,0,0,0},
	{1,0,0,0,0,0,1},
	{1,0,0,0,0,1,0}
};
int visited[N];
void dfs(int here) {

	//지금 here이 이미 방문된 정점이라면 다시 빠꾸
	if (visited[here]) return;

	printf("정점 %d를 방문\n", here);

	visited[here] = 1;	//지금 here 정점은 방문

	for (int next = 0; next < N; next++) 
		//그래프가 이어져있으면서, 아직 다음 정점이 방문되지 않았으면 ㄱㄱ
		if (g[here][next] == 1 && !visited[next]) dfs(next);
}
int main() {
	dfs(0);
}

결과는 이렇습니다.

네, 뭐 간단합니다. 재귀함수로 dfs를 쉽게 구현해볼 수 있습니다. 그렇다면 dfs를 도대체 어디에 활용할 수 있을까요? 배웠으면 써먹어야 될꺼 아니겠어요? 그런 다음 포스팅에 알아보도록 하겠습니다.