티끌 모아 태산

1. 한정 조건을 가진 문제를 풀려는 전략

 - 해를 찾기 위해, 해의 후보를 전짐적으로 확인하여, 해당 후보가 제약 조건을 만족할 수 없다고 판단한 경우 backtrack하여, 다음 후보로 넘어가 최적의 해를 찾는 전략

2. backtrack

- 제약 조건을 만족할 수 없다고 판단한 후보에 대하여 다음 단계에서 다시 확인하지 않도록 표기하는 방법

3. 모든 경우의 수

- 각 후보의 모든 경우의 수를 상태공간트리를 통해 표현하고 각 후보를 DFS 방식으로 확인한다.

4. Promising

- 확인 단계에서 해당 루트가 조건에 맞는지를 검사하는 기법

5. Pruning

- 조건에 맞지 않는 루트를 포기하고 다른 루트로 방향을 옮겨 탐색 시간을 절약하는 기법

백트래킹의 과정

1. 문제 상황을 상태 공간 트리로 표현한다.

2. 루트 부터 DFS를 하여 불필요한 탐색을 하지 않고 한정 함수를 만족하는 (x[1], x[2], ..., x[n])를 찾는다.

3. 각 노드 s 에 도착할 때마다 루트에서 s까지의 경로 예를 들어 k번째 선택에선 (x[1], x[2], ..., x[k])의 튜플이 한정함수를 만족하는지 판단한다.
4-1.  (x[1], x[2], ..., x[k])의 튜플이 한정 함수를 만족한다면 x[k] 노드를 live node이자 e-node로 변경한다.
4-2. 한정함수를 만족하지 않는 다면 T(x[1], ... x[k])의 노드들을 더이상 확장하지 않으며 dead node로 만든다.
5.  k < n일때 x[k]의 자식 노드들인 x[k+1] 들 즉, T(x[1], ... x[k])을 탐색한다.
6. 모든 자식 노드를 탐색했다면 현재 노드를 dead node로 변경한다.
7. 진행 도중 한정함수를 만족하는 (x[1], x[2], ..., x[n])에 도달하면 정답을 출력한다.
8. 정답이 도출되었거나 모든 노드가 dead 노드가 되었다면 탐색을 종료한다. 이때 정답이 여러개 인 경우에 모든 정답을 찾고 싶다면 모든 노드가 dead 노드가 될때까지 탐색해야 한다.

DFS는 그래프를 탐색하는 방식 중에 하나이다. 

1. 그래프

노드(node)와 그 노드를 연결하는 간선(edge)을 하나로 모아 놓은 비선형 자료 구조

그래프 : G = (V,E) 이고, V,E는 다음과 같다.

V(G) : 정점(set of vertices)

E(G) : 간선(set of edges), 정점을 연결하는 선, V X V의 부분집합

• 그래프는 node(혹은 vertice)와 edge(혹은 arcs)로 구성되어 있으며 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조로 네트워크 모델이다.
• 간선이 방향을 갖는지 여부에 따라 무방향 그래프와 방향 그래프로 구분한다.
• 인접 리스트/인접 행렬 두 가지 방식으로 그래프를 구현할 수 있다.

2. 그래프 탐색

- 그래프의 각 정점을 방문하는 것을 탐색(traversal)이라고 한다.

- 그래프에 관한 연산 중 가장 중요한 것이다.

- 탐색에서 노드의 방문 순서에 따라 다음과 같은 방법이 있다.

• 깊이우선탐색 – DFS (Depth First Search) – 갈수있는데 까지 가보는 방문 방법 -트리의 전위탐색 방법을 그래프에 적용한 것이다. (preorder tree traversal)

• 너비우선탐색 – BFS (Breath First Search) – 거리가 가까운 곳부터 가보는 방문 방법 - 트리의 레벨우선탐색을 그래프에 적용한 것이다. (level order tree traversal)

3. 깊이 우선 탐색

