상경한 개발자 지망생들

문제 링크

www.acmicpc.net/problem/2252

접근 방법

이 문제는 가장 기본적인 위상 정렬 문제이다. 

이 문제는 크게 3가지 부분으로 나눌 수 있습니다. 

1. 입력을 받음과 동시에 indegree체크

2. q에 초기값 담기

3. q의 값을 pop하며, 조건에 해당하는 값을 push

아래에서 자세한 설명을 하겠습니다.

1. 입력을 받음과 동시에 indegree체크

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		v[a].push_back(b);
		indegree[b]++;
	}

위상정렬은 자신이 무엇인가를 하기 위해 다른 무엇인가가 완료되어야 할 수 있다?

즉, 어떤 일을 하는 순서를 찾는 알고리즘 입니다.

예를 들어, '그냥 기초'를 하기 위해선 완전 기초가 요구되어야 하며, '어려움'을 위해서는 '그냥 기초'가 수행되어야 하고,

'보통'을 위해서는 '완전 기초'와 '진짜 기초'가 모두 수행되어야 합니다. 여기서 indegree는 어떤 노드가 수행되기 위해, 선 수행되어야 하는 노드의 수 입니다. 위의 경우 indegree[완전기초] = 0 , indegree[그냥기초] = 1 , indegree[보통] = 2로 표현 가능합니다.  

2. q에 초기값 담기

	queue<int> q;
	for (int i = 1; i <= n; i++) {
		if (indegree[i] == 0)
			q.push(i);
	}

그럼 가장 먼저 수행가능 한 노드는 어떤 것 일까요? indegree[] = 0인 값들, 즉 자신이 수행되기 위해 선 수행 할 것이 없는 것들입니다. 그러한 값을 q에 담아줍니다.

3. q의 값을 pop하며, 조건에 해당하는 값을 push

while (!q.empty()) {

		int now = q.front();
		q.pop();

		cout << now << " ";

		for (int i = 0; i < v[now].size(); i++) {
			if (--indegree[v[now][i]] == 0) {
				q.push(v[now][i]);
			}
		}
	}

 자 이제 q에서 pop한 값을 now라 한다면, 자신을 수행하기 위해 now가 선 수행되어야하는 노드들의 indegree가 줄어들 것이고, indegree가 0이 된다면 선 수행할 것들이 없다는 의미이므로 q에 담아줍니다.  

소스 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

vector<int> v[32001];
int indegree[32001];
int n, m;

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
		
	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		v[a].push_back(b);
		indegree[b]++;
	}

	queue<int> q;
	for (int i = 1; i <= n; i++) {
		if (indegree[i] == 0)
			q.push(i);
	}

	while (!q.empty()) {

		int now = q.front();
		q.pop();

		cout << now << " ";

		for (int i = 0; i < v[now].size(); i++) {
			if (--indegree[v[now][i]] == 0) {
				q.push(v[now][i]);
			}
		}
	}
}

개발 환경 : VS2019

질문, 지적 환영합니다!

문제 링크

www.acmicpc.net/problem/16637

접근 방법

 문제를 해결하면서 골치 아팠던 3가지 유의사항이 있었다.

※ 유의 사항

1. 입력받는 수의 갯수가 1개일 경우, 해당 값이 정답이 되어야 함

2. 문제에서 요구하는 최댓값이 음수 일 수 있기 때문에, 정답의 초기값을 0으로 설정하지 않는다.

3. 원인은 파악 안했으나, 하단의 소스코드가 문제를 발생시킴.

ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

1. 기본적으로 재귀 함수를 사용하여 괄호 추가가 가능한 모든 경우의 수에 대해 탐색하였고,  연산자와 숫자를 따로 분리하여 관리 하였다.

 괄호 추가가 가능한 모든 경우의 수를 탐색하는 코드이다. 

