'분류 전체보기'에 해당되는 글 229건

BOJ [1260] DFS와 BFS

문제해석

그래프를 DFS와 BFS 순으로 탐색한 결과를 반환하면 되겠습니다.

제약조건

간선 M은 10000개 이하, 정점 N은 1000 이하입니다.

그냥 묻지도 따지지도 않고 DFS, BFS 오지게 코딩하시면 됩니다.

문제풀이

DFS와 BFS에 대한 설명은 아래의 링크를 통해서 확인해주세요.

DFS https://reakwon.tistory.com/4?category=300866

BFS https://reakwon.tistory.com/7?category=300867

코드

#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;

vector<int> dfs_order = vector<int>();
vector<int> bfs_order = vector<int>();
vector<bool> visited;
int map[1001][1001];

int V,E;

void dfs(int here) {
	
	visited[here] = true;
	dfs_order.push_back(here);

	for (int to = 1; to<=V; to++) 
		if (!visited[to] && map[here][to] == 1) 
			dfs(to);
}

void bfs(int start) {

	queue<int> q;
	q.push(start);
	bfs_order.push_back(start);
	visited[start] = true;

	while (!q.empty()) {
		int here = q.front();
		q.pop();
		for (int next = 1; next<=V; next++) 
			if (!visited[next] && map[here][next] == 1) {
				q.push(next);
				bfs_order.push_back(next);
				visited[next] = true;
			}
	}
}

void print_order(vector<int> &order) {
	for (int i = 0; i < order.size(); i++)
		printf("%d ", order[i]);
	printf("\n");
}


int main() {
	
	scanf("%d %d", &V, &E);

	int start;
	scanf("%d", &start);
	for (int i = 0; i<E; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		map[a][b] = map[b][a] = 1;
	}

	visited = vector<bool>(V + 1);
	dfs(start);
	visited = vector<bool>(V + 1);
	bfs(start);

	print_order(dfs_order);
	print_order(bfs_order);

}

dfs_order와 bfs_order는 각각 dfs 순으로 방문된 순서를 저장하는 벡터, bfs 순으로 방문된 순서를 저장하는 벡터입니다.

1012번 유기농 배추

문제 해석

문제는 여러가지 방법으로 풀 수 있습니다.

문제는 간단히 말해 이렇답니다.

그냥 1이 뭉쳐저 있는 곳을 세는 겁니다. 

단, 1은 상하좌우를 통해서 연결되어 집니다. 대각선으로 1은 서로 다른 지역으로 인식하게 되는 겁니다.

위의 예제에서는 1이 뭉쳐져 있는 곳이 총 5부분입니다. 그래서 답이 5가 되는 것입니다.

이런 문제는 조금 흔한 문제라서 딱 보면 그거네~ 하실 거에요.

제약 조건

테스트케이스 T가 주어지고 N과 M은 1이상 50 이하입니다. 배추가 심어져 있는 점은 Y, X로 주어집니다.

최대 50*50이 주어질 수가 있겠군요. 

풀이

이 유기농배추가 있는 지도를 그래프로 생각을 해보도록 하겠습니다. 탐색 방법은 어떤 방향이든 좋습니다. 하지만 상하좌우 네 방향을 전부 탐색해야합니다. 단, 1인 정점만 탐색합니다.

현재 위치를 y,x라고 치고 상하좌우를 탐색합니다. 위쪽 정점은 현재 정점의 y-1, x 아래 정점은 현재 정점의 y+1,x, 왼쪽 정점은 현재 정점의 y, x-1, 오른쪽 정점은 현재 정점의 y, x+1입니다.

하지만 이미 방문되었다면 그 정점은 탐색하지 않습니다.

따라서 dfs가 몇번 호출되었는가가 이 문제의 답이됩니다. 코드를 통해서 살펴보도록 할까요?

#include <cstdio>
#include <string.h>
#define M 51
#define VISITED 0
using namespace std;

int n, m, k;
int map[M][M];

void dfs(int y, int x) {
	
	if ( y<0 || y >= n || x < 0 || x >= m || map[y][x] == VISITED )
		return;

	map[y][x] = VISITED;
	dfs(y + 1, x);	dfs(y, x + 1);
	dfs(y - 1, x);	dfs(y, x - 1);
}