방법 : 자동차로 여행할 경우 방문지가 있으면 무조건 방문하는 방법이다. 즉 후진하지 않고 가는 방법이며 후진하는 경우는 길이 막히거나, 이미 방문했던 곳일 경우이다. 후진하여 방문할 곳은 마지막에 갈수 있었던 곳 중 가지 않았던 길이다. 이 방법을 깊이 우선 탐색이라고 하며 탐색 중 방문 가능한 곳은 스택 자료를 이용하여 저장해 둔다.

1단계 : 하나의 노드를 택한다.

2단계 : 노드를 방문하여 필요한 작업을 한 다음 연결된 다음 노드를 찾는다. 현재 방문 노드는 스택에 저장한다. 2단계를 반복하면서 방문을 계속한다. 막히면 3단계로 간다.

3단계 : 더 이상 방문할 노드가 없으면 스택에서 노드를 빼내 다음 방문 노드를 찾아 2)번 과정을 다시 반복한다.

-깊이 우선 탐색 알고리즘

/* 정점 v에서 시작하여 그래프의 깊이 우선 방문 */
void dfs(int v) {
		node_ptr w;
		visited[v] = TRUE; /* 1 방문지 표시 */
		printf(“%5d”, v);
		for(w = graph[v]; w; w = w->link) /* 2 연결리스트 탐색 */
			if(!visited[w->vertex])
				dfs(w->vertex);
}

4. 깊이 우선 탐색의 시간 복잡도

- DFS는 그래프(정점의 수 : N, 간선의 수: E)의 모든 간선을 조회함

* 인접 리스트로 표현된 그래프 : O(N+E)

* 인접 행렬로 표현된 그래프 : O(N^2)

이진 탐색 알고리즘이란?

위 그림과 같이 정렬되어 있는 리스트 내에서 특정한 값을 찾을 때 중간의 값을 정하고 그 값을 기준으로 찾는 값에 맞는 범위에서 다시 반복한다.

알고리즘 

int BinarySearch(int key, int arr[])
{
	int left, right = arr.length() - 1, mid;
	while (left <= right) {
		mid = (left + right) / 2;
		if (iKey == arr[mid])
			break;
		if (iKey < arr[mid])
			right = mid - 1;
		else
			left = mid + 1;
	}
}

시간복잡도

www.acmicpc.net/problem/10844

2차원 배열 dp[x][y]에 sol[x][y]의 결과를 저장하고

이미 방문하여 계산을 마친 [x,y] 는 사전에 저장해놓은 dp[x][y]를 사용하여 계산해 반복 계산을 줄인다.

계단 수의 경우의 수는 한칸 아래 혹은 한칸 위 뿐이므로 가장 작은 수 0과 가장 큰 수 9를 예외로 두고

if (x == 0)
dp[x][y] += sol(x + 1, y + 1);
else if (x == 9)
dp[x][y] += sol(x - 1, y + 1);
else {
dp[x][y] += sol(x - 1, y + 1);
dp[x][y] += sol(x + 1, y + 1);
}

다음과 같은 형식으로 재귀 형태로 구성하며

if (y == n - 1) {
dp[x][y] = 1;
return dp[x][y];
}

가장 높은 자릿수에서는 더이상 반복하지 않고 1 을 return 한다.

코드

#include<iostream>
#define MAX 101
#define N 10

using namespace std;
long long dp[N][MAX] = { 0 };
int n;

long long sol(int x, int y) {
	//이미 방문한 경우
	if (dp[x][y] != 0)
		return dp[x][y];
	//기저
	if (y == n - 1) {
		dp[x][y] = 1;
		return dp[x][y];
	}

	if (x == 0)
		dp[x][y] += sol(x + 1, y + 1);
	else if (x == 9)
		dp[x][y] += sol(x - 1, y + 1);
	else {
		dp[x][y] += sol(x - 1, y + 1);
		dp[x][y] += sol(x + 1, y + 1);
	}

	return dp[x][y] % 1000000000;
}


int main() {
	cin >> n;
	long long sum = 0;
	for (int i = 1; i < 10; i++)
		sum += sol(i, 0);

	cout << sum % 1000000000 << endl;
	return 0;
}

결과

www.acmicpc.net/problem/10942