void solve(int now) {

	for (int i = now; i < numbers.size() - 1; i++) {
		if (visited[i] == false) {
			visited[i] = visited[i + 1] = true;
            		ans = max(ans, calc_result());
			solve(i + 1);
			visited[i] = visited[i + 1] = false;	
		}
	}
}

visited[]는 괄호에 감싸져 있는 숫자를 체크하는 배열이다. 문제의 조건에서 괄호안에는 하나의 연산자만 포함한다고 했으므로, 인접한 두 숫자에 대해서 방문체크를 하게 된다. 이후 calc_result()라는 함수안에서 현제 괄호를 포함한 전체 수식을 계산하게 된다.

calc_result()

long long calc_result() {

	vector <long long> tmpnumbers;
	vector <char> tmptokens;
	vector <bool> visited_t(tokens.size());
	long long result;
	
    //괄호 값 먼저 계산
	for (int i = 0; i < numbers.size(); i++) {
		if (i < numbers.size() -1 && visited[i] && visited[i + 1]) {
			tmpnumbers.push_back(part_calc(numbers[i], numbers[i + 1], tokens[i]));
			visited_t[i] = true;
			i += 1;
		}
		else 
			tmpnumbers.push_back(numbers[i]);
	}
    
    //괄호에서 사용하고 남은 연산자 배열
	for (int i = 0; i < tokens.size(); i++) 
		if (!visited_t[i]) 
			tmptokens.push_back(tokens[i]);

	//괄호의 계산이 종료 된 이후, 전체 수식 계산 
	result = tmpnumbers[0];
	for (int i = 1; i < tmpnumbers.size(); i++) 
		result = part_calc(result, tmpnumbers[i], tmptokens[i - 1]);

	return result;
}

 괄호값을 먼저 계산하여 수를 정리하고, 괄호안에서 사용된 연산자를 제외한 연산자를 모아 다시 수식 생성

입력숫자(numbers) -> 정리숫자(tmpnumbers) , 입력연산자(tokens) -> 정리연산자(tmptokens)

이 함수에는 3가지 과정이 존재한다. 

ex)  1-(2+3)-(4+5)     

1. 괄호 값 먼저 계산

   앞서 visited[]를 통해 괄호의 위치를 체크하였기 때문에 괄호가 포함된 (a ,(+-*), b)를 part_calc() 함수에서 계산하며,

   괄호안에서 사용된 연산자를 visited_t[]로 사용표시를 한다. 또한 괄호가 정리된 이후 계산 될 새로운 숫자 벡터             tmpnumbers에 push한다. 

   tmpnumbers={1, 5, 9} -> 2와3 사이의 '+'위치 체크, 4와5 사이의 '+'위치 체크, visited_t[1]=visited_t[3]=true

2. 괄호에 포함되지 않아 사용되지 않은 연산자를 tmptokens에 담는다.

    tmptokens={-, -}

3. 정리된 전체 수식을 계산한다.

소스 코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n;
vector <long long> numbers;
vector <char> tokens;
bool visited[20];
long long ans = -9999999999;

long long part_calc(long long a, long long b, char token) {

	long long result = 0;
	if (token == '*')
		result = a * b;
	else if (token == '+') 
		result = a + b;
	else if (token == '-') 
		result = a - b;

	return result;
}

long long calc_result() {

	vector <long long> tmpnumbers;
	vector <char> tmptokens;
	vector <bool> visited_t(tokens.size());
	long long result;
	
	for (int i = 0; i < numbers.size(); i++) {
		if (i < numbers.size() -1 && visited[i] && visited[i + 1]) {
			tmpnumbers.push_back(part_calc(numbers[i], numbers[i + 1], tokens[i]));
			visited_t[i] = true;
			i += 1;
		}
		else 
			tmpnumbers.push_back(numbers[i]);
	}
	for (int i = 0; i < tokens.size(); i++) 
		if (!visited_t[i]) 
			tmptokens.push_back(tokens[i]);

	result = tmpnumbers[0];
	for (int i = 1; i < tmpnumbers.size(); i++) 
		result = part_calc(result, tmpnumbers[i], tmptokens[i - 1]);

	return result;
}

