1. 생존자이 문제를 푸는 데 있어서 아주 중요한 아이디어는, 바로 이것이 스케줄링 문제라는 것을 발견하는 것이다. 다음과 같은 문제를 생각해 보자. * N개의 작업이 있다. 각 작업은 S_i 시간 동안 연속적으로 해야 하며, P_i + S_i 시간 내에 완수해야 한다. 작업이 돌아가는 시간을 최대화하여라.이 문제는 원래 문제랑 완전히 동일한 문제일까? 한번 문제의 조건들을 다시 잘 살펴보자. * S_i 시간 만큼 허기를 채울 수 있고 (작업을 돌릴 수 있고), P_i 시간 전에 시작해야 한다는 것은 P_i + S_i 시간 전에 끝내야 한다는 것과 동치이다. * 허기를 채울 수 있는 시간동안은 먹지 않는다. 즉 두 개의 작업을 동시에 하지 않는다. * 지금부터 음식을 먹는다 / 허기를 채우지 않으면 바로..
1. 회색 영역해당 데이터가 어떤 막대에 들어가게 되는지 판별할 수 있는 기준이 전부 문제에 적혀 있다. 기준에 따라 각 막대에 들어간 개수를 세주자. 가장 큰 값을 들고 있는 막대가 마지막 막대이니, 전체 막대의 개수를 알 수 있다. 막대 개수와 각 막대의 높이를 알면 문제에 적힌 대로 답을 계산할 수 있다. 2. 편집 거리문제 디스크립션이 많이 엉망이다 ㅠㅠ 다시 문제를 정리하면 다음과 같다. 초기 문자열 S와 최종 문자열 T가 주어진다. 입력 문자열은 처음에 S가 들어있고 출력 문자열은 비어있다. 입력 문자열의 맨 앞 글자를 삭제하고 출력 문자열의 맨 뒤에 글자를 추가하는 다양한 연산들이 주어진다. 연산 후에 입력 문자열은 비어야 하고, 출력 문자열은 T 여야 한다. 복사를 제외한 연산의 개수를 스..
1. The Postman경로에 대한 조건이 없을 때 이 문제는 방향 그래프에서 오일러 회로를 찾는 잘 알려진 문제이다. 오일러 회로는 모든 정점의 indegree와 outdegree가 같으며, 연결되어 있는 그래프라면 항상 존재한다. 이 문제의 그래프가 그러함을 가정하자 (그렇지 않다면 NIE).오일러 회로는 다음과 같은 재귀 함수 Rec(v) 로 선형 시간에 찾을 수 있다. 오일러 회로에 대해서는 복습을 위해 알고리즘만 간략히 적어두고 설명하지는 않겠다. * 정점 v에서 나가는 에지 e를 아무거나 찾고 제거 (사용한 에지들의 인덱스를 전역 변수 등에다 마킹해 놓고, vector에서 pop_back() 하면서 에지를 지워주자) * e의 반대편 끝점이 w라면, Rec(w) 호출 * Rec(w)가 종료되면..
- Total
- Today
- Yesterday