[453] 백준 2631번 - 줄세우기(LIS)
1. 문제https://www.acmicpc.net/problem/2631 2. 문제 이해임의의 순서로 수열이 주어질 때, 오름차순으로 정렬하기 위해 움직이는 최소 횟수를 구하는 문제입니다.움직일 때는 데이터를 정렬할 때처럼 자리를 서로 바꾸는 것이 아니라, 움직이는 수가 두 수 사이로 비집고 들어갑니다.[3, 7, 5, 2, 6, 1, 4] 가 주어질 때, 아래와 같이 최소 4번으로 정렬을 완성할 수 있습니다.3. 해결 방법해를 구하기 위해 두 가지를 살펴봅시다.가. 한 원소를 여러 번 움직일 필요가 없다.생각해보면 한 원소를 자리를 두 번 움직일 경우, 그냥 한 번에 최종 위치로 움직이는 것과 다름이 없습니다.굳이 두 번을 움직일 필요가 없고, 다시 말해 n개의 원소 중에 일부 원소만 선택해 자리를 ..
[452] 백준 11057번 - 오르막수(점화식과 DP테이블)
1. 문제https://www.acmicpc.net/problem/110572. 문제 이해길이가 N이고 원소가 한 자리 수인 단조 증가 수열의 개수를 구하는 문제입니다.단조 증가 수열은 나중에 나오는 원소가 이전의 원소보다 같거나 큰 수열을 말합니다.예를 들어 [2, 2, 3, 4]와 [3, 6, 7, 8], [1, 1, 1, 1, 9]는 단조 증가 수열이지만,[2, 2, 3, 2], [3, 6, 7, 6], [9, 1, 1, 1, 1]은 단조 증가 수열이 아닙니다.참고로 단조롭다는 표현은 영어로 monotonic으로 사용합니다. 3. 해결 방법우선 N이 1부터 차례대로 살펴봅시다. 길이가 1인 단조 증가 수열은 [0], [1], [2], [3], [4], [5], [6], [7], [8], [9]로 총..
[449] 완전수 쉽게 배우기
1. 완전수란 무엇일까?완전수는 자신을 제외한 모든 약수의 합이 자기 자신과 같은 수를 말해.먼저, 진약수라는 개념을 알아보자.진약수는 자기 자신을 제외한 약수를 뜻해.예를 들어, 숫자 6의 약수는 1, 2, 3, 6인데, 이 중 6을 뺀 1, 2, 3이 바로 6의 진약수야.진약수의 합에 따라 숫자는 세 가지로 나눌 수 있어. 완전수: 진약수의 합이 자기 자신과 같은 수예: 6의 진약수는 1, 2, 3이고, 이걸 더하면 6이 돼. 그래서 6은 완전수야! 부족수: 진약수의 합이 자기 자신보다 작은 수예: 8의 진약수는 1, 2, 4이고, 이걸 더하면 7이야. 7은 8보다 작으니까, 8은 부족수야. 과잉수: 진약수의 합이 자기 자신보다 큰 수예: 12의 진약수는 1, 2, 3, 4, 6이고, 이걸 더하면 1..