void solve(int now) {

	for (int i = now; i < numbers.size() - 1; i++) {
		if (visited[i] == false) {
			visited[i] = visited[i + 1] = true;
			ans = max(ans, calc_result());
			solve(i + 1);
			visited[i] = visited[i + 1] = false;	
		}
	}
	
}

int main() {

	cin >> n;
	for (int i = 0; i <= n/2; i++) {
		int num;
		char token;
		scanf("%1d", &num);
		numbers.push_back(num);
		if (n / 2 != i) {
			scanf("%c", &token);
			tokens.push_back(token);
		}
	}
	solve(0);
	if (n == 1)
		cout << numbers[0];
	else
		cout << ans;
}

개발 환경 : VS2019

질문, 지적 환영합니다!

문제 링크

www.acmicpc.net/problem/1937

접근 방법

 간략히 말하자면 2차원 배열 위에서 현재 값 보다 더 큰 값으로만 이동할 수 있을 때, 가장 멀리 이동 할 수 있는 거리를 구하는 문제이다. 단, 출발점이 정해져 있지 않아 모든 위치에서 출발을 시작 해 봐야 한다. 

 하지만, 동적계획법을 사용하여 많은 계산을 줄일 수 있다 어떻게 줄일 수 있을까?

아래의 그림을 보자!

예를 들어, 9에서 11로 이동한 경우와 5에서 11로 이동한 경우 모두 11에서 부터 끝 까지의 경우의 수는 같다는 것을 알 수 있다. 9 -> 11 -> 15 , 5 -> 11 -> 15, 즉 어떤 위치 부터 끝 까지의 값을 기록하면 중복되는 연산을 줄일 수 있다는 것이다.

dp[세로][가로]로 표현하여 기록할 수 있다.  

pair<int, int> nextdir[4] = { {1,0}, {0,1}, {-1,0}, {0,-1} };

for (int i = 0; i < 4; i++) {
		int next_x = nowx + nextdir[i].first;
		int next_y = nowy + nextdir[i].second;
		if (0 <= next_x && next_x < n && 0 <= next_y && next_y < n) {
			if (map[nowx][nowy] < map[next_x][next_y]) {
				ret = max(ret, solve(next_x, next_y));
			}
		}
	}
dp += ret;
return dp;

가장 오래 살아남아야 하므로, 위의 코드를 보면 상,하,좌,우 4방향으로 이동했을 때 최댓값을 갱신하도록 하여, 현재의 생존일에 더하도록 하였다.   

소스 코드

#include <iostream>
#include <algorithm>

using namespace std;

int map[500][500];
int dp[500][500];
pair<int, int> nextdir[4] = { {1,0}, {0,1}, {-1,0}, {0,-1} };
int result = 0;
int n;

int solve(int nowx, int nowy) {

	int &ref = dp[nowx][nowy];
	int ret = 0;

	if (ref != 0)  //방문한 적이 있다면
		return ref;
	else  // 방문한적이 없다면
		ref = 1;

	for (int i = 0; i < 4; i++) {
		int next_x = nowx + nextdir[i].first;
		int next_y = nowy + nextdir[i].second;
		if (0 <= next_x && next_x < n && 0 <= next_y && next_y < n) {
			if (map[nowx][nowy] < map[next_x][next_y]) {
				ret = max(ret, solve(next_x, next_y));
			}
		}
	}
	ref += ret;
	return ref;
}

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> map[i][j];
	
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			if (dp[i][j] == 0) //방문 한적 없다면
				result = max(result, solve(i, j));
			else //방문한 적 있다면
				result = max(result, dp[i][j]);
		}

	cout << result << endl;
}

문제 링크

www.acmicpc.net/problem/2193

