Approach 사실상 이 문제와 거의 동일하다. https://viyoung.tistory.com/317 [백준 1012번] [DFS / BFS] 유기농 배추 Approach 연결 요소(Component)의 개수를 묻는 문제이다. 배추가 심어져 있는 곳에 대해서 방문하지 않았다면 DFS / BFS를 돌리고 component의 개수를 1 증가시켜 주면 된다. Code #include #define fastio ios_b.. viyoung.tistory.com 단, 유기농 배추 문제와 달리 이동할 수 있는 노드를 직접적으로 제시하지 않고 이동할 수 없는 노드들을 제시했다는 점에서만 차이가 존재한다. 근본적인 접근 방법은 완전히 동일하다고 할 수 있다. 결과적으로 Component 개수를 물어보는 문제라고 ..

Approach 이 문제와 거의 비슷하다. https://viyoung.tistory.com/317?category=884242 [백준 1012번] [DFS / BFS] 유기농 배추 Approach 연결 요소(Component)의 개수를 묻는 문제이다. 배추가 심어져 있는 곳에 대해서 방문하지 않았다면 DFS / BFS를 돌리고 component의 개수를 1 증가시켜 주면 된다. Code #include #define fastio ios_b.. viyoung.tistory.com 다만. Component 개수를 물어보는 것이 아니라 component안에 속한 원소 개수의 최대값이므로 이를 dfs 반환값을 통해 구해주면 된다. Code #include #define fastio ios_base::sync_..

Approach 다른 Component의 경우 DFS 탐색을 통해 방문할 수 없다는 점을 이용해주면 된다. 모든 정점에 대해서 방문하지 않았으면, dfs를 돌리고 component 개수를 1개씩 올려나가면 원하는 답을 도출시킬 수 있다. component에 대해서는 다음 블로그를 참고하도록 하자. https://m.blog.naver.com/kks227/220785731077 깊이 우선 탐색(Depth-First Search) (수정 2019-08-18) 어후... 강의 꾸준히 쓰기 정말 힘드네요. 이번엔, 원래 3부 전에 썼어야 할 내용인 탐색에 대해 작성할 겁... blog.naver.com Code #include #define fastio ios_base::sync_with_stdio(0), ci..

Approach 1개의 정점을 기준으로 1개의 outstream만 가능하므로, 각 component별로 사이클 1개와 해당 사이클을 구성하고 있는 정점을 지시하는 정점들로 구성되어 있을 수 밖에 없다. 기존에 방문 여부를 판단하기 위해서 visited배열을 이용했다면, 해당 노드를 완전히 방문했는지를 체크하기 위해서 finished 배열을 추가해주면 된다. 자세한 내용은 kks227님의 블로그를 참고해주면 된다. https://m.blog.naver.com/kks227/220785731077 깊이 우선 탐색(Depth-First Search) (수정 2019-08-18) 어후... 강의 꾸준히 쓰기 정말 힘드네요. 이번엔, 원래 3부 전에 썼어야 할 내용인 탐색에 대해 작성할 겁... blog.naver..

Approach 연결 요소(Component)의 개수를 묻는 문제이다. 배추가 심어져 있는 곳에 대해서 방문하지 않았다면 DFS / BFS를 돌리고 component의 개수를 1 증가시켜 주면 된다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; typedef pair pii; int dx[4] = {0, 0, 1, -1}; int dy[4] = {-1, 1, 0, 0}; int m, n; int edge[51][51]; int visited[51][51]; vector node; void dfs(int x_val, int y_val){ visited[x_val][y..

Approach 기본적인 접근 방법은 https://viyoung.tistory.com/315과 동일하다. [백준 1725번] [스택] 히스토그램 Approach 기본적인 접근 방법은 다음 블로그를 참고하면 된다. https://cocoon1787.tistory.com/315 [C/C++] 백준 1725번 - 히스토그램 (스택 풀이) 문제 히스토그램에 대해서 알고 있는가? 히스토그램은 아래와.. viyoung.tistory.com 다만, 이 문제에서 결과값이 20억 이하라는 보장이 없으므로 출력을 long long 자료형을 사용해야한다는 점에서 차이가 있다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)..

Approach 기본적인 접근 방법은 다음 블로그를 참고하면 된다. https://cocoon1787.tistory.com/315 [C/C++] 백준 1725번 - 히스토그램 (스택 풀이) 문제 히스토그램에 대해서 알고 있는가? 히스토그램은 아래와 같은 막대그래프를 말한다. 각 칸의 간격은 일정하고, 높이는 어떤 정수로 주어진다. 위 그림의 경우 높이가 각각 2 1 4 5 1 3 3이다. cocoon1787.tistory.com 이 접근방법을 잘 곱씹어보면, 스택이 점점 쌓여감에 따라서 들어있는 숫자들을 index로 가지는 히스토그램 막대의 높이는 계속 증가하거나 같을 수 밖에 없다. 따라서 pop 연산을 계속 수행하게 되면, 나오는 숫자들은 계속 감소하거나 같을 수 밖에 없다. 위 블로그에 나온 예시에..

Approach 완전 탐색으로 이 문제를 처리한다고 하면 비둘기집의 원리에 따라서 중복되는 연산이 매우 많다는 사실을 쉽게 캐치할 수 있다. dp[i] = i번째 수부터 시작하는 LIS 중 합이 가장 큰 값 dp[i] = max(v[i], max{dp[i + j] + v[i]}) for all j s.t v[i] < v[j] Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; vector v; int n; int dp[1001]; int memoi(int k){ int& ret = dp[k]; if(ret != -1) return ret; int cmp = v[k]; fo..