그냥 하는 노트와 메모장

BOJ 2995 생일 [분류 : 세그먼트 트리] [풀이] [좌표평면] 구간의 왼쪽들을 x축으로, 구간의 오른쪽들을 y축으로 생각해보자. 좌표평면으로 옮긴 두 구간을 비교할 땐 두 점을 비교하는 걸로 동치로 볼 수 있다. 둘 중에 한 점이 x축이 작고 y축이 크면 다른 한 점(구간)을 포함한다라고 볼 수 있다. [정렬] 세그먼트 트리 갱신해야하기 때문에 정렬을 수행한다. 나는 x축을 비오름차순으로, y축을 비내림차순으로 접근했다. 이렇게 접근하면 방문하고 있는 x좌표는 지금까지 방문한 좌표들보다 무조건 작거나 같으므로 구간을 포함할 수 있는 가능성을 열어두게끔 한다. 반대로 y좌표는 같거나 작아야하는 좌표들 중 가장 큰 값을 가져와야하므로 구간 최대를 가져오기 위해 세그먼트 트리를 사용한다. 더보기 #in..

배낭 문제(냅색) 시리즈 - BOJ 12865 평범한 배낭, BOJ 12920 평범한 배낭2, Algospot SUSHI [분류 : 다이나믹 프로그래밍] 냅색 문제들을 모아 풀이를 공유하는 포스팅입니다. 이 포스팅은 희한한 냅색 문제들 보는 대로 갱신됩니다. 1. BOJ 12865 평범한 배낭 더보기 일반적으로 알고있는 냅색을 사용하면 된다. 시간 복잡도는 O(NK)가 된다. 재귀적으로 처리해도 좋고, 일차원 배열을 만들어서 큰 값에서 작은 값으로 내려가면서 데이터 오염을 피하며 dp를 구성해도 좋다. #include #include #include using namespace std; const int MAX_N = 100; int N, dp[MAX_N][100001], w[MAX_N], v[MAX_N..

BOJ 10563 정수 게임 [분류 : 다이나믹 프로그래밍] 은근히 어려운 문제.. [풀이] [구간 내의 수 선택] 현재 수를 뽑을 수 있는 구간을 [l, r]이라고 하자. 여기 안에서 조건에 만족하는, 즉 양 옆에 수들 모두 자신보다 작은 후보 집합 S={x | A[x-1] A[x+1]} 중에서 하나 x를 뽑았다고 해보자. [구간 밖의 선택] 그러면 구간은 [l, x), (x, r] 구간으로 나눠지고, 여기서 어느 구간을 선택할지를 고르면 되는데, 1이 존재하는 구간은 반드시 둘 중에 하나밖에 없다. 그 1이 포함되지 않은 구간을 선택하는 경우는 현재 내가 1이 포함되어 있는 구간 중 어느 수를 선택해도 반드시 질 경우에 유효할 수 있다. 가령 구간 [l, x)을 뽑으면 반드시 진다고 ..

BOJ 1555 소수 만들기 [분류 : 다이나믹 프로그래밍, 수학] [풀이] [순열] N개의 수에 대해서 각 자리수에 어떤 수를 둬도 상관없으므로 최대 N!은 먹고 들어간다. (C++에서 next_permutation 사용) [연산 규칙] +,-,*,/ 모두 사칙연산에도 쓸 수 있지만 특히 -는 사칙연산뿐만 아니라 단항 연산에 사용될 수 있다. 즉, 값을 음수면 양수로, 양수면 음수로 바꿀 수 있다. 단순히 두 피연산자 e1과 e2(e1가 왼쪽에 있을 때)가 있을 때 나올 수 잇는 방법은 아래가 있다 e1 + e2 e1 - e2 e1 * e2 e1 / e2 하지만 음수를 붙여주면 경우의 수는 배로 늘어난다. -e1 - e2 -e1 + e2 -e1 * e2 -e1 / e2 보면 1.~4.에 음수를 붙힌 것..

BOJ 1955 수식 표현 [분류 : 다이나믹 프로그래밍] [풀이] 할 수 있는 연산을 생각해보자. 덧셈 곱셈 팩토리얼 여기 세 가지 연산에서 항으로 들어갈 수 있는 표현식도 생각해보자. 대신 마지막 표현식만 생각하자. 표현식을 e1, e2로 둘 때 e1+e2, e1*e2, e1!로 표현이 가능하다. 따라서 n이 주어지면 1.에서는 단순 덧셈으로 구간을 나누고, 2.에서는 약수 판별을, 3.에서는 현재 값이 특정 표현식 e1의 팩토리얼인지 확인해서 다이나믹을 구성해주면 된다. 특정 표현식이라고 표기한 이유는 6! = (3!)!일 수도, (1+5)!일 수도 있기 때문이다. 더보기 #include #include #include using namespace std; const int MAX_N = 1e4 +..

BOJ 15487 A[j]-A[i]+A[l]-A[k] [분류 : 다이나믹 프로그래밍] [풀이] A[j] - A[i]를 먼저 계산해보자. 고정된 j에 대해 A[j]-A[i]가 최대가 되기 위해선 A[i]가 최소이어야 한다. 따라서 j를 순회하면서 [0, j) 구간에서 최소값을 유지하자. 나머지 A[l] - A[k]을 구간 (j, N)에서 구하면 된다. 이 부분은 거꾸로 진행하면 된다. 즉 k를 N-2부터 시작해서 2까지 감소시켜나가면서 A[l]을 최대값으로 유지하며 진행하면 된다. 이렇게 양쪽으로 최소/최대를 유지해나가며 그 중 최대값을 가져오면 AC를 받을 수 있다. 더보기 #include #include using namespace std; const int MAX_N = 1e6; int main() ..

BOJ 2313 보석 구매하기 [분류 : 다이나믹 프로그래밍] 연속 부분 수열의 합을 최대로 하는 방식을 여러 차례 반복해서 진행하면 되는 문제. [주의해야 할 점] 정답은 32비트 int 자료형에 들어가지 않을 수 있다. 오버플로우에 유의하자. 구간의 길이가 짧아야한다. 0인 요소에 대해 처리할 필요가 있다. 가령 "0 0 0 1 0"이 입력으로 들어오면 [1, 4]가 아니라 [4, 4]가 정답 구간이다. 더보기 #include #include #include using namespace std; int main() { int n, L, sum, asum, i, l, r, d, al, ar; long long ans = 0; vector seg; scanf("%d", &n); while (n--) { ..