접근 방법

 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.

1. 이친수는 0으로 시작하지 않는다.
2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.

예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.

N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.

문제의 조건에서 알 수 있는 점 들이 있다.

1. 처음 시작은 무조건 1이어야 한다.

2. 1다음엔 0이어야 한다.

3. 0 다음엔 0또는 1이어야 한다.

그럼 dp 테이블은 어떻게 설계해야 할까? 다음 그림을 보자

5자리 수일 때 규칙에 따라 표현하면 이런 트리가 형성 될 것이다. dp는 중복된 연산을 줄이는 것이 핵심이다. 그림을 보았을 때 어떤 부분이 중복되는지 쉽게 찾을 수 있다.

 위의 그림에서 같은 층(자릿수)의 같은 값을 가진 (층:4 값:0) 노드 부터는 자식 노드들의 갯수가 완전히 일치하는 것을 알 수 있다. 

 즉 층(자릿수)과 값(0또는1) 2가지 특성을 사용한 2차원 DP 테이블을 사용해야 된다는 유추를 할 수 있다.

dp[자릿수][값=2]

소스 코드

#include <iostream>
#include <algorithm>

using namespace std;

int n;
long long dp[100][2];

long long solve(int cnt, int now) {

	long long &ref = dp[cnt][now];

	if (ref != 0)  //방문한적 있다면
		return ref;
	if (cnt == n)  //마지막까지 도달
		return ref = 1;
	if (now) 
		ref += solve(cnt + 1, !now);
	else 
		ref += (solve(cnt + 1, now) + solve(cnt + 1, !now));
	return ref;
}

int main() {
	cin >> n;
	cout  << solve(1, 1) << endl;
}

개발 환경 : VS2019

질문, 지적 환영합니다!

문제 링크

https://www.acmicpc.net/problem/12100

접근 방법

(1) 문제에서 제시하는 2048게임은 한 턴에 동, 서, 남, 북 4방향 중 1방향으로 이동이 가능하고, 최대 5번 이동이 가능하므로, 4^5 = 1024가지의 경우의 수가 존재한다. 1024번의 경우의 수를 탐색하기 위해 백트래킹(DFS)기법을 사용하여 최댓값을 도출하면 된다.

(2) 어떤 방향으로 이동을 시킬 때, 3가지 단계로 구분하였다. 

 1. 한쪽으로 모든 숫자를 몰아넣는다.(예시: 서쪽 방향)

 2. 이동시킨 방향(서쪽)의 끝을 기준으로 시작하여 인접한 수가 같으면 합친다.

 3. 다시 이동시킨 방향으로 몰아 넣는다.

이런 과정을 거치면 한 쪽 방향에 대한 이동이 끝난다.

(3) (2)의 과정에 대한 소스 코드

// 서쪽으로 이동 시킬때의 예시
for (int i = 0; i < n; i++) {
	int zerocnt = 0; //빈 공간의 갯수를 새기 위한 변수 -> 수를 몇칸 이동시킬지 결정
    //1번 과정
	for (int j = n - 1; j >= 0; j--) {
		if (map[i][j] == 0) { //빈 공간일 때
			zerocnt++;
		}
		else { //빈 공간이 아닐 때
			if (zerocnt != 0) {
				map[i][j + zerocnt] = map[i][j];
				map[i][j] = 0;
			}
		}
	}
    // 2번 과정
	for (int j = n - 1; j > 0; j--) {
		if (map[i][j - 1] == map[i][j]) { //인접한 숫자가 같다면
			map[i][j] *= 2; 
			map[i][j - 1] = 0;
		}
	}
    // 3번 과정
	zerocnt = 0;
	for (int j = n - 1; j >= 0; j--) {
		if (map[i][j] == 0) {
			zerocnt++;
		}
		else {
			if (zerocnt != 0) {
				map[i][j + zerocnt] = map[i][j];
				map[i][j] = 0;
			}
		}
	}
}

