얘는 살짝 만 생각하면 답이나오는 문제 였다. 문제 푸는 방법이 퍼뜩퍼뜩 났으면 좋겠는데 아직 수련이 부족해서 시간이 오래 걸린다.
이 문제는 간단하다 내이전에 나온 최댓값과 나를 더한값과 나 혼자 값중에 더큰애를 선택해주면 되는 문제였다.
그 이유는 어찌됬든 더하는 수가 양수라면 값은 증가하기 때문이다
10
10 -4 3 1 5 6 -35 12 21 -1
즉 이런식으로 입력이 주어지면
dp[1]은 -4와 6중에 선택한다
dp[2]는 3과 9중에 선택한다
dp[3]은 10과 1중에 선택한다
10
6
9
10
15
21
-14
12
33
32
이런식으로 dp값이 바뀐다 즉 점화식은
max(dp[i-1]+arr[i],arr[i])값이 된다
#include <iostream>
using namespace std;
int arr[100000];
int dp[100000];
int max(int x,int y) {
return x > y ? x:y;
}
int main() {
int inputnum;
int maxnum;
cin >> inputnum;
for (int i = 0; i < inputnum; i++) {
cin >> arr[i];
}
dp[0]=arr[0];
maxnum = dp[0];
for (int i = 1; i < inputnum; i++) {
dp[i] = max(dp[i - 1] + arr[i], arr[i]);
}
for (int i = 0; i < inputnum; i++) {
if (dp[i] > maxnum) {
maxnum = dp[i];
}
}
cout << maxnum;
}
이 코드가 자기자신과 인접한 4방향중 아직 방문하지 않은 곳으로 가서 자기 자식임을 표시한다 표시방법은 나의 단계에서 1을 더해주는 방식으로 작성 하였다 또한 나의 자식들도 큐의 삽입함으로서 계속해서 자손들을 확인한다.
즉 극단적인 위의 표로 봤을때 큐의 값은 (0,0)->(0,1)(1,1)(1,0)->(0,2)(2,1)(2,2)(1,2)(0,0)->..... 이런식으로 큐의 값이 변화하게 된다. 그후 맨마지막에 도착지점이 몇번째인지 마크되어있을테니 이것을 그대로 출력해주면 된다.
DFS
DFS방식으로는 이문제를 풀 수 없다 백트래킹을 사용하지 않고서는 DFS는 도착지점에 도착하는 순간 끝나기 때문에 백트래킹을 사용하여 이전지점으로가 다른 루트를 찾아가는 방법을 사용하지만 이문제에서는 시간초과를 발생시킨다. 이에
DFS방식으로 푸는것을 추천하지 않는다
#include <iostream>
#include <utility>
#include <stack>
using namespace std;
char maze[101][101] = { '0',};
bool visited[100][100] = { false, };
int N = 0, M = 0;
int minnum = 10001;
stack<pair<int, int>> visitedvertex;
void dfs(int startx, int starty) {
visited[startx][starty] = true;
visitedvertex.push({ startx,starty });
if (startx == N-1 && starty == M - 1) {
if (visitedvertex.size() < minnum) {
minnum = visitedvertex.size();
}
}
else{
if (maze[startx][starty + 1] == '1' && visited[startx][starty + 1] == false) {
starty += 1;
dfs(startx, starty);
starty -= 1;
}
if (maze[startx + 1][starty] == '1' && visited[startx + 1][starty] == false) {
startx += 1;
dfs(startx, starty);
startx -= 1;
}
if (maze[startx - 1][starty] == '1' && visited[startx - 1][starty] == false) {
startx -= 1;
dfs(startx, starty);
startx += 1;
}
if (maze[startx][starty - 1] == '1' && visited[startx][starty - 1] == false) {
starty -= 1;
dfs(startx, starty);
starty += 1;
}
}
visited[startx][starty] = false;
visitedvertex.pop();
}
int main() {
int startx = 0, starty = 0;
cin >> N >> M;
for (int i = 0; i < N; i ++) {
cin >> maze[i];
}
dfs(0, 0);
cout << minnum;
DFS방식은 재귀를 사용하여야 한다 이에 재귀를 사용하면서 스택을 섞어서 사용하였다 자신이 방문할때 스택에다가 값을 쌓아올린다. 이후 도착점에 도착했을 때 도착한 최솟값과 비교하여 작은값을 저장하여 DFS로 갈 수 있는 방법중 최솟값을 출력하는게 내가 한방법이다 DFS는 일단 불러지는 순간 자기자신을 스택에 쌓는다 그후 자신의 4방향을 탐색하여 방문한적이 없으면 쌓는다 하지만 방문할곳이 없으면 다시 스택에서 나온다 이것을 반복하여 방문한곳을 방문하지 않고 끝점 까지 도달하는 경우의 수들중 최소의 점만을 거쳐서 도착하는 값을 출력한다
이문제의 경우 깊이 우선 탐색(DFS) 너비 우선 탐색(BFS)의 차이를 알기에는 딱인 문제 였다.
일단 BFS의 경우 재귀함수를 사용하지 않고 풀어 보았다
현재 이렇게 입력값을 주었을 경우 BFS는 기준점을 기준으로 선 1개를 통해 연결 된 애들 선 2개를 통해 연결된 애들
이런식으로 단계를 나눠준다
이렇게 생각을 하거나 아니면
DFS의 경우에는 또 다르게 생각해주어야한다 비슷하게 생각해보자면 최대한 길게 선을 그어서 모든 정점을 방문하는 방법이라고 생각한다 단 다시 되돌아가기는 내가 왔던 점으로만 돌아 갈수 있다 또한 만약에 이때 다른 경로가 아직 방문되지 않았고 내가 간적 없는 정점이라면 그곳으로 간다. 즉 최대한 길게 갈려고 한다고 생각하면 된다.
다르게 생각하면 부모를 기준으로 내 첫째 자식의 후손들 까지 갔다가 2째 자식의 후손들 까지 쭉보고 나머지 자식들 순으로 그 자식들의 후손들까지 쭉 보는거라고 생각하면된다
이런식으로 기준점을 1로 두고 1과 선 한개로 연결된 애들과 선을 2개로 해서 갈수 있는 애들을 나눠서 생각해줄수 있다
단 밑에 그림처럼 생각할시에는 2번째 단계에서 이미 4를 방문했으므로 3단계에 있는 4에는 방문을 할 필요가 없다고 생각해주면 된다.
일단 전체 코드를 첨부후 부분 부분 설명하도록 하겠다.
#include <iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<memory.h>
using namespace std;
vector <int> vertex[10002];
vector <int> resultofDfs;
vector <int> resultofBfs;
int vertexnum;
bool visited[1001] = { false, };
//dfs 함수
void dfs(int start) {
resultofDfs.push_back(start);
visited[start] = 1;
for (int i = 0; i < vertex[start].size(); i++) {
if (visited[vertex[start][i]] == true){
continue;
}
dfs(vertex[start][i]);
}
}
int main() {
queue<int> Bfsqueue;
int edgenum;
int startvertex;
int startvertexforDfs;
int inputvertex;
int inputedge;
cin >> vertexnum;
cin >> edgenum;
cin >> startvertex;
startvertexforDfs = startvertex;
resultofBfs.push_back(startvertex);
for (int i = 0; i < edgenum; i++) {
cin >> inputvertex >> inputedge;
vertex[inputvertex].push_back(inputedge);
vertex[inputedge].push_back(inputvertex);
}
//작은것부터 나와야하니까 정렬해준다
for (int i = 1; i <= edgenum; i++) {
sort(vertex[i].begin(), vertex[i].end());
}
//DFS
dfs(startvertexforDfs);
for (int i = 0; i < resultofDfs.size(); i++) {
cout << resultofDfs[i] << ' ';
}
cout << endl;
// 배열 재사용 위해 초기화
memset(visited, 0, sizeof(visited));
//BFS
visited[startvertex] = true;
for (int i = 0; i < vertexnum; i++) {
int sizeofvertex = vertex[startvertex].size();
for (int j = 0; j < sizeofvertex; j++) {
if (visited[vertex[startvertex][j]] == false) {
visited[vertex[startvertex][j]] = true;
Bfsqueue.push(vertex[startvertex][j]);
resultofBfs.push_back(vertex[startvertex][j]);
}
}
if (Bfsqueue.empty()) {
break;
}
startvertex = Bfsqueue.front();
Bfsqueue.pop();
}
for (int i = 0; i < resultofBfs.size(); i++) {
cout << resultofBfs[i] << ' ';
}
}
맨처음 각각의 정점들이 누구랑 연결되어 있는지를 vector형태로 넣어 줄 수 있도록 만들어 주었다
만약
이런 식으로 입력받아지면
vector[1] 에 2,3,4
vecotr[2] 에 1,4
vector[3] 에 1,4
가 들어가게 된다 즉 내가 다른 누군가와 연결되었는지를 입력해주게 된다
그다음 각 정점이 방문되었는지를 확인해주는 visited 배열을 만들어 주었다
void dfs(int start) {
resultofDfs.push_back(start);
visited[start] = 1;
for (int i = 0; i < vertex[start].size(); i++) {
if (visited[vertex[start][i]] == true){
continue;
}
dfs(vertex[start][i]);
}
}
이 부분의 경우
일단 내가 들어온 곳을 방문 했다고 마크 한다
그후 for문 첫번째 조건에서 내가 아무하고 도 연결안되어있으면 for문을 돌지 않는다 그래서 더이상 가지않고 함수를
return하고 재귀적으로 call하기 이전의 함수가 다시 경로를 찾는다.
혹은 내가 만약에 방문할 수 있는 경로가 있더라도 그곳이 방문됬었다면 방문하지 않고 다른 경로를 찾는다.
BFS의 코드는 재귀가 아니라 반복문으로 작성하였다.
visited[startvertex] = true;
for (int i = 0; i < vertexnum; i++) {
int sizeofvertex = vertex[startvertex].size();
for (int j = 0; j < sizeofvertex; j++) {
if (visited[vertex[startvertex][j]] == false) {
visited[vertex[startvertex][j]] = true;
Bfsqueue.push(vertex[startvertex][j]);
resultofBfs.push_back(vertex[startvertex][j]);
}
}
if (Bfsqueue.empty()) {
break;
}
startvertex = Bfsqueue.front();
Bfsqueue.pop();
}
이 부분의 경우 일단 시작점은 무조건 방문한거니 true로 마크해준다
그 이후에 나랑 연결된 애들중에 방문되지 않은애들을 큐에다가 넣어 준다 resultofBFS 는 큐는 pop을 이용해서 정보를 빼고 더하기 때문에 vector에다가 방문하는 지점을 저장해주기 위해 만들어 놓은것이다 큐에 있는 것들을 pop해주면서 pop되는 애들의 자식들도 queue에다가 넣어준다 이것을 반복해서 같은대의 자식들이 계속 큐에 넣어져서 접근한다 이후에 큐가 비게되면 모두 방문한거가 된다 순서를 보자면
5 5 3
5 4
5 2
1 2
3 4
3 1
처음 큐 3-> 1,4->2-5이런식으로 root로 부터 몇개의 선으로 갈수 있는지에 따라 level이 나누어 진다
이렇게 수열이 있으면 처음 이렇게 만 있을 때 증가하는 수열들은 각각 하나 씩이라고 생각하자
그 후에 내 이전의 원소들을 보면서 비교한다 내 이전의 원소가 나보다 작으면
나의 수에 내 이전 원소 까지의 증가수를 합쳐준다
예시로
20이 10을 만나게 되면 10은 하나짜리 증가 수열이고 20은 10보다 크니
10 20은 증가수열이다 이에 서로까지의 증가 수열 수를 더해준다 이에 20은
2의 증가 수열을 갖는다
하지만 이 때 내 이전 원소가 나보다 작을 수 있는 경우의 수가 여러 개이므로
내 이전까지의 증가수열 수 + 1 끼리를 비교하여 가장 큰값을 내가 갖고 있어야 한다
이에 dp[i]=max(dp[i],dp[j]+1) 이 필요하다
이에 자기자신의 값과 내 이전의 증가수열이 나를 만났을 때의 개수 와 비교해 준다
이렇게 점점 자기자신보다 작은애까지의 증가수열 + 나의 값이 최대가 되는 것을 구하는게
핵심이다
#include <iostream>
using namespace std;
int max(int x, int y)
{
return x > y ? x : y;
}
int main() {
int arr[1001];
int dp[1001]; //자신 까지의 증가 수열 수
int maxnum=0;
int inputn;
cin >> inputn;
for (int i = 0; i < inputn; i++) {
cin >> arr[i];
dp[i] = 1;
}
for (int i = 1; i < inputn; i++) {
for (int j = 0; j <= i; j++) {
if (arr[i] > arr[j]) {
dp[i] = max(dp[i], dp[j]+1);
}
}
}
for (int i = 0; i < inputn; i++) {
if (dp[i] > maxnum)
maxnum = dp[i];
}
cout << maxnum;
}
