함수포인터

우리는 이제까지 어떤 변수를 가리키는 포인터, 배열을 가리키는 포인터를 사용해보았어요. 물론 이정도를 알아도 상당히 훌륭하다고 생각합니다.

그렇지만 변수뿐만 아니라 함수도 포인터로 가리킬 수 있다는 것을 알게 된다면 조금 더 간지나는 프로그래밍을 시도해 볼 수 있겠습니다. 이제부터 설명할 것이 무엇이냐, 그 이름하여 함수포인터랍니다. 

함수포인터라... 그냥 포인터도 극혐인데 말이죠

함수포인터란 함수를 가리킬 수 있는 포인터를 의미합니다. 아니, 근데 그러면 주소를 알아야하는데, 함수에도 주소가 있나? 네, 있습니다. 함수가 주소를 가지고 있다구요? 제말이 구라가 아님을 보여드리겠습니다.

#include <stdio.h>
int sum(int a, int b) { 
        return a + b;
} 

int main() { 
        printf("함수 sum의 주소 : %p\n", &sum);
}

이 코드의 결과는 어떻게 될까요? 우리는 변수명 앞에 &(amp)를 붙여 변수의 주소를 알게 됩니다. 그렇다면 &함수명은 무엇을 의미하게 될까요? 아무리 눈치없어도 진짜 이정도면 눈치채야지~

신기하네요. 16진수로 어떤 수가 나오네요. 눈치채셨겠지만 함수의 주소를 의미하게 됩니다. 바늘가는데 실간다는데 주소가 있으면 포인터가 있겠죠. 그렇다면 함수포인터를 선언하는 방법을 알아보도록 하겠습니다. 간단합니다.

①int ②(*ptrSum)③(int a,int b)

일반 포인터와 마찬가지로 주소를 가리킬때는 *을 사용해서 포인터라고 알려줍니다.

①은 함수의 반환형을 의미합니다.

②는 함수포인터의 이름을 의미합니다. (변수명과 같이 임의로 정해줍니다.)

③은 매개변수를 의미합니다. 매개변수가 없을 때는 빈 괄호나 void를 사용합니다.

네, 위 세가지만 지켜주면 됩니다.

그러니까 ptrSum이라는 함수포인터는 반환형이 int형이고 매개변수 2개를 갖는데, 둘 다 int형 매개변수인 함수포인터가 되겠습니다.

그렇다면 다음과 같은 함수포인터는 무엇을 의미할까요?

void (*ptrFunc)()

함수명이 ptrFunc인데, 반환값이 없고(void), 매개변수도 없는 함수포인터를 의미합니다. 이제 응용가능하시겠죠? 함수포인터에서 반환형과 매개변수가 일치하는 함수만 함수포인터에 할당이 가능합니다. 기억하세요.

함수포인터를 선언하는 방법은 알게 되었으니, 다음 코드를 통해서 함수포인터의 값이 바로 그 함수의 주소인지 확인도 해보고, 사용도 해봅시다.

#include <stdio.h>
int sum(int a, int b) { 
        return a + b;
}

int main() {
        int(*ptrSum)(int a,int b); 
        ptrSum = sum; 
        printf("sum의 주소: %p\n", &sum); //&sum은 sum과 같음 
        printf("ptrSum의 값: %p\n", ptrSum);
        printf("ptrSum의 주소: %p\n", &ptrSum);
        printf("ptrSum(%d, %d) = %d\n", 3, 4, ptrSum(3, 4));
}

우리는 sum이라는 함수의 주소가 0x00081023번지라는 것과 ptrSum이 0x00081023을 가리키는 것을 확인할 수 있습니다(실제 sum도 함수의 주소, &sum도 함수의 주소입니다).

그리고 그 함수포인터의 주소는 0x0026FB04번지네요.

함수포인터를 통해서 호출(ptrSum(3,4)) 확인해볼 수 있군요. 

(코드에서 나오지는 않았지만 함수포인터의 크기는 역시 4바이트입니다. 포인터이기 때문에요.)

조금 더 쉽게 그림을 통해서 보도록할게요.

포인터를 설명할때 아주 많이 사용하는 그림이죠? 지겹죠?

