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..

https://husk321.tistory.com/363 [C++] C++ sort는 어떤 알고리즘을 사용할까 서론 '리스트는 어떤 정렬 알고리즘을 사용하나요?' 사실 algorithm 헤더에 있는 sort는 어떤 알고리즘을 사용하는가에 대한 이야기는 많이 있었습니다. 그런데 리스트의 경우 리스트 내부 함수로 so husk321.tistory.com 2개의 원소를 비교하는 정렬 stl이용하기 https://stormpy.tistory.com/344 [C++] List 에서 pair로 된 데이터 찾기 list를 사용하다가 두 개의 데이터를 담아야 해서 pair를 사용했다. 찾을 때는 통상 first로 찾았는데, 이는 사실 map을 이용하는 편이 훨씬 편하다. list에서 pair를 사용하여 둘 다 만족하는..

1. 개념 간단한 순열과 조합은 기본적인 조건문과 반복문으로 출력할 수 있다. N개의 숫자 중에서 M개를 뽑아 순열, 조합하는 경우를 구해보자. 예를 들어 1~5까지 숫자 중에서 2개를 순열, 중복순열, 조합, 중복조합으로 뽑는다고 해보자. 참고로, 순열은 순서의 개념이 포함되므로 모든 숫자들을 나열하는 경우이고, 조합은 순서의 개념이 없으므로 출력되는 숫자들은 오름차순, 중복조합의 경우 비내림차순이 된다. 2. 구현 코드로 보면 다음과 같다. 순열(P) //순열 #include using namespace std; int check[6]; int main(void) { //ex) P(5, 3) for (int i = 1; i

1. 문제 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 중복을 허락하여 해당 동전을 만들 수 있는 경우이므로 자연수 분할, 즉 중복 조합문제이다. 2. 풀이 아이디어(시행착오) 동전 n개로 k원을 만들 수 있는경우의 수를 구하는 문제이다. 언뜻 보기엔 일반적인 DFS로 재귀를 이용한 top - down방식으로 풀 생각이 들 수 있다. 예들 들어 1, 2원짜리 동전을 가지고 4원을 만드는 경우 3원(4 - 1원)에 1원을 더한 것과 2원(4 -..