꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/3045 3045번: 이중 연결 리스트 문제 창영이는 1학년 때 숙제로 했던 이중 연결 리스트 소스를 상근이에게 생일 선물로 보내주었다. 상근이는 드디어 자신이 원하던 기능이 있는 소스를 받게 되어서 매우 기뻤다. 상근이는 하�� www.acmicpc.net 블로그 방문하셨던 분이 질문주셨던 문제여서 풀어보기 시작했던 문제였습니다. 처음에는 제목만 보고 이중 연결 리스트만 구현하면 되는줄 알았는데 생각보다 많은 부분을 고려해야 풀 수 있었던 문제였습니다. 우선, 이중 연결 리스트가 어떤 식으로 삽입 삭제되는지 A 1 4 연산을 예시로 그림과 함께 설명드리겠습니다. 1. 1번 노드를 떼어내야하기 때문에 1번 노드의 다음 노드인 2번..

문제 링크입니다: https://www.acmicpc.net/problem/12738 N이 최대 1,000,000이기 때문에 O(N^2)으로는 풀 수 없는 문제입니다.따라서, O(NlogN)으로 LIS의 길이를 구해줘야합니다. #include #include using namespace std; const int MAX = 1000000 + 1; int N; int arr[MAX]; int cache[MAX]; int LIS(void) { int idx = 0; cache[idx] = arr[0]; for (int i = 1; i < N; i++) { //오름차순이라면 if (cache[idx] < arr[i]) { cache[++idx] = arr[i]; } //치환 else { int idx2 = l..

문제 링크입니다: https://www.acmicpc.net/problem/2568 백준 2565번 전깃줄(https://jaimemin.tistory.com/1094)의 연장선 문제였습니다. 알고리즘은 아래와 같습니다.1. 연결한 줄을 입력받고 A 전봇대 인덱스를 모두 visited 배열에 표시합니다.2. LIS 함수를 통해 가장 긴 부분 증가 수열의 길이를 구합니다.-> answer 배열에 {인덱스, 연결된 B 전봇대 인덱스} 표시해줍니다.3. N - (2번에서 구한 길이)를 출력해줍니다.4. 각 인덱스에 위치한 A 전봇대 인덱스를 구하고 해당 인덱스는 연결이 되어있는 상태이므로 visited 배열에서 빼줍니다.5. 4번까지 완료하면 visited 배열에 표시되어있는 인덱스는 초기에는 연결했지만 LI..

문제 링크입니다: https://www.acmicpc.net/problem/14002 가장 긴 증가하는 부분 수열 5(https://jaimemin.tistory.com/1095)와 동일한 문제였습니다. #include #include #include using namespace std; const int MAX = 1000 + 1; int N; int arr[MAX]; int cache[MAX]; pair answer[MAX]; stack s; int LIS(void) { int idx = 0; cache[idx] = arr[0]; answer[0] = { 0, arr[0] }; for (int i = 1; i < N; i++) { if (cache[idx] < arr[i]) { cache[++idx]..

문제 링크입니다: https://www.acmicpc.net/problem/14003 Crocus님(https://www.crocus.co.kr/681) 덕분에 풀 수 있었던 문제였습니다.O(NlogN)에 LIS의 최대 길이를 구하는 알고리즘을 통해서는 정확한 LIS 배열을 구할 수 없다는 것을 처음 알았습니다. 기존의 LIS 코드는 동일하고 pair answer 배열과 스택을 이용해 정확한 LIS 배열을 구하는 것은 코드의 주석을 보면 이해가 될 것입니다! #include #include #include using namespace std; const int MAX = 1000000 + 1; int N; int arr[MAX]; int cache[MAX]; pair answer[MAX]; stack s..

문제 링크입니다: https://www.acmicpc.net/problem/2565 백준 2352번 반도체 설계(https://jaimemin.tistory.com/488)와 유사한 문제였습니다. #include #include using namespace std; const int MAX = 500 + 1; int N; pair connect[MAX]; int cache[MAX]; int LIS(void) { int idx = 0; int length = 0; cache[idx] = connect[0].second; for(int i=1; i> N; for (int i = 0; i > connect[i].first >> connect[i].second; sort(connect..

문제 링크입니다: https://www.acmicpc.net/problem/11054최근에 자주 풀었던 LIS의 응용문제였습니다.http://jaimemin.tistory.com/317와 다른점이라면 기존에는 해당 인덱스를 시작으로 하는 최대 부분수열의 길이를 캐시에 저장했는데 이 문제에서는 해당 인덱스를 마지막 요소로 하는 최대 부분수열의 길이를 캐시에 저장해야했다는 점입니다.우선 정방향 LIS를 구하고 캐시에 저장한 뒤 반대방향 LIS를 구하고 캐시에 저장했습니다.그 다음 수열 S가 어떤 수 Sk를 기준으로 S1 Sk+1 > ... SN-1 > SN 를 만족해야하므로 모든 인덱스를 순회하며 fCache[i]+rCache[i]의 최대값을 찾았습니다. 여기서 주의..

문제 링크입니다: https://www.acmicpc.net/problem/1965사실상 최대 증가부분 수열의 길이 구하기 문제였습니다.예전에도 LIS 문제를 풀어봤기 때문에 쉽게 구현할 수 있었습니다. /* 정육면체 모양의 상자들이 일렬로 늘어서 있다. 상자들마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 있다. 예를 들어 앞에서부터 순서대로 크기가(1, 5, 2, 3, 7)인 5개의 상자가 있다면, 크기 1인 상자를 크기 5인 상자에 넣고, 다시 이 상자들을 크기 7인 상자 안에 넣을 수 있다. 하지만 이렇게 상자를 넣을 수 있는 방법은 여러 가지가 있을 수 있다.앞의 예에서 차례대로 크기가 1, 2, 3, 7..

http://jaimemin.tistory.com/317?category=985009에서는 LIS의 길이만 구했는데 이번에는 직접 최대 부분 수열까지 구해보는 코드입니다. /*최대 증가 부분 수열을 실제로 계산하기*/#include #include #include #include //memsetusing namespace std; int length; //수열 길이int cache[101], S[100], choices[101];//S[start]에서 시작하는 증가 부분 수열 중 최대 길이 반환int LIS(int start){ int &result = cache[start + 1]; if (result != -1) return result; result = 0; int bestNext = -1; for..

문제 링크입니다: https://algospot.com/judge/problem/read/LIS책에서 언급한 이분 검색을 이용하여 시간 복잡도 O(nlogn)을 충족하는 알고리즘을 작성했습니다. /*정수 수열 S에서 최대 부분 수열의 길이를 구하시오*/#include #include #include #include //memsetusing namespace std; int idx; //최대 부분 수열의 길이int length; //순열 길이int arr[500]; //원래 주어진 순열int C[500];//int cache[100]; //list2용 //list3용//int cache[101]; //index -1을 추가한 캐시(길이를 구할 때 각 위치를 순회하는 코드 생략) /*//완전 탐색 알고리즘i..