소스 코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n, result;

vector<vector<int>> move(int dir, vector<vector<int>> map) { //0 북 1 서 2 동 3 남
	if (dir == 0) {
		for (int j = 0; j < n; j++) {
			int zerocnt = 0;
			for (int i = 0; i < n; i++) {
				if (map[i][j] == 0) {
					zerocnt++;
				}
				else {
					if (zerocnt != 0) {
						map[i - zerocnt][j] = map[i][j];
						map[i][j] = 0;
					}
				}
			}
			for (int i = 0; i < n - 1; i++) {
				if (map[i][j] == map[i + 1][j]) {
					map[i][j] += map[i + 1][j];
					map[i + 1][j] = 0;
				}
			}
			zerocnt = 0;
			for (int i = 0; i < n; i++) {
				if (map[i][j] == 0) {
					zerocnt++;
				}
				else {
					if (zerocnt != 0) {
						map[i - zerocnt][j] = map[i][j];
						map[i][j] = 0;
					}
				}
			}
		}
	}
	if (dir == 1) {
		for (int i = 0; i < n; i++) {
			int zerocnt = 0;
			for (int j = n - 1; j >= 0; j--) {
				if (map[i][j] == 0) {
					zerocnt++;
				}
				else {
					if (zerocnt != 0) {
						map[i][j + zerocnt] = map[i][j];
						map[i][j] = 0;
					}
				}
			}
			for (int j = n - 1; j > 0; j--) {
				if (map[i][j - 1] == map[i][j]) {
					map[i][j] *= 2;
					map[i][j - 1] = 0;
				}
			}
			zerocnt = 0;
			for (int j = n - 1; j >= 0; j--) {
				if (map[i][j] == 0) {
					zerocnt++;
				}
				else {
					if (zerocnt != 0) {
						map[i][j + zerocnt] = map[i][j];
						map[i][j] = 0;
					}
				}
			}
		}
	}
	if (dir == 2) {
		for (int j = 0; j < n; j++) {
			int zerocnt = 0;
			for (int i = n - 1; i >= 0; i--) {
				if (map[i][j] == 0) {
					zerocnt++;
				}
				else {
					if (zerocnt != 0) {
						map[i + zerocnt][j] = map[i][j];
						map[i][j] = 0;
					}
				}
			}
			for (int i = n - 1; i > 0; i--) {
				if (map[i][j] == map[i - 1][j]) {
					map[i][j] *= 2;
					map[i - 1][j] = 0;
				}
			}
			zerocnt = 0;
			for (int i = n - 1; i >= 0; i--) {
				if (map[i][j] == 0) {
					zerocnt++;
				}
				else {
					if (zerocnt != 0) {
						map[i + zerocnt][j] = map[i][j];
						map[i][j] = 0;
					}
				}
			}
		}
	}
	if (dir == 3) {
		for (int i = 0; i < n; i++) {
			int zerocnt = 0;
			for (int j = 0; j < n; j++) {
				if (map[i][j] == 0) {
					zerocnt++;
				}
				else {
					if (zerocnt != 0) {
						map[i][j - zerocnt] = map[i][j];
						map[i][j] = 0;
					}
				}
			}
			for (int j = 0; j < n - 1; j++) {
				if (map[i][j] == map[i][j + 1]) {
					map[i][j] *= 2;
					map[i][j + 1] = 0;
				}
			}
			zerocnt = 0;
			for (int j = 0; j < n; j++) {
				if (map[i][j] == 0) {
					zerocnt++;
				}
				else {
					if (zerocnt != 0) {
						map[i][j - zerocnt] = map[i][j];
						map[i][j] = 0;
					}
				}
			}
		}
	}
	return map;
}


int find_max(vector<vector<int>> map) {
	int maximum = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			maximum = max(maximum, map[i][j]);
		}
	}
	return maximum;
}