0x0026FB04번지에 있는 ptrSum이라는 함수포인터는 0x00081023번지에 있는 함수 sum의 시작주소를 가리키게 됩니다.

sum은 함수이기 때문에 시작주소를 갖고 있고, 그 주소를 기점으로 매개변수를 할당, 그리고 함수 내부의 변수들을 스택에 따라 쌓아올립니다. 그러니까 함수의 시작주소를 통해 변수의 주소를 알게 됩니다. 함수의 시작주소는 중요하단 거죠. (더 자세하게 함수호출과정을 아는 것도 도움이 됩니다. 구글형님께 물어보세요.)

그런 sum의 시작주소를 ptrSum은 알고 있기 때문에 sum함수를 호출할 수 있는 겁니다.

아니, 그렇다면 sum함수만 호출하면 되지, 왜 굳이 포인터를 써서 호출하는 거야?

저도 무척이나 이런 생각을 하고 하고 또 하면서 그냥 함수포인터를 흘려 넘겼었죠.

근데 쓰임새는 꽤나 많습니다. 예를 들면 함수 자체를 매개변수로 받고 싶을때가 있을 겁니다.

프로젝트를 진행할때 한 사람만이 진행한다면 물론 상관이 없지만, 여러 사람과 협업을 해야하거나, 라이브러리를 제공할때, 함수에 함수자체를 매개변수로 받아야할 때가 있습니다. 누가 어떤 함수를 필요로 할지 모르니, 어떤 형식으로 함수를 정의해서 매개변수로 전달하게 되면 그 함수를 내부에서는 호출하게 되는 식으로 말이죠.

void func(void (*ptr)()) {
...      ptr();       ... 
}

그리고 또 구조체에서 멤버함수를 커스터마이징할때도 사용할 수가 있습니다. 

struct animal{     
...       void (*walk)();       ... 
}

위에서 walk라는 멤버함수를 우리가 원하는 대로 기능을 정의해줄 수 있습니다. 물론, 함수포인터의 형식과 맞는다면 말이죠. 이런 방식은 자바에서 interface라고 하여 메소드를 구현하는 방식과 비슷해보입니다. 함수포인터를 더 연습해보고 개념을 확실히 이해하세요.

이것으로 함수포인터에 대해 알아보았습니다.

1912번 연속합

문제 해석

수열에서 연속된 수들의 합이 가장 큰 것을 구하는 문제입니다.

10, -4, 3, 1, 5, 6, -35, 12, 21, -1 라는 수열에서 가장 큰 연속은 얼마일까요?

12, 21 부분이 가장 큰 연속합입니다.

연속합의 수들은 한개 이상이라는 점입니다.

음

쉬워보입니다.

처음 시작점을 고정하고 끝점을 하나씩 늘려가면서 시작점과 끝점을 전부 더하는 거죠. 전부 현재의 최대값과 비교해서 크면 그게 최대값이 되는 식으로요.

#include <cstdio>
#include <algorithm>

using namespace std;

int main() {
	int n;
	int nums[100001];

	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d", &nums[i]);

	int ans = -1001;
	for (int start = 0; start < n; start++) {
		for (int end = start; end < n; end++) {
			int sum = 0;
			for (int i = start; i <= end; i++)
				sum += nums[i];
			ans = max(sum, ans);
		}
	}
	printf("%d\n", ans);
}
	

네, 이렇게 제출하면 시간초과랍니다. 하하

입력이 자그마치 10만개가 되거든요.

단순히 이렇게 for루프만 돈다면 문제를 해결할 수가 없습니다.

여기서 간단한 이론(?)이 있는데요.

부분합이라는 개념이 여기 사용됩니다.

우리는 전에 계산한 합을 이용할 수 있다는 거죠.

[0]~[5]까지의 합은 [0]~[4]까지의 합 + 현재의 수를 더하면 된다는 것을 알 수 있습니다.

코드로 본다면 이런 형태이죠.

for (int i = 1; i <= n; i++)
		partialSum[i] = partialSum[i - 1] + numbers[i];

i가 1부터 시작한 이유는 조금 더 보기 편하게 하기 위함입니다. 그러니까 n까지 for루프를 돌아야 됩니다.