int main() {
	int T;

	scanf("%d",&T);
	for (int t = 0; t < T; t++) {

		memset(map, 0, sizeof(map));

		scanf("%d %d %d", &m, &n, &k);
		for (int i = 0; i < k; i++) {
			int y, x;
			scanf("%d %d", &y, &x);
			map[x][y] = 1;
		}

		int count = 0;
		for (int y = 0; y < n; y++) {
			for (int x = 0; x < m; x++)
				if (map[y][x] == 1) {
					dfs(y, x);
					count++;
				}
		}
	
		printf("%d\n", count);
	}
}

이중 for문을 돌며 1이 등장하면 그 정점부터 dfs를 실행합니다.  dfs는 그 정점이 0이거나 y, x가 범위 밖이면 바로 return 됩니다.

그렇다면 우리는 그냥 0을 방문되었다고 표현하면 더 간단하게 문제를 풀 수 있지 않을까요?

아래 사진처럼 0,0에서 1을 만났다고 치겠습니다. 그렇다면 그 지점 0,0에서 dfs를 수행하면 앞뒤 양옆을 dfs로 순차적으로 돌아 전부 방문됩니다. 그러면 0으로 값이 변하게 되지요. 이 부분이 두번째 사진의 빨간색으로 된 0으로 표현을 했네요.

dfs가 끝났으니 for문을 계속 수행합니다. 하지만 이미 dfs가 돌아 0으로 값이 변했으므로 skip됩니다.

이런 식으로 dfs를 한번 돌게 되면 하나의 덩어리를 구할 수 있습니다. 이 덩어리의 수를 세는 것이 답입니다.

답은 위 코드의 count로 표현됩니다.

시간 복잡도는 N*M이 됩니다. 

이외에도 BFS를 통해서도 문제의 해답을 구할 수도 있습니다. 

마찬가지로 for문 속에서 일일이 루프를 돌면서 아직 방문되지 않는 점이 있으면 bfs를 돌고 count에 1을 더해 주기만 하면 되거든요.

BFS나 DFS나 둘 중 하나만 알아도 이 문제는 풀 수 있습니다.

또 어떤 방법으로 풀 수 있을까요??

배열과 포인터

배열과 포인터는 아주 유사한 성격을 갖고 있습니다. 배열은 뭘까요?

우선 배열에 대해서 알아봅시다. 배열은 같은 자료형이 연속된 공간으로 나열되있는 것을 뜻합니다. 배열에 대해서 조금 더 쉽게 접근하기 위해서 index를 갖는데요. index를 통해 빠르게 배열 원소에 접근하게 됩니다.

int a[5]={5, 3, 1, 2, 4};

이와 같은 배열이 있다면 메모리의 구조는 바로 이렇게 구성될겁니다.

왜 이런식으로 배열이 구성이 될까요??

왜 배열의 원소는 4바이트나 되는 걸까요.

그 이유는 int가 4바이트이기 때문입니다. 따라서 4바이트씩 주소가 증가하고 있는 겁니다.

그렇다면 char형의 배열은 한 원소의 크기가 1바이트이고, long long배열의 한 원소 크기는 8바이트가 되는 겁니다. got it?

사실 a라는 변수는 a[0]의 주소값을 갖고 있습니다. 배열의 시작주소를 가지고 있다는 거지요.

따라서 a는 &a[0]와 같은 값을 나타냅니다. a는 a[0]의 주소를 가리키고 있다는 겁니다. 

a가 주소값을 가지고 있다고??

그렇다면 a가 가지고 있는 주소를 참조한다면 *a로 a가 참조하는 값을 구할 수 있겠네요. 그러면 정말 a[0]의 값을 참조할까요? 

코드로 확인해보세요.

이제부터는 다른 배열의 다른 연산법을 알아보겠습니다. a는 a[0]을 가리키고 있는 포인터라고 했습니다. a[0]은 5의 값을 가지고 있습니다. 

헌데, a가 a[0]를 가리키고 있으니, *a는 a[0]의 값을 나타내게 되는 것이지요.

그렇다면 이렇게 변형해볼까요?

*(a+0) 는 *a와 같은 뜻이 될까요? 아마 그렇겠죠?

그렇다면 *(a+1)은 어떤 값을 나타나게 될까요?? 결론부터 말씀드리면 a[1]의 값을 갖게 됩니다. 어떤 포인터의 +1은 그것이 참조하고 있는 자료형의 크기만큼 주소를 더하라는 의미가 됩니다. 

