Lis2

• 

  [백준][Java] 2631 - 줄세우기 1. 문제 정보 https://www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 난이도 : G4 유형 : DP, LIS 시간 : O(N^2) 2. 문제 풀이 주어진 줄에서 가장 긴 증가하는 부분 수열을 찾아내면 된다. 가장 길게 증가하는 부분 수열을 제외한 나머지 원소들만 자리를 바꿔야 최소 값이 나오기 때문이다. 3 7 5 2 6 1 4 예시에서 주어진 줄을 보면 3 x 5 x 6 x x 부분 수열이 가장 길게 증가하는 수열이다. 이 부분 수열은 괜히 자리를 변경을.. Algorithm, Problem Solving/백준(boj) 2024. 3. 23.

• [백준][Java] 2565 - 전깃줄 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 난이도 : G5 유형 : LIS, DP 비슷한 문제 https://www.acmicpc.net/problem/7578 7578번: 공장 어떤 공장에는 2N개의 기계가 2열에 걸쳐 N개씩 배치되어 있다. 이 2개의 열을 각각 A열과 B 열이라고 부른다. A열에 있는 N개의 기계는 각각이 B열에 있는 N개의 기계와 하나씩 짝을 이루어 케이블 www.acmicpc.net 문제 풀이 세그먼트 트리로도 풀리지만 .. Algorithm, Problem Solving/백준(boj) 2023. 3. 23.