void solve(int cnt, vector<vector<int>> &map) {
	if (cnt == 5) {
		result = max(find_max(map), result);
		return;
	}
	for (int i = 0; i < 4; i++) {
		vector<vector<int>> tmp = map; //이동시키기 전의 상태를 저장
		map = move(i, map);
		solve(cnt + 1, map);
		map = tmp;   //이동시키기 전의 상태로 복구
	}
}

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	vector<vector<int>> map;
	vector<vector<int>> tmp;

	cin >> n;

	map.resize(n);
	tmp.resize(n);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int num;
			cin >> num;
			map[i].push_back(num);
		}
	}
	solve(0, map);
	cout << result;
}

개발 환경 : VS2019

질문, 지적 환영합니다!

문제 링크

https://www.acmicpc.net/problem/11657

접근 방법

(1) 음수의 가중치가 존재하는 최단 거리 탐색 문제이므로 벨만-포드 알고리즘을 사용하면 된다.

(2) 문제에서 요구하는 출력

    1. 사이클의 가중치 합이 음수인 경우

    2. 버스가 도착지에 도달할 수 없는 경우

    3. 문제 없이 버스가 도착지에 도착한 경우

(3) (2)에서 요구한 조건을 만족하는 경우

   1. 벨만 포드 알고리즘의 핵심은 3중 for문의 가장 바깥 쪽 for문에서 i == N인 순간 갱신이 일어난다면 말할 것도 없         이 사이클의 가중치 합이 음수인 경우이다.

   2.  dist[j] == INF라면 단 한번도 j번째 지점이 갱신이 일어나지 않았다는 것이다. 즉 j번째 지점에 도착할 수 없다라는         말이 된다. 

   3. 만약 1번 조건에서 걸리게 되면 함수가 return이 되므로 1, 2의 조건에 모두 걸리지 않는다면 버스가 문제 없이

      도착하였다는 뜻이 된다.

(4) 주의할 점

 문제에서 주어지는 변수의 범위는 다음과 같다.

 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. 

 최악의 경우에서 생각해본다면 1번부터 500번 노드까지 거쳐갈 수 있는 최대 노드의 갯수는 499개이고 가중치 C의 최댓값이 10000이므로 499*10000 이므로 INF는 4990000 이상은 잡아줘야 한다.

만약 모든 C가 -10000이면 어떨까? 

for (int i = 1; i <= N; i++) { 
	for (int from = 1; from <= N; from++) {
		for (int j = 0; j < graph[from].size(); j++) {
				//연산 
		}
	}
}

 graph[from].size()가 10 이상 이면 500*500*10*(-10000) = -2,500,000,000 즉 int의 범위를 벗어나 overflow가 발생한다.

그래서 dist는 long long으로 사용해야 적절한 답을 얻을 수 있다.

소스 코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#define INF 0xFFFFFFF

using namespace std;

vector <pair<int, int>> graph[502];
long long dist[502];
int N, M;

void solve() {

	dist[1] = 0;
	bool updated = false;

	for (int i = 1; i <= N; i++) { 
		updated = false;
		for (int from = 1; from <= N; from++) {
			if (dist[from] == INF) 
				continue;
			for (int j = 0; j < graph[from].size(); j++) {
				int to = graph[from][j].first; 
				int cost = graph[from][j].second;
				if (dist[to] > dist[from] + cost) {
					dist[to] = dist[from] + cost;
					updated = true;
				}
			}
		}
		if (i == N) {
			if (updated == true) { // 1.사이클의 가중치 합이 음수인 경우
				cout << -1 << "\n"; 
				return;
			}
		}
	}
	for (int j = 2; j <= N; j++) {
		if (dist[j] == INF)   // 2. 버스가 도달할 수 없는 경우
			cout << -1 << "\n";
		else 		    // 3. 버스가 잘 도착한 경우
			cout << dist[j] << "\n"; 
	}
}

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> N >> M;
	for (int i = 0; i < 502; i++) 
		dist[i] = INF;
	
	for (int i = 0; i < M; i++) {
		int s, e, w;
		cin >> s >> e >> w;
		graph[s].push_back({ e,w });
	}
	solve();
}