그렇다면 *(a+i)는 a[i]가 되겠네요!! 와우!!

이제껏 지껄인 말이 확실한지 코드로 확인해보도록 하겠습니다.

#include <stdio.h>

int main() {
	int i;
	int a[5] = { 5,3,1,2,4 };
	
	
	
	printf("a의 주소 &a[0] = %p, a = %p \n", &a[0],a);
	printf("a의 값: %d\n", *a);
	for (i = 0; i < 5; i++)
		printf("\t 주소 %p  a[%d] : %d, *(a+%d) : %d\n",(a+i),i,a[i],i,*(a+i));

}

다음 사진은 결과를 보여줍니다.

제가 설명한 내용이 맞나요??

a의 값은 a[0]의 주소와 같네요!! 주소 값은 역시 4바이트씩 증가합니다. 

아까 포인터 연산 역시 제가 설명한 대로 나오고 있습니다.

포인터로 배열을 참조할 수 있습니다.

방금 전 배열 a를 포인터 ptr로 참조해보도록 하지요.

int *ptr = a;

로 간단하게 a라는 배열을 포인터로 참조할 수 있습니다.

a 역시 배열의 주소를 가지고 있고 ptr 역시 배열 a를 가리키고 있습니다. 그래서 a와 ptr은 같은 곳을 바라보게 되는 거죠.

그러면 ptr 역시 a가 가지는 특성을 그대로 가지고 있을까요?

코드로 확인해봅시다. 컴퓨터는 거짓말을 하지 않으니까

#include <stdio.h>

int main() {
	int i;
	int a[5] = { 5,3,1,2,4 };
	int *ptr = a;
	
	
	
	printf("a의 주소 &a[0] = %p, a = %p \n", &a[0],a);
	printf("a의 값: %d\n", *a);
	
	for (i = 0; i < 5; i++)
		printf("\t 주소 %p  a[%d] : %d, *(a+%d) : %d\n",(a+i),i,a[i],i,*(a+i));

	printf("\n");

	printf("ptr이 가리키는 주소 : %p\n", ptr);
	for (i = 0; i < 5; i++)
		printf("\t 주소 %p  p[%d] : %d, *(p+%d) : %d\n"
			,(ptr+i),i,ptr[i],i,*(ptr+i));
	
	
}

 

정확히 똑같은 성질을 갖고 있다는 것을 알 수 있습니다.

그러면 둘의 차이는 없을까요??

이 둘의 차이는 크기에서 차이가 납니다.

sizeof연산을 한 번 해보도록 하지요.

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

	printf("a의 사이즈 :%d, ptr의 사이즈 :%d\n", sizeof(a), sizeof(ptr));
}

결과

음.....

a의 사이즈는 20이고, ptr의 사이즈는 4바이트네요.

a는 배열의 크기를 갖고 있습니다.

a는 int형(4바이트) 배열로 5개가 할당되어있으니 20바이트이지요.

하지만 ptr은 단순히 그 배열을 참조해야하기 때문에 주소값만 저장할 수 있는 공간이면 충분합니다. 따라서 4바이트면 충분합니다.

그리고 배열은 상수화가 된다는 것이 특징입니다. 배열의 원소는 변경가능합니다. 하지만 배열 변수를 다른 값으로 변경할 수는 없습니다.

int a[5];

int b[5] = {5, 3, 1, 2, 4} ;

a=b;

a는 b와 크기가 같고 자료형이 같음에도 불구하고 이와 같은 코드는 컴파일 에러를 불러일으키게 되는 겁니다.

a는 a[0]의 주소입니다. b 역시 b[0]의 주소입니다.

주소는 read-only입니다. 즉, 값을 대입할 수가 없습니다 절대로!

위의 코드는 이것과 같은 얘기가 됩니다. 

&a[0] = &b[0] 이라는 거죠.

이제까지 이야기한 내용을 이해하셨다고 한다면 이해가 갈겁니다.

주소는 포인터만이 참조할 수 있는 포인터만의 특성입니다.

그러니까 위의 코드는 이렇게 바뀌어야합니다.

int *a;

int b[5] = {5, 3, 1, 2, 4} ;

a=b; //a=&b[0]과 같음.

배열과 포인터의 관계 이해하셨는지요??

이것으로 배열과 포인터의 관계를 마치겠습니다~~~

