본문 바로가기

백준61

최장 증가 부분 수열 찾기 | 역추적 (Longest Increasing Subsequence Tracking) 2020/06/25 - [알고리즘] - 최장 증가 부분수열: LIS (Longest Increasing Sub-sequence) 지난 포스팅에서 LIS로 찾은 결과는 부분 수열의 최장 길이에 대한 정보만을 가지고 있을 뿐, 그 자체가 부분 수열이 될 수 없다는 점을 강조했다. LIS 역추적을 위해 pair 자료형 배열을 만들고 다음과 같이 정의하였다. pair LIS[MAX_SIZE] // first = 값, second = 인덱스 그리고 매번 arr배열을 탐색하면서 2가지 규칙으로 i번째 인덱스 앞에 올 인덱스 j (j LIS[_size-1].first) { lastidx = i; pre[i] = LIS[_size - 1].second; LIS[_size++] = { arr[i],i }; continu.. 2020. 6. 26.
최장 증가 부분수열: LIS (Longest Increasing Sub-sequence) LIS 길이는 꽤 단순하게 구할 수 있다. 10 20 10 30 20 50의 전체 수열이 있다면 먼저 10을 벡터에 넣는다 10 그 다음 수를 벡터의 마지막 수와 비교하여 1) 마지막 수보다 크다면 그대로 벡터에 삽입 10 20 2) 마지막 수보다 작거나 같다면 벡터에 있는 요소들 중 다음 수보다 크거나 같은 가장 작은 정수를 찾아 바꿔주면 된다. 10 20 (세번째 10과 첫번째 원래 들어있던 10을 바꾼것이다) 이 수를 찾을 때 lower_bound를 사용하면 편하지만 실력 향상을 위해 직접 이분탐색을 구현하여 써봐도 좋다. 끝까지 반복하면 10(2) 20(4) 30(3) 50(5) ()안에 수는 인덱스이다 의 결과를 얻을 수 있는데 이것은 부분 수열의 길이가 4라는 것이지 이 결과가 최장 증가 부분.. 2020. 6. 25.
[BOJ] 백준 14939번: 불 끄기 첫 줄에서 스위치를 누를수 있는 모든 경우 (1024가지)를 미리 정해놓고 두번째 줄부터 이전 줄의 전구의 켜짐 상태를 그리디하게 끄면서 마지막 줄에 켜진 전구의 유무로 경우의 수를 구하는 문제 #include #include #include #include #include #include #include #define INF (10001) using namespace std; typedef pair pii; typedef long long ll; int nx[5] = { 0,0,0,-1,1 }; int ny[5] = { 0,-1,1,0,0 }; char map[11][11]; char tmp[11][11]; void click(int x, int y) { for (int i = 0; i < 5; i++.. 2020. 6. 23.
[BOJ] 백준 13537번: 수열과 쿼리 1 머지 소트 트리 + 이분탐색 아래글 참고. 2020/08/17 - [알고리즘] - 머지 소트, 머지 소트 트리 및 관련 백준 문제 풀이 #include #include #include #include #include #include using namespace std; typedef long long ll; int n, m, k; int arr[100001]; int mst[17][100002] = { 0, }; void make_tree(int s, int e,int depth) { if (s == e) { mst[depth][s] = arr[s]; } else { int mid = (s + e) / 2; make_tree(s, mid, depth + 1); make_tree(mid + 1, e, de.. 2020. 6. 22.

티스토리툴바