그렇다면 [7]~[8]까지의 합만을 구하려면 어떻게 할까요?

partialSum[8]-partialSum[6]을 하게 되면 [7]과 [8]의 부분합만을 구할 수 있습니다.

그럼 1부터 3까지의 합은 partialSum[3]-partialSum[0]이 되겠죠? 인덱스를 왜 1부터 시작하는 지 이유를 알 것 같습니다. 그렇지 않으면 if문을 사용해야합니다.

이제 우리는 위의 코드를 2개의 for문으로 줄일 수 있습니다.

#include <cstdio>
#include <algorithm>

using namespace std;

int main() {
	int n;
	int partialSum[100001];

	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		int number;
		scanf("%d", &number);
		partialSum[i] = partialSum[i - 1] + number;
	}
	int ans = -1001;
	for (int start = 0; start <= n-1; start++) {
		for (int end = start + 1; end <= n; end++) {
			ans = max(ans, partialSum[end] - partialSum[start]);
		}
	}
	printf("%d\n", ans);
}
	

부분합을 이용해서 이중 for문으로 문제에 접근할 수도 있지만, 이 역시 시간초과가 됩니다. 아까 말한것 처럼 입력이 10만개이기 때문에 이중 for문 역시 시간초과죠.

여기서 한 번 더 줄일 수 없을까요?

부분합을 이용해서 말이죠. 

그전까지 계산한 부분합 + 지금 숫자가 지금 숫자보다 작다면 부분합은 다시 계산 되어야 한다는 것을 직관적으로 느낄 수 있을까요??

그러니까...

현재의 수를 numbers[i]라고 하고 그 전까지 계산했던 부분합이 partialSum[i-1]라고 할때 , partialSum[i]=max(partialSum[i-1]+numbers[i], numbers[i]) 라고 하는 것 말이에요.

다시말해,

partialSum[i]=max(partialSum[i-1]+numers[i], numbers[i])

                =max(지금까지의 부분합, 현재 수)

라고 하는 것이 이해가 가시나요?

지금까지 구한 부분합이 현재의 수보다 작다면 현재의 수부터 다시 부분합을 계산하는 것이 더 클 거니까요.

이것만 이해가 간다면, 다음의 코드는 이 과정을 배열없이 구현했다라는 것을 알 것입니다.

#include <cstdio>
#include <algorithm>

using namespace std;

int main() {
	int n, partialSum = 0, maxPartialSum = -1001;
	scanf("%d", &n);

	for (int i = 1; i <= n; i++) {
		int number;
		scanf("%d", &number );
		partialSum = max(number, number + partialSum);
		maxPartialSum = max(partialSum, maxPartialSum);
	}

	printf("%d\n", maxPartialSum);
	
}
	

코드가 무척이나 짧아졌습니다.

문제의 답은 maxPartialSum입니다. 

코드에서 이 부분을 보세요.

partialSum = max(number, number + partialSum);

number는 현재의 수를 말하는 것이고, partialSum은 이전까지 계산했던 부분합을 의미합니다.

현재의 수와 이전까지 계산했던 부분합 + 현재의 수가 현재의 수보다 작다면 부분합은 다시 현재의 수부터 시작입니다.

이후 이 부분합(partialSum)과 지금까지 부분합의 최대값(maxPartialSum)을 비교해서 큰 값이 다시

maxPartialSum이 되는 것입니다.

2178번 미로탐색

문제 해석

추석인데 할게 없으니, 알고리즘 하나 풀어보자구요!

NxM행렬이 있습니다. N은 행의 수, M은 열의 수인데, 1은 통과 가능한 구역, 0은 통과하지 못하는 공간이라고 문제 설명에서 말합니다.

(1,1)부터 시작해 (N,M)까지 오는데, 가장 적게 1을 통과하는 수를 구하는 게 문제의 답입니다.

아래처럼 빨간 색으로 된 1을 통과하는 게 답이 되겠고, 15가 답이 됩니다.

물론 답은 여러가지가 있을 수도 있겠죠?

위에 빨간점대로 이동하지 않고도 녹색점을 거쳐서 오는 경우도 가능한데, 어차피 답은 똑같다라는 점입니다.

