알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/13711 두개의 수열이 주어졌을 때, LCS를 구하는 문제입니다.  두개의 수열이 주어졌을 때, 두 수열의 최장 공통 부분 수열을 구하는 문제입니다.N의 값이 10^5이기에 반복문을 통해서 전부  확인해본다면 시간 초과가 생깁니다. 문제를 봤을 때, 각 수열은 1부터 N까지 숫자가 1개씩만으로 주어진다는 것을 알 수 있습니다.그렇다면, 하나의 문자열을 기준으로 잡고, 다른 문자열의 숫자가 몇번 째로 나오는지를 저장만 해준다면,이는 가장 긴 증가하는 부분 수열의 문제로 바뀐다는 것을 알 수 있습니다. 예를 들어보겠습니다.문자열 1 : 1 2 4 7 8 9 6 3 5문자열 2 : 2 4 6 8 1 3 5 7 9-> 해당 수열의 LC..

문제 링크 입니다 https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net https://junseok.tistory.com/23 이 문제의 심화 문제 입니다. 백준 12015 - 가장 긴 증가하는 부분 수열2(복습) 문제 링크입니다 https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다...

문제 링크입니다 https://www.acmicpc.net/problem/3745 3745번: 오름세 입력은 여러개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 주가를 관찰한 날의 수 N (N ≤ 100000)이 주어진다. 둘째 줄에는 관찰한 주가가 첫 날부터 순서대로 주어진다. www.acmicpc.net 가장 긴 증가하는 부분 수열 o(n log n) 문제였습니다. 저는 lower_bound를 구현했습니다! 문제 접근 방법 1. 수열을 입력받은 뒤 오름차순으로 정렬한다. 2. vector에 arr[0]의 값을 입력한 뒤, lower_bound를 실행한다. 3. vector의 크기를 출력한다. 4. 1번~3번을 반복한다. 문제 접근 방법 - 2번 void binary_search(..