개발 환경 : VS2019

질문, 지적 환영합니다!

문제 링크

https://www.acmicpc.net/problem/1786

접근 방법

문자열 검색 알고리즘인 KMP 알고리즘의 구현을 묻는 문제였습니다.

일반적인 문자 Character by Character mapping은 두 문자열의 길이의 곱인 O(NM)만큼 연산을 하게 됩니다.

KMP 알고리즘은 O(N + M)만큼의 시간만에 검색 연산을 해낼 수 있습니다.

KMP 알고리즘은 문자열이 모든 부분 일치하지 않더라도 현재까지 일치했던 영역 내에서의 정보를 최대한 활용합니다.

주로 활용하는 정보는 일치하는 영역 내의 '문자열 내 접두와 접미의 반복'이 있는가? 입니다. 반복이 없으면 일치하는 영역 내에 재검사할 정보가 없기때문에 일치하는 만큼 건너 뛰고, 반복이 있다면 반복하는 영역으로 점프하여 검사하는 것이 기본 아이디어입니다.

아래의 사진을 보면 이해하기 쉽습니다.

KMP 알고리즘은 위와 같이 일치하는 문자열 내에 정보를 최대한 활용함으로써 O(N + M)의 시간복잡도로 문자열 검색을 구현할 수 있습니다.

패턴 문자열 P의 문자열 길이 1 ~ P.length()까지 접두/접미의 길이 k를 미리 계산해놓고 j를 얼마나 이동할지를 결정하는 것이 KMP 알고리즘의 핵심입니다.

ABCABD의 경우,

A, k = 0

AB, k = 0

ABC, k = 0

ABCA, k = 1

ABCAB, k = 2

ABCABD, k = 0 이 되겠습니다.

소스 코드

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
string S, P;

vector<int> get_failure(string p) {
	vector<int> k(p.size(), 0);
	for (int i = 1, j = 0; i < p.size(); ++i) {
		while (j > 0 && p[i] != p[j])
			j = k[j - 1];
		if (p[i] == p[j])
			k[i] = ++j;
	}
	return k;
}