BFS(Breadth First Search, 너비우선탐색)

그래프 이론 DFS와 BFS 중 BFS는 그래프를 가까운 정점부터 순서대로 탐색하는 그래프 탐색 알고리즘이랍니다. 그래프에서 탐색 시 아주 많이 사용되는 탐색기법이지요. 우선 다음과 같은 무향그래프가 있다고 가정해보겠습니다. 

우선 그래프 탐색을 하기 전에 조건이 있습니다.

1. 처음 정점 0부터 시작한다고 칩시다.

2. 정점을 방문한 적이 있다면 다시 방문하지 않는다.

3. 방문해야 할 정점이 여러 개일 경우 가장 번호가 낮은 정점부터 방문한다.

BFS로 위 그래프를 탐색하는 과정을 보겠습니다 

1. 0을 방문한다.

2. 0과 가장 가까운 정점을 찾는다 ( 1, 5, 6).

3. 1이 방문되지 않았으므로 1을 방문한다.

4. 5가 방문되지 않았으므로 5를 방문한다.

5. 6이 방문되지 않았으므로 6을 방문한다.

6. 1에서 가장 가까운 정점을 찾는다 (0, 2, 3).

7. 0은 이미 방문했으므로 skip한다.

8. 2는 방문되지 않았으므로 2를 방문한다.

9. 3이 방문되지 않았으므로 3을 방문한다.

10. 5에서 가장 가까운 정점을 찾는다 (0, 6).

11. 0과 6은 방문됐으므로 skip한다.

12. 6과 가장 가까운 정점을 찾는다 (0, 5).

13. 0과 5는 이미 방문됐으므로 skip한다.

14. 2와 가장 가까운 정점을 찾는다 (1, 4). 

15. 1은 이미 방문됐으므로 skip한다.

16. 4는 방문되지 않았으므로 4를 방문한다.

17. 모든 정점을 지나쳤으므로 종료한다.

이제 방문된 점을 차례대로 나열해본다면  0 - 1 - 5 - 6 - 2 - 3 - 4 로 방문이 되는 것을 확인 할 수 있습니다. 코드로 표현하면 어떻게 될까요? 아래 C++ 소스코드로 BFS를 구현해보았습니다.

#include <cstdio>
#include <vector>
#include <queue>
#define V 7
using namespace std;

int g[V][V] = {
	{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}
};

vector
 bfs(int start) {
	vector discovered(V, false);
	queue next;

	vector order;

	visited[start] = true;

	next.push(start);
	while (!next.empty()) {
		int from = next.front();
		next.pop();

		order.push_back(from);

		for (int to = 0; to < V; to++) {
			if (g[from][to] == 1 && !visited[to]) {
				next.push(to);
				visited[to] = true;
			}
		}
	}
	return order;
}
int main() {

	vector bfsOrder = bfs(0);
	for (int i = 0; i < V; i++)
		printf("%d ", bfsOrder[i]);
}

이 후 0은 방문될때 큐에서 꺼내어 집니다. 그 다음에 0에서 가장 가까운 정점 중에 방문되지 않은 정점을 큐에 저장합니다. 이렇게 말입니다.

0을 방문합니다. 0은 큐에서 꺼내어 지고 0과 가장 가까운 정점 1 5 6이 큐에 저장됐습니다. 그 후에는 다시 1을 큐에서 꺼내오고 1과 가장 가까운 정점을 큐에 집어 넣습니다.

단, 방문되지 않은 녀석들로요.

1은 방문이 되어 큐에서 나오고 2와 3이 추가 돼었군요. 역시 과정은 계속 반복됩니다. 다음 5가 방문될 차례입니다. 5를 꺼내고 5와 가장 가까운 정점을 추가합니다.

5와 가장 가까운 정점 0과 6이 있는데, 6은 아직 큐에 존재하니까 방문하지 않은 걸로 간주합니다. 그래서 6을 다시 큐에 집어 넣습니다. 다음 6을 방문합니다. 

6과 가장 가까운 정점 0과 5는 이미 방문된 상태랍니다. 그래서 큐에 집어 넣지 않습니다. 다음 2를 방문합니다. 

2과 가장 가까운 정점은 1, 4로 1은 이미 방문된 상태로 넘어가고 4는 큐에 들어갑니다. 왜냐면 방문될 정점으로 큐에 아직 존재하니까요. 다음 3을 방문합니다.