칠판에 적혀 있는 숫자들을 arr 에 저장하고 2차원 배열 dp 를 통해 ( dp[s][e]  ( 질문이 S E 일 때의 결과) ) 결과들을 저장하여 이미 계산이 이뤄진 경우의 수를 반복 계산하지 않도록 한다.

펠린드롬을 검사할 때에는 첫번째 index와 마지막 index부터 하나씩 더하고, 빼면서 비교하여 체크한다.

코드

#include <iostream>
#include <string.h>

using namespace std;

int N;
int arr[2001];
int M;

int dp[2001][2001];

bool sol(int s, int e) {

	//이미 확인한 경우
	if (dp[s][e] != -1)
		return dp[s][e];

	//펠린드롬인지 검사
	bool answer = 1;
	for (int i = 0; i <= (e - s) / 2; i++)
	{
		if (arr[s + i-1] != arr[e - i-1]) {
			dp[s][e] = 0;
			answer = 0;
			break;
		}
	}
	dp[s][e] = answer;
	return answer;
}

int main() {

	ios::sync_with_stdio(false);
	cin.tie(0);

	for (int i = 0; i < 2001; i++) 
		memset(dp[i], -1, sizeof(int) * 2001);

	cin>>N;
	for (int i = 0; i < N; i++)
		cin>>arr[i];
	cin >> M;

	bool ans[1000000];

	int S, E;
	for (int i = 0; i < M; i++)
	{
		cin >> S >> E;
		ans[i] = sol(S, E);
	}

	for (int i = 0; i < M; i++)
	{
		cout<<ans[i]<<"\n";
	}

	return 0;
}

결과

동적 계획법 이란?

1. 조건

▶ 최적 부분 구조 : 기본 문제의 최적해가 부분 문제의 최적해를 포함하고 있는 구조 , 즉 전체 문제의 최적해가 부분 문제의 최적해들로써 구성이 되어있다는 것이다. 예를 들어 A 문제의 부분문제 a, b 가 있을 때 , a, b의 최적해가 a' , b' 라면 A의 최적해가 a' 와 b'로 구성되는 것을 증명한다면 이는 최적부분 구조를 가진다고 할 수 있다.

▶ 부분 문제 반복 : 재귀 알고리즘을 통해 문제를 해결할 때 같은 부분 문제를 계속 반복하여 해결해야 하는 경우 이를 부분 문제 반복 구조를 가진다 할 수 있다.

2. 방식

하나의 문제를 여러개의 하위 문제로 나누어 푼 다음 , 그것을 결합하여 최족적인 목적에 도달한다. 각 하위 문제에 대한 결과를 계산하여 , 이 결과들을 저장하고 같은 문제가 나왔을 경우 저장된 결과를 사용하여 해결한다. 이러한 방법을 통해 계산 횟수를 줄일 수 있다.

분할 정복(divide and conquer) 또한 큰 문제를 작은 문제로 나누어 해결하지만 동적 계획법은 작은 부분문제들이 반복되는 것을 이용하여 문제를 푸는 것이고 분할 정복은 작은 문제 내에서 반복이 일어나는 부분이 없다.

3. 이용

최단 경로 문제, 행렬의 제곱 문제 등의 최적화에 사용한다.

동적 계획법은 문제를 해결하기 위한 모든 방법을 검토하고, 그 중 최적의 풀이법을 찾아낼 수 있다.

문제에 대한 모든 방법을 충분히 빠른 속도로 처리할 수 있는 경우 최적의 해법이다.

4. memorization

memorizaion을 사용하면 이미 한번 결과를 계산한 부분 문제에 대해서는 반복하여 계산하지 않는다.

위 피보나치 수열을 예로 들면 이미 계산한 f2->f1 과 f3->f2,f1 은 저장되어 있는 결과를 사용한다.

그렇기 때문에 전체 문제에 대한 총 계산횟수를 줄여주며 동적프로그래밍의 시간복잡도를 줄일 수 있다.

5. 관련문제

포도주 시식 [2156]https://www.acmicpc.net/problem/2156

쉬운 계단 수 [10844] https://www.acmicpc.net/problem/10844

