1. 전구편의상 왼쪽 스위치와 오른쪽 전구의 번호가 1 2 3 4.. 처럼 순서대로 되어 있다고 하자. p[i] = (왼쪽 i번 스위치를 눌렀을 때 켜진 오른쪽 전구의 번호) 라 하자. 전선이 교차하지 않게 왼쪽에서 {i1, i2, i3, ... ik} 스위치를 켰다는 것은, p[i1] < p[i2] < p[i3] < ... < p[ik] 라는 것과 동치이다. 이렇게 최대 개수의 스위치를 켜는 것은, 최장 증가 부분 수열 (LIS) 문제와 동일하다. 이는 동적 계획법으로 O(N^2)에 찾고 역추적도 할 수 있다. (만약 방법을 모른다면, dp[i] = i번 수에서 끝나는 최대 길이의 LIS라 정의하고 생각해 보자.)왼쪽 스위치와 오른쪽 전구의 번호가 실제로 1 2 3 4가 아니라는 것이 문제인데, 그냥 ..
1. 생존자이 문제를 푸는 데 있어서 아주 중요한 아이디어는, 바로 이것이 스케줄링 문제라는 것을 발견하는 것이다. 다음과 같은 문제를 생각해 보자. * N개의 작업이 있다. 각 작업은 S_i 시간 동안 연속적으로 해야 하며, P_i + S_i 시간 내에 완수해야 한다. 작업이 돌아가는 시간을 최대화하여라.이 문제는 원래 문제랑 완전히 동일한 문제일까? 한번 문제의 조건들을 다시 잘 살펴보자. * S_i 시간 만큼 허기를 채울 수 있고 (작업을 돌릴 수 있고), P_i 시간 전에 시작해야 한다는 것은 P_i + S_i 시간 전에 끝내야 한다는 것과 동치이다. * 허기를 채울 수 있는 시간동안은 먹지 않는다. 즉 두 개의 작업을 동시에 하지 않는다. * 지금부터 음식을 먹는다 / 허기를 채우지 않으면 바로..
1. 회색 영역해당 데이터가 어떤 막대에 들어가게 되는지 판별할 수 있는 기준이 전부 문제에 적혀 있다. 기준에 따라 각 막대에 들어간 개수를 세주자. 가장 큰 값을 들고 있는 막대가 마지막 막대이니, 전체 막대의 개수를 알 수 있다. 막대 개수와 각 막대의 높이를 알면 문제에 적힌 대로 답을 계산할 수 있다. 2. 편집 거리문제 디스크립션이 많이 엉망이다 ㅠㅠ 다시 문제를 정리하면 다음과 같다. 초기 문자열 S와 최종 문자열 T가 주어진다. 입력 문자열은 처음에 S가 들어있고 출력 문자열은 비어있다. 입력 문자열의 맨 앞 글자를 삭제하고 출력 문자열의 맨 뒤에 글자를 추가하는 다양한 연산들이 주어진다. 연산 후에 입력 문자열은 비어야 하고, 출력 문자열은 T 여야 한다. 복사를 제외한 연산의 개수를 스..
- Total
- Today
- Yesterday