PS하는 깃털

예전에 LIS알고리즘을 DP로 O(n^2)만에 구현하는 포스팅을 올린 적이 있다. 하지만 이 알고리즘을 쓰기엔 시간복잡도가 크다보니 시간초과가 나는 문제가 많다.LIS O(n^2) : https://code-feather.tistory.com/19 최장 증가 부분 수열 DP O(N^2)백준 : https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20code-feather.tistory.com 이번 포스팅에서는 이분탐색을 활용한 O(nlogn) LIS 알고리즘을 올려보려고 한다. 이분탐색을 써서 푸는 백준 문제..

백준 : https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이www.acmicpc.net  오늘은 DP를 이용해 최장 증가 부분 수열의 길이를 구하는 코드를 구현해볼 것이다.최장 증가 부분 수열 : 어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다. 이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라 한다.ex)  A = ..

PS를 좋아하는 사람이라면 한 번쯤은 Knapsack Problem에 대해 들어본 적이 있을 것이다. DP를 활용하는 대표적인 문제이기도 하고, 알고리즘을 공부하기에도 좋은 문제이다. Knapsack Problem : 주어진 물건들에 대해 그 가치와 무게가 주어져있을 때, 무게의 합이 담을 수 있는 최대 무게를 넘기지 않고 가치의 합이 최대가 되도록 배낭에 담기 위해서는 어떤 물건을 담아야하는가? 자세한 설명 : https://en.wikipedia.org/wiki/Knapsack_problem Knapsack problem - Wikipedia From Wikipedia, the free encyclopedia Problem in combinatorial optimization Example of a ..

배열을 다루다보면 일정한 기준으로 그 배열을 정렬해야하는 상황이 생긴다. 이럴 때 C++ STL 에서 제공하는 sort()를 이용하면 편하다. sort()는 기본적으로 헤더파일에 속해있다. 그래서 이 함수를 쓰기 전에 먼저 헤더파일을 가져와야한다. #include 1) 배열(array) 배열을 정렬할 때는 sort()를 아래와 같이 사용한다. sort(시작주소, 끝주소 + 1) 시작주소는 (배열의 이름) + (번지수) 로 표기한다. 예를 들어 arr라는 배열의 1번지부터 시작하고 싶으면 arr+1로 나타낸다. 끝주소는 (배열의 이름) + (번지수)+1 로 표기하고, 예를 들어 n-1번지는 arr+n으로 표현한다. 2) 벡터(vector) 벡터를 정렬할 때에도 배열과 비슷한 방식을 사용한다. sort(v...