🧐 최장 증가 부분 수열 (LIS)란? 최장 증가 부분 수열, Longest Increasing Subseqeunce는 어떠한 수열의 부분 수열중 오름차순으로 증가하는 가장 긴 수열을 의미한다. (이때 각 원소는 연속할 필요는 없다.) 아래의 예시 수열을 보자. [ 7, 3, 5, 2, 7, 4, 8, 2] 이 수열에서 증가하는 순열에는 [2, 4], [2, 4, 8], [3, 5] 등 다양한 것이 있지만 LIS는 [3, 5, 7, 8]이 된다. 📝 LIS를 구해보자 LIS를 구하는 방법에는 동적 계획법(DP)와 이분탐색으로 크게 두가지의 방법이 있다. DP는 $O(n^2)$의 시간복잡도를 보이며, 이분탐색으로 구현하게 되면 $O(n\log{n})$의 시간복잡도가 나타난다. 1) 동적 계획법 (Dynam..
전형적인 DP 문제로, 점화식만 이끌어 낸다면 쉽게 풀 수 있다.n번째에서의 경우의 수를 계산한다 하자n-1에서 n으로 가는 경우의 수는 한가지다.n-2에서 n으로 가는 경우는 n-2+1+1, n-2+2로 2가지다. 이때 n-2+1+1은 n-1에서 n으로 갈 떄 세준 케이스 이므로 n-2+2 의 한가지 경우만 센다.마찬가지로 n-3에서 n으로 가는 경우의 수도 한가지이다.즉, 다음과 같이 식을 세울 수 있다. DP[n]=func(n-1)+func(n-2)+func(n-3) 스스로 코드를 짠 후 아래를 눌러 읽어보자.더보기#include using namespace std;int DP[11];int func(int n) { if(DP[n]) return DP[n]; if(n==1) return ..
DP를 사용하여 가능한 최수 경우의 수를 Bottom-Up 방식으로 구해준다.#include using namespace std;int main() { int N, DP[1000001]; cin >> N; DP[1]=0; for(int i=2; i
문제 a. 문제 양팔 저울과 몇 개의 추가 주어졌을 때, 이를 이용하여 입력으로 주어진 구슬의 무게를 확인할 수 있는지를 결정하려고 한다. 무게가 각각 1g과 4g인 두 개의 추가 있을 경우, 주어진 구슬과 1g 추 하나를 양팔 저울의 양쪽에 각각 올려놓아 수평을 이루면 구슬의 무게는 1g이다. 또 다른 구슬이 4g인지를 확인하려면 1g 추 대신 4g 추를 올려놓으면 된다. 구슬이 3g인 경우 아래 과 같이 구슬과 추를 올려놓으면 양팔 저울이 수평을 이루게 된다. 따라서 각각 1g과 4g인 추가 하나씩 있을 경우 주어진 구슬이 3g인지도 확인해 볼 수 있다. 와 같은 방법을 사용하면 구슬이 5g인지도 확인할 수 있다. 구슬이 2g이면 주어진 추를 가지고는 확인할 수 없다. 추들의 무게와 확인할 구슬들의 ..
동적 계획법(Dynamic Programming, DP)은 알고리즘이라기 보다는 하나의 기술이다. 분할 정복에서 사용하는 기법으로, 큰 문제들을 작은 문제들로 쪼개서 그 답을 저장하고 재활용한다. 쉽게 말하자면 '기억하며 풀기' 라고 할 수 있다. 왜 DP를 사용하는가? 다음과 같은 함수를 계산한다고 해보자. $f(a, b) = f(a-1, b)+f(a, b-1)\space(a, b\ge 1)$ $f(0, n)=f(n, 0)=1$ 이떄 f(2, 2)를 계산한다고 하면 다음과 같은 계산 과정를 거치게 된다. 위 에서는 총 5번의 연산을 수행하는데, 이때 f(1, 1)에 대한 연산을 2번 수행하고 있으므로 이를 미리 연산한다고 가정하면 f(2, 2)를 구하기 위해 4번의 연산만 수행하면 된다. 만약 a, b..
7576번 토마토 문제에 세로축만 추가된 것으로 마찬가지로 BFS를 사용하면 된다. 풀이는 이전 글을 참고하자. #include #include #include using namespace std; int M, N, H, a[100][100][100]={}; queue q; int dh[6]={-1, 1, 0, 0, 0, 0}; int dn[6]={0, 0, -1, 1, 0, 0}; int dm[6]={0, 0, 0, 0, -1, 1}; bool isDone() { for(int i=0; i H; for(int i=0; i
문제 a. 문제 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다. 어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며 배열의 각 원소는 해당 지점의 높이를 표시하는 자연수이다. 예를 들어, 다음은 N=5인 지역의 높이 정보이다. 이제 위와 같은 지역에 많은 비가 내려서 높이가 4 이하인 모든 지점이 물에 잠겼다고 하자. 이 경우에 물에 잠기는 지점을..
두 노드간의 거리를 계산하는 문제이므로 BFS를 사용하는 것이 더 적합하나, DFS로도 풀어 보았다. BFS 풀이 #include #include #include #include using namespace std; int N, M, A, B; vector a[101]; bool visited[101]={false, }; void BFS() { queue q; q.push({A, 0}); int now = A; int len = 0; visited[A]=true; while(!q.empty()) { now = q.front().first; len = q.front().second; if(now==B) { cout > A >> B; cin >> M; for(int i=0; i> x >> y; a[x].pu..
'적어도 몇 번' 이란 말과 탐색 문제란 점에서 BFS를 사용해야함을 알 수 있다. #include #include using namespace std; int F, S, G, U, D; int d[1000001]={}; void BFS() { queue q; q.push(S); d[S]=1; while(!q.empty() && q.front()!=G) { int now = q.front(); q.pop(); if(now+U0 && d[now-D]==0){ q.push(now-D); d[now-D]=d[now]+1; } } if(!q.empty()) cout F >> S >> G >> U >> D; BFS(); }
'가장 빠른 시간' 이란 말에서 BFS를 사용하는 문제임을 알 수 있다. #include #include using namespace std; int N, K; int d[100001]; int cnt; void BFS() { queue q; q.push(N); d[N]=1; while(!q.empty() || q.front()==K){ int now=q.front(); q.pop(); if(now-1>=0 && d[now-1]==0){ q.push(now-1); d[now-1]=d[now]+1; } if(now+1> K; BFS(); }
