DP - LIS(최장 증가 수열) 및 0-1 Knapsack 개념 (JAVA)

최장 증가 부분 수열(LIS) 최장 증가 부분 수열이란? 어떤 임의의 수열이 주어졌을 때, 수열에서 앞에서부터 차례대로, 순서를 유지한 채 몇 개의 숫자들을 뽑아서 부분 수열을 만들 수 있다. 이렇게 만들 수 있는 부분 수열 중 가장 긴 수열을 최장 증가 부분 수열(LIS, Longest Increasing Subsequence)라고 한다. 예를 들어, [6, 2, 1, 4, 3, 5]라는 수열이 있다면마지막 원소 5를 붙일 거라면, 5보다 앞에 있고, 5보다 작은 수로 끝나는 가장 긴 부분 수열에 붙이는 것이 좋다. [1, 3, 5]가 위 수열에서 만들 수 있는 최장 증가 부분 수열에 해당하고 길이는 3이다. (여러 개 일 수 있다. ) DP를 활용하여 O(N²)으로 구해보기 배열의 숫자를 하나씩 살펴..

• format_list_bulleted JAVA/Algo 개념
• · 2023. 7. 16.
• textsms

[백준] 5676.음주코딩 - 세그먼트 트리 (JAVA)

문제링크 🚩 https://www.acmicpc.net/problem/5676 5676번: 음주 코딩 각 테스트 케이스마다 곱셈 명령의 결과를 한 줄에 모두 출력하면 된다. 출력하는 i번째 문자는 i번째 곱셈 명령의 결과이다. 양수인 경우에는 +, 음수인 경우에는 -, 영인 경우에는 0을 출력한다. www.acmicpc.net ​ 📕 문제 접근 📕 -기존 세그먼트 트리와 매우 유사하지만 EOF 를 처리하는 유형의 문제이다 - 여러가지 방법이 존재하지만 본인의 경우 try - catch 방식을 활용하여 문제를 해결하였다. - 문제에서 정확한 숫자가 아닌 음수 혹은 정수 혹은 0을 요구했기에 입력 받는 과정에서 음수면 - 양수면 +의 로직을 활용하였다. 💻 Code 💻 import java.io.Buffer..

• format_list_bulleted JAVA/Algo 풀이
• · 2023. 7. 16.
• textsms

[백준] 2268.수들의 합 7 - 세그먼트트리(JAVA)

문제링크 🚩 https://www.acmicpc.net/problem/2268 ​ 📕 문제 접근 📕 해당 문제는 세그먼트 트리에서 트리를 만드는 과정에 없어지고 modify와 sum만하면 풀 수 있도록 만들어진 문제다 세그먼트 트리의 정석적인 풀이 방법대로 풀면 매우 쉽지만 문제를 잘 읽어야한다. N개의 수 A[1], A[2], …, A[N] 이 주어졌을 때, 함수 Sum(i, j)는 A[i] + A[i+1] + … + A[j]를 구하는 함수이다. (i > j일 경우에는 A[j] + A[j+1] + ... + A[i]) A가 주어졌을 때** 해당 조건을 확인하면 i > j 일 때 도 있다는 의미가 내포되어있다. 해당 부분을 놓친다면 답이 틀리게된다. 💻 Code 💻 import java.io.Buffer..

• format_list_bulleted JAVA/Algo 풀이
• · 2023. 7. 15.
• textsms

[백준] 11505.구간 곱 구하기 - 세그먼트트리(JAVA)

문제링크 🚩 https://www.acmicpc.net/problem/11505 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 📕 문제 접근 📕 - 세그먼트 트리의 입문 문제로 구간 합 구하기과 매우 유사한 문제 입니다- 다만 곱이나보니 mulTree 함수를 만들 때 return 값에 유의하여 0이 아닌 1이 반환되도록 하였습니다. -> 0을 곱해버리면 결과가 0이 나오기 때문. 💻 Code 💻 import java.io.BufferedReader..

• format_list_bulleted JAVA/Algo 풀이
• · 2023. 7. 14.
• textsms