[목차] LIS란? LIS를 구하는 알고리즘 완전 탐색 알고리즘 분할 정복 백트래킹 두 완전 탐색 알고리즘의 비교 동적 계획법 알고리즘 O(N²) 풀이 이분 탐색을 이용한 풀이 두 동적 계획법 알고리즘 비교 세그먼트 트리 알고리즘 LIS의 대표 예제 전깃줄 문제 줄세우기 문제 합친 LIS 1. 가장 긴 증가하는 부분 수열(LIS)이란? 증가하는 부분 수열을 중에서 길이가 가장 긴 수열을 말한다. 영어로는 줄여서 LIS(Longest Increasing Subsequence)라고 한다. 여기서 잠깐 LIS의 S가 subarray가 아니라 subsequence의 이유를 보면 다음과 같다. 부분 수열의 종류는 크게 subarray와 subsequence가 있다. subarray는 연속적으로 이어져있는 부분 수..

[백준] 14502번 연구소를 풀다가 화딱지가 나서 겨우겨우 구현했다. 이게 과연 쓸 일이 있을까 해서 그냥 남겨둔다. 백트래킹으로 1차원 배열의 조합은 구현해봤어도 2차원 배열의 조합은 처음 해본다. 생각보다 생각해내기 어려웠다.... 직접 손으로 써보면서 겨우 찾아냈다.. y좌표가 증가하는 순으로 x좌표가 무조건 0부터n-1까지가 아니라 다음 탐색에서 y랑 같을 때만 x이고 그 다음부터는 0부터 n-1까지이다. x부터가 아니라 바로 x+1부터로 하면 되지 않냐? 하는 의문이 들지만 해보면 처음 채울 때에 첫째칸이 안채워진다. 따라서 x부터 하는게 맞다. #include using namespace std; int map[4][4]; int cnt; void print() { for (int i = 0..

1. 가장 긴 증가하는 부분 수열(LIS)이란? 증가하는 부분 수열을 중에서 길이가 가장 긴 수열을 말한다. 영어로는 줄여서 LIS(Longest Increasing Subsequence)라고 한다. 이때 부분수열의 원소들은 주어진 원래의 배열처럼 이어져 있지 않아도 된다는 특징이 있다. 예를 들어 다음과같은 수열 S(n)을 보자. S(n) = {10, 20, 10, 30, 20, 50} 수열 S(n)에 대하여 다음과 같이 총 5개의 증가하는 부분 수열을 만들 수 있다. {10, 20, 30, 50} {20, 30, 50} {10, 30, 50} {30, 50} {20, 50} 이 중에서 LIS는 {10, 20, 30, 50}이 되는 것이다. 부분 수열 문제는 배낭 문제(knapsack problem)의..

1. 가장 긴 증가하는 부분 수열(LIS)이란? 증가하는 부분 수열을 중에서 길이가 가장 긴 수열을 말한다. 영어로는 줄여서 LIS(Longest Increasing Subsequence)라고 한다. 이때 부분수열의 원소들은 주어진 원래의 배열처럼 이어져 있지 않아도 된다는 특징이 있다. 예를 들어 다음과같은 수열 S(n)을 보자. S(n) = {10, 20, 10, 30, 20, 50} 수열 S(n)에 대하여 다음과 같이 총 5개의 증가하는 부분 수열을 만들 수 있다. {10, 20, 30, 50} {20, 30, 50} {10, 30, 50} {30, 50} {20, 50} 이 중에서 LIS는 {10, 20, 30, 50}이 되는 것이다. 부분 수열 문제는 배낭 문제(knapsack problem)의..

https://shoark7.github.io/programming/algorithm/4-ways-to-get-subarray-consecutive-sum 최대 연속 부분수열 합을 구하는 4가지 알고리즘 I introduce 4 algorithms to get largest continuous sum of subarrays shoark7.github.io 1. 완탐 오앤제곱 2. DP on + 투 포인터???

https://velog.io/@pppp0722/%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EB%AC%B8%EC%A0%9C-%EC%9C%A0%ED%98%95-%EC%A0%95%EB%A6%AC 코딩테스트 문제 유형 정리 코딩테스트에서 가장 중요한 것은 꾸준함이 아닐까...? 🔥 코딩테스트의 중요성 신입 개발자 채용의 경우 지원 후 코딩테스트로 일정이 시작되는 경우가 대부분이다. 물론 코딩테스트를 보지 velog.io https://devjeong.com/algorithm/algorithm-1/#%ED%88%AC-%ED%8F%AC%EC%9D%B8%ED%84%B0 [Algorithm] 백준 문제 추천 devjeong.com

https://jeonyeohun.tistory.com/86 [알고리즘 정리] 배낭 문제(Knapsack Problem) Knapsack Problem Knapsack Problem, 배낭문제는 다이나믹 프로그래밍에서 매우 유명한 문제이다. 어떤 배낭이 있고 그 배낭안에 넣을 수 있는 최대 무게가 K라고 하자. 배낭에 넣을 수 있는 N개의 물건이 jeonyeohun.tistory.com 예제로는 [백준 12865번] 평범한 배낭을 참고한다. 이 문제는 NP-hard문제이다. optimazation problem 모든 경로를 탐색하여 최적해를 찾는 문제!! DP를 이용해야겠지?? 경로: 해당 무게로 만들 수 있는 조합 값: V가치 1. top - down 방식 2. bottom - up 방식 tabulat..