[목차] 완전 탐색과 DP로 푼 LIS LIS 알고리즘 아이디어 알고리즘 알고리즘 분석 예제 정리 1. 완전 탐색과 DP로 구현한 LIS 이 전의 글에서는 LIS를 구하는 알고리즘을 완전 탐색과 동적 계획법으로 구현했었다. 동적 계획법 풀이는 O(N²)의 시간 복잡도를 가졌었다. 하지만 이분 탐색을 이용하면 O(N logN)의 시간 복잡도로 더 빠르게 해결할 수 있다. 이번 글에서는 이분 탐색을 이용하여 O(N log N)의 시간 복잡도로 구현해보려고 한다. 이분 탐색의 LIS를 이해하려면 이분 탐색의 lower_bound() 함수와 upper_bound()함수에 대해 알고 있어야 한다. 또한 DP로 푼 LIS알고리즘도 이해하고 오면 도움이 된다. 따라서 앞의 부분에 대한 이해가 안되어있다면 최소한 이분..

최적화 문제를 결정 문제로 바꾸어 해결하면 매우 단순한 생각으로 바꿀 수 있다. 예를 들면 Parametric Search를 결정 문제로 바꾸면 단순한 이분 탐색으로해결할 수 있고 부분수열의 합이 S이상것들 중 최대 최소를 구할 때에도 합이 S인가?라는 결정 문제로 바꾸면 단순한 부분수열의 합 문제로 바꾸어 해결할 수 있다.

1. 두 포인터란? 포인터 두 개를 사용하여 배열이나 문자열을 탐색하는 알고리즘이다. 흔히 배열을 탐색하다 보면 완전탐색을 진행할 경우 O(N²)의 시간복잡도를 가진다. 하지만 투 포인터를 이용하면 동시에 포인터 두 개로 탐색하므로 O(N)의 시간 복잡도로 한 번에 탐색할 수 있다. 예시 https://www.acmicpc.net/problem/2230 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net #include #include using namespace std; int N, M, a..

https://gamedoridori.tistory.com/54 [C++ STL] vector 선언 및 초기화 (1차원, 2차원) 개요 C++의 STL 중 하나로, 한 번에 한 타입만 저장 가능합니다. 이번 게시글에서는 vector의 선언과 초기화에 대해 다뤄보겠습니다. 상세 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 #include using namespace std; int gamedoridori.tistory.com

1. 문제 https://www.acmicpc.net/problem/2231 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net 2. 풀이 아이디어 제한 시간이 2초인 만큼 모든 수를 선형탐색해도 시간이 넉넉하다. 따라서 1부터 N까지 반복문을 다음 수를 만들면 된다. 분해합이 N이 되는 순간 반복문을 멈추고 바로 답을 출력하면 통과 시간을 최대한 빠르게 할 수 있다. 분해합을 구하는 과정은 [자릿수 분해] 알고리즘을 사용한다. 알고리즘 순서 1 ~ N까지 반복문을 돌며 현재의 숫자의..