void solve() {
	int cnt = 0;
	vector<int> cd;
	vector<int> k = get_failure(P);
	for (int i = 0, j = 0; i < S.size(); ++i) {
		while (j > 0 && S[i] != P[j])
			j = k[j - 1];
		if (S[i] == P[j]) {
			if (j + 1 == P.size()) {
				++cnt;
				cd.push_back(i - j + 1);
				j = k[j];
			}
			else {
				++j;
			}
		}
	}

	cout << cnt << "\n";
	for (int i = 0; i < cd.size(); ++i) {
		cout << cd[i] << "\n";
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	getline(cin, S); getline(cin, P);
	solve();
	return 0;
}

개발 환경 : Visual Studio 2019

질문, 덧글, 지적 환영합니다.

문제 링크

https://www.acmicpc.net/problem/1949

접근 방법

1. 문제에서 마을은 트리구조로 되어 있다고 얘기하고 있다. 즉 마을의 연결관계를 트리구조로 나타내자.

void dfs(int now, int parent) {
	for (int i = 0; i < adj[now].size(); i++) {
		int there = adj[now][i];
		if (parent != there) {
			tree[now].push_back(there);
			dfs(there, now);
		}
	}
}

DFS를 통해 트리구조를 구현할 수 있다. adj[]는 양 방향으로 인접한 노드에 대한 정보를 담고 있는 벡터이며,

인접한 부분을 탐색을 하되 if (parent != there)라는 조건을 통해 부모 방향으로 접근할 수 없게 자식 방향으로만 탐색하여 트리를 구성하게 된다.

문제에서 제시하는 3가지 조건

1. '우수 마을'로 선정된 마을 주민 수의 총 합을 최대로 해야 한다.  
2. 마을 사이의 충돌을 방지하기 위해서, 만일 두 마을이 인접해 있으면 두 마을을 모두 '우수 마을'로 선정할 수는 없다. 즉 '우수 마을'끼리는 서로 인접해 있을 수 없다.  
3. 선정되지 못한 마을에 경각심을 불러일으키기 위해서, '우수 마을'로 선정되지 못한 마을은 적어도 하나의 '우수 마을'과는 인접해 있어야 한다. 

조건 1을 통해 동적계획법을 사용해야 한다는 사실을 깨달을 수 있다. 동적계획법을 하며 메모를 하기 위한 변수로는 

dp[now][in] (in=0 or in=1)을 사용할 것이며 now는 현재노드 번호, in은 현재 마을이 우수마을로 선정되었다면 1 아니면 0을 의미 한다. 

if (include) { //우수 마을이라면
	int ans = 0;
	for(int i = 0; i < tree[now].size(); i++) {
		int next = tree[now][i];
		ans += solve(next, 0);
	}
	return res = ans + cost[now];
}

solve() 함수 내에서 현재 노드가 우수마을로 선정되었을 경우이다. 2번 조건에 따라 다음 마을은 우수마을이 되면 안되므로 자식노드는 우수마을이 되지 않게 (solve(next, include = 0))진입한다. 또한 우수마을로 선정되었을 경우에는 

cost를 더하게 된다.

else { //include == 0
		int ans = 0;
		for (int i = 0; i < tree[now].size(); i++) {
			int next = tree[now][i];
			int t1 = solve(next, 1);
			int t2 = solve(next, 0);
			ans += max(t1, t2);
		}
		return res = ans;
	}

 이는 현재 노드가 우수마을로 선정되지 않았을 경우이다.

1. 우수마을로 선정되지 않은 경우로 진입을 하게 되는 경우는 이전의 노드가 우수마을이였을 경우가 있다.

2. 우수마을로 선정되지 않은 경우로 진입을 하게 되는 경우는 이전의 노드가 우수마을이 아니였을 경우가 있다.

1의 경우 다음 마을이 우수마을 이던지 아닌지 끝까지 탐색을 해보지 않으면 모른다. 하지만 2의 경우 다음 노드는 무조건 우수마을로 가는것이 이득이기 때문에 max에서 자동으로 우수마을로 가지 않는 값이 걸러질 것이다.

소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <iostream>
#define MAX 10000

using namespace std;

vector <int> adj[MAX + 1];
vector <int> tree[MAX + 1];
int dp[MAX + 1][2];
int cost[MAX + 1];

void dfs(int now, int parent) {
	for (int i = 0; i < adj[now].size(); i++) {
		int there = adj[now][i];
		if (parent != there) {
			tree[now].push_back(there);
			dfs(there, now);
		}
	}
}

int solve(int now, int include) {
	int &res = dp[now][include];
	if (res != -1) 
		return res;
	if (include) { //우수 마을이라면
		int ans = 0;
		for (int i = 0; i < tree[now].size(); i++) {
			int next = tree[now][i];
			ans += solve(next, 0);
		}
		return res = ans + cost[now];
	}
	else {
		int ans = 0;
		for (int i = 0; i < tree[now].size(); i++) {
			int next = tree[now][i];
			int t1 = solve(next, 1);
			int t2 = solve(next, 0);
			ans += max(t1, t2);
		}
		return res = ans;
	}
}

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &cost[i]);
		dp[i][0] = dp[i][1] = -1;
	}
	for (int i = 1; i < n; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	dfs(1, 1);
	int result = max(solve(1, 1), solve(1, 0));
	cout << result;
}

개발 환경 : VS2019

질문, 지적 환영합니다!