3과 가장 가까운 정점 1은 이미 방문된 상태라 넘어갑니다. 다음 4를 방문합니다.

4와 가장 가까운 정점 2는 이미 큐에서 나와 방문이 되었습니다. 어느 정점하나 큐에 들어가지 않습니다. 이제 큐에 남아있는 방문될 정점 6과 4는 이미 방문이 되었으므로 큐에서 그냥 빠져나옵니다. 방문되지 않는 다는 뜻입니다. 버립니다.

이로써 큐는 모두 비워졌습니다. 큐가 비워졌으니 더 이상 방문할 정점이 없으니 BFS과정은 끝나게 됩니다. 이로써 BFS가 어떻게 동작하는 지 살펴보았습니다. BFS는 그럼 도대체 언제 사용하게 될까요? 그건 다음에 알아보도록 하겠습니다.

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를 도대체 어디에 활용할 수 있을까요? 배웠으면 써먹어야 될꺼 아니겠어요? 그런 다음 포스팅에 알아보도록 하겠습니다.

동적계획법(Dynamic Programming)

동적계획법(Dynamic Programming)이라는 것은 알고리즘에서 아주 자주 등장하는 주제입니다. 줄여서 DP라고도 부릅니다.

DP의 특징은 어떤 부분 문제는 두 개 이상의 문제를 푸는 데 사용될 수 있습니다. 그래서 "답을 여러 번 계산하는 대신 한번 만 계산한다!" 입니다.  

개인적으로 DP를 보면 항상 먼저 떠오르는게 바로 재활용이라고 생각합니다. 재활용을 통해서 속도를 빠르게 향상 시킬 수 있는 방법입니다.

어떻게 재활용을 할 수 있을까요? 가장 유명한 피보나치 수열을 한 번 보도록 해봅시다. 피보나치의 정의는 아래와 같습니다. 간단합니다.

이 피보나치 수열을 재귀함수로 정의해보겠습니다. 

int fibo(int n) {
	if (n == 0) return 0;
	if (n == 1) return 1;
	return fibo(n - 1) + fibo(n - 2);
}

이런식으로 정의가 될 것 같네요. 여기서 n은 무조건 양수라고 가정하겠습니다. 음수는 귀찮습니다. 만약 fibo(5)라는 값을 계산하려면 어떤 과정을 거칠까요?

fibo(5) = fibo(4) + fibo(3) 라는 것을 알 수 있고 이제 fibo(4)와 fibo(3)을 더해주기만 하면 됩니다.

그럼 왼쪽 fibo(4)부터 차근 차근히 계산을 해보도록 하겠습니다. 노가다로 해보겠습니다.

fibo(4) = fibo(3) + fibo(2) 

이것도 역시 fibo(3), fibo(2)를 계산해야 되겠군요

fibo(3) = fibo(2) + fibo(1) 이 되겠습니다.

fibo(2) = fibo(1) + fibo(0) 이 되어서 fibo(2) = 1이라는 것을 알게 됩니다.

그렇다면 fibo(3) = fibo(2) + fibo(1) 이니까 1+1 해서 fibo(3) = 2라는 것을 알 수 있겠네요.

fibo(4) = fibo(3) + fibo(2) 랍니다. 여러 분, 이제 슬슬 감이 오고 있나요? 노가다 하기 싫습니다.

fibo(4) = 2 + fibo(2)라는 것이 됩니다. fibo(3)을 방금전에 계산했거든요. 그러면 오른쪽 fibo(2)를 구해보도록 합시다.

fibo(2) = fibo(1) + fibo(0) 으로 fibo(2)=1입니다.

그럼 fibo(4) = 2+ 1 = 3 이라는 결과가 나옵니다. 이제 fibo(4) 구한 겁니다.

이제 fibo(3)을 구해볼까요?

이제 손가락이 아파서 못할 거 같고요

fibo(3) 뭐라고 했지요? 아까 계산했는데 말입니다.

2가 나왔죠?

이 같은 노가다를 막기 위한 것이 바로 DP의 큰 역할이라고 할 수 있겠습니다. 만약 위의 저 코드를 통해서 fibo(40)을 계산한다면 얼마나 걸릴까요? 아마 계산했던 결과를 또 계산하고 앉아있으니 오래 걸릴거라는 걸 짐작할 수 있나요?