한칸 띄어서 정수형으로 주지 귀찮게

#include <cstdio>
#include <queue>
#include <string>
#include <string.h>

using namespace std;

int n, m;
bool visited[101][101];
char map[101][101];

struct Point {
	int x, y;
	Point(int _y, int _x) {
		x = _x; y = _y;
	}
};

queue<Point> q;

void pushQ(int y, int x) {

	if (y >= n || x >= m || y<0 || x<0 || visited[y][x] || map[y][x] == '0') return;
	q.push(Point(y, x));

	visited[y][x] = true;
}

int bfs() {

	pushQ(0, 0);
	int count = 1;
	while (!q.empty()) {

		int size = q.size();

		for (int i = 0; i<size; i++) {
			Point here = q.front();
			q.pop();

			if (here.y == n - 1 && here.x == m - 1) return count;

			pushQ(here.y + 1, here.x);
			pushQ(here.y - 1, here.x);
			pushQ(here.y, here.x + 1);
			pushQ(here.y, here.x - 1);
		}
		count++;
	}
	return count;
}

int main() {
	scanf("%d %d", &n, &m);

	memset(visited, false, sizeof(visited));
	for (int i = 0; i < n; i++)
		scanf("%s", map[i]);

	printf("%d\n", bfs());
	return 0;
}

위 코드는 단순하게 (0,0) (문제에서는 1,1라고 했지만, 배열은 0,0부터 첫번째 요소이기 때문에)부터 시작해서 (n-1, m-1)( 역시 배열의 가장 마지막 요소는 n-1, m-1)까지 문자열로 입력을 받고,  bfs를 돕니다.

bfs에서는 우선 시작 정점(0,0)을 큐에 집어 넣습니다. 그 후에 bfs의 size를 호출해 포문을 돌고 그 상하좌우의 정점을 집어 넣게 되는 겁니다. 주의해야할 점은 for루프 조건문에서 직접적으로 q.size()를 호출하면 안된다는 점입니다. for루프 안에서 q에 push되므로 for문을 한번 돌때마다 q.size()가 유동적으로 바뀌게 됩니다.

                int size = q.size();

		for (int i = 0; i<size; i++) {
			Point here = q.front();
			q.pop();

			if (here.y == n - 1 && here.x == m - 1) return count;

			pushQ(here.y + 1, here.x);
			pushQ(here.y - 1, here.x);
			pushQ(here.y, here.x + 1);
			pushQ(here.y, here.x - 1);
		}
		count++;

그렇게 for문을 한 번 돌면 그 주위에 있는 정점 한번을 탐색한 것이니까 count를 하나 증가시켜 주고요. 만약 n-1, m-1 정점까지 도달했다면 바로 이 count를 return하게 되면 몇 번만에 (n-1, m-1)까지 도달했는지 알 수 있습니다.

pushQ함수는 조건에 맞지 않는 정점은 그냥 지나쳐 버립니다.

조건에 맞지 않는 정점이라는 것은 범위밖의 정점( 0보다 작거나 n또는 m보다 큰 정점), 이미 방문된 정점, 또는 0인 정점을 말하는 것이죠.

방문해야 할 정점이라면 큐에 push하고 방문되었다는 표시만 해주는 아주 단순한 함수입니다. visited[y][x] = true가 바로 방문되었다는 표시를 해주는 작업이랍니다.

단순하긴 하지만 이 함수가 없다면 for루프 안에 일일히 if문으로 검사를 해주어야하는 뻘짓을 하게 될겁니다.

void pushQ(int y, int x) {

	if (y >= n || x >= m || y<0 || x<0 || visited[y][x] || map[y][x] == '0') return;
	q.push(Point(y, x));

	visited[y][x] = true;
}

그리고 또 한가지는 pushQ를 총 4번 호출하죠?

for문으로 돌릴 수 있으나, 거기까지 생각하면서 귀찮게 코딩 안하잖아요 우리는...

그냥 짧은거는 복붙합시다... 티도 안나요.

점(point)을 조금 편하게 관리하게 위해서 Point라는 구조체를 사용했습니다.

뭐... 사용하지 않고 그냥 배열로만 해도 상관없구요.

십쥬?