[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..
[446] 느리게 갱신되는 세그먼트 트리(lazy propagation)
1. 세그먼트 트리 동작 과정세그먼트 트리는 루트 노드에서 리프 노드까지 범위를 나누어 가며 통일된 연산값을 유지해야 합니다.따라서 자식 노드에서 부모 노드로 올라가더라도 더 넓어진 범위에 대해 연산 결과를 유지할 수 있어야합니다.이게 가능한 연산은 최대, 최소, 덧셈, 곱셈 등 일부의 결과로 전체 범위에 적용이 가능한 연산을 세그먼트 트리에 적용할 수 있습니다. 8 크기의 배열에서 3, 2, 5, 3, 5, 2, 3, 4의 값을 가지고 있고, 구간합을 관리하는 세그먼트 트리는 다음과 같습니다. 이 세그먼트 트리에서 2 ~ 8 범위의 구간합을 구하고 싶다면 다음과 같이 구합니다. 찾고자 하는 범위 안에 포함될 때까지 자식으로 내려가며 합을 구하면, 2+8+14로 24라는 것을 알 수 있습니다.다음으로 세..