팰린드롬 [10942] https://www.acmicpc.net/problem/10942

외판원 순회 [2098] https://www.acmicpc.net/problem/2098

몽고DB란?

몽고 DB 는 위키백과에 다음과 같이 설명되어 있다.

이러한 몽고DB를 node.js에서 사용하기 위해서는 moongoose라는 ODM을 사용해야 한다. ODM은 Object Cocument Mapping으로 문서를 DB에서 조회할 때 자바스크립트 객체로 바꿔주는 역할을 한다. 

mongo DB와 이전에 Express.js로 제작한 간단한 웹 애플리케이션과 연결하는 과정은 다음과 같다.

1. 몽고 DB 회원가입

www.mongodb.com/

2. Cluster 생성

3. 몽고 DB 유저 생성

4. MongGoose 다운로드

npm install mongoose --save

5. index.js 파일 추가

-> index.js

const express = require('express')
const app = express()
const port = 5000
const mongoose = require('mongoose')
mongoose.connect('MongoDB URL',{
	useNewUrlParser: true, 
    useUnifiedTopology: true,
    useCreateIndex: true, 
    useFindAndModify:false
}).then(() => console.log('MongoDB Connected...')).catch(err => console.log(err))
app.get('/', (req, res) => {
  res.send('Hello World!')
})
app.listen(port, () => {
  console.log(`Example app listening at http://localhost:${port}`)
})

- 코드 설명

'mongodb+srv://<username>:<password>@boilerplate.16rla.mongodb.net/<dbname>?retryWrites=true&w=majority'

<username> : 이전에 생성한 몽고DB 유저 ID

<password> : 이전에 생성한 몽고DB 유저 비밀번호

<mongodb> : 생성한 몽고DB 이름

*.then(()=>console.log('MongoDB Connected...')) : 연결확인 여부를 위한 console에 띄우는 로그

* .catch(err => conseole.log(err)) : 연결이 되지 않은 경우에는 err를 log로 띄움

* 에러방지를 위한 코드

useNewUrlParser: true,

useUnifiedTopology: true,

useCreateIndex: true,

useFindAndModify: false

6. 실행

npm run start

www.acmicpc.net/problem/2104

분할 정복을 통해 해결

1. mid 를 중심으로 왼쪽 부분배열의 최대값

2. mid 를 중심으로 오른쪽 부분배열의 최대값

3. mid를 포함한 부분배열의 최대값

중 가장 큰 값을 출력

#include <iostream>
#include <algorithm>

using namespace std;

const int MAX = 1000001;

int N;
int A[MAX];

long long GetMax(int from, int to)
{
	if (from == to) return (long long)A[from] * A[from];

	int mid = (from + to) / 2;
	//1. 왼쪽 부분배열의 최대값
	long long leftSum = GetMax(from, mid);
	//2. 오른쪽 부분배열의 최대값
	long long rightSum = GetMax(mid + 1, to);

	//1+2.왼쪽, 오른쪽 부분배열의 최대값
	long long maxValue = max(leftSum, rightSum);

	
	int left = mid;
	int right = mid + 1;

	long long sum = A[left] + A[right];
	long long minValue = min(A[left], A[right]);
	// 최대 값 비교

	maxValue = max(maxValue, sum * minValue);

	//3. mid를 포함한 부분배열의 최대값
	while (left > from || right < to)
	{
		//값이 더 큰 방향으로 이동하면서 최대값을 찾음
		if (right < to && (left == from || A[left - 1] < A[right + 1]))
		{
			sum += A[++right];
			minValue = min(minValue, (long long)A[right]);
		}
		else    
		{
			sum += A[--left];
			minValue = min(minValue, (long long)A[left]);
		}
		long long crossSum = sum * minValue;
		// 한 칸씩 이동하면서 구한 최대값과 현재최대값 비교 후 저장
		maxValue = max(maxValue, crossSum);
	}

	//1+2+3 . 세 가지 경우 중 최대값을 구하여 저장
	return maxValue;
}

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	cin >> N;
	for (int i = 1; i <= N; i++) cin >> A[i];

	cout << GetMax(1, N);

	return 0;
}