네, 오래 걸립니다. 우리는 이제 계산된 값을 재활용 합시다. 이렇게요.

int dp[50];
int fibo(int n) {
	
	if (n == 0) return 0;
	if (n == 1) return 1;
	if (dp[n] != -1) return dp[n];
	return dp[n] = (fibo(n - 1) + fibo(n - 2));
}
int main() {
	memset(dp, -1, sizeof(dp));
	printf("fibo(40)=%d\n", fibo(40));
}

어떻습니까? 맨 처음 초기화값은 -1입니다. memset함수에 주목합시다. 이 함수는 dp라는 배열을 -1이라는 값으로 전부 초기화 시키는 역할을 하는 것이랍니다. 처음 계산하는 값이라면 dp[n]에 -1이라는 값이 들어있을 겁니다. 그렇지 않을까요? 이해 되십니까?

C언어 문자열 처리 함수

문자열 처리는 어느 언어에서나 중요하죠.

우선 C언어에서 문자열을 처리하려면 string.h를 반드시 포함해야합니다. 

※이제부터 설명하는 함수들은 보안적인 취약점이 발견되있는 함수들이 있습니다. 테스트를 해보시기 전에 SDL을 NO로 설정하세요.

Project - [Project Name] Properties - (왼쪽) C/C++ - SDL checks : No
또는 전처리 구문을 사용합니다.

#define _SECURE_CRT_NO_WARNINGS

가장 많이 쓰이는 4개의 함수에 대해서만 우선 알아 보도록 합시다.

● 문자열 길이  size_t strlen(const char *str) 

문자열을 input으로 넣어주면 반환되는 문자열의 길이가 나오게 됩니다. NULL문자

까지가 아닌 순수 문자열의 길이를 반환해주게 됩니다.

ex)

char str[20] = "hello, world";

int len = strlen(str);

● 문자열 연결 char* strcat(char *_Destination, const char* _Source)

문자열을 합치게 됩니다. _Destination 뒤에 _Source를 이어주게 됩니다. 주의해야 할 점은 매개변수로 _Destination은 배열로써 그 크기가 지정되어진 문자열이어야 합니다. 

ex) 

char dst[30]="dst";    //char *dst="dst"; 로 바꾸게 되면 error가 나오게 됩니다.

char src[30]="src";

printf("%s \n", strcat(dst,src));

● 문자열 비교 int strcmp(const char *_Str1, const char *_Str2)

문자열을 비교하게 됩니다.  

_Str1이 _Str2보다 사전순으로 나중에 등장하면 1

_Str1이 _Str2보다 사전순으로 먼저 등장하면 -1

_Str1과 _Str2와 사전순이 같다면 0

보통 문자열을 비교할때 이 함수를 사용하는데 두 문자열이 같다면 0이 나오기 때문에 문자열이 같은 지 if문에서 확인하려면 !strcmp(str1,str2)로 확인해야 합니다. 왜냐면 str1,str2가 같다면 0(FALSE)가 반환되기 때문이죠.

● 문자열 복사 char* strcpy(char *_Dest, const char *_Source)

문자열 _Source를 _Dest에 복사합니다. strcat와 마찬가지로 _Dest는 배열의 형태로 넘겨받습니다. _Dest에 _Source문자열을 합치기 때문에 _Dest는 _Source의 문자열을 포함할 만큼 크기가 커야합니다.

ex)

char _dest[20] = "hello,";

char _src[10] = "world";

strcat(_dest, _src);

위 네 가지 함수를 실제로 적용시켜볼까요??

#include<stdio.h>
#include<string.h>

int main() {

	char country[32] = "korea";
	char south[32] = "south";
	char southkorea[32] = "southkorea";
	char south_korea[32] = "South Korea";

	printf("문자열의 길이 : %d\n", strlen(country));

	strcat(south, country);
	printf("문자열 결합 : %s\n", south);

	printf("문자열 비교 : ");
	if (!strcmp(south, southkorea)) {
		printf("%s = %s\n", south, southkorea);
	}
	else {
		printf("%s != %s\n", south, southkorea);
	}


	strcpy(southkorea, south_korea);
	printf("문자열 복사 : %s\n", southkorea);

}

그리고 그 결과입니다.

이상으로 문자열과 관련해서 자주쓰이는 함수 몇가지를 살펴보았습니다.