구사과

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)가 종료되면..

1. 작은 새각각의 쿼리가 그다지 연관성이 없어보이니, 그냥 K가 고정됐다 치고 각 문제를 독립적으로 풀어보자. 결국 쿼리당 O(n)에 해결하면 되니 말이다. O(n^2) 동적 계획법은 다음과 같이 어렵지 않게 할 수 있다. dp(i) = 1번에서 i로 오는 데 필요한 최소의 힘든 점프 수라 하면, 그 전 위치를 j라 했을 때에 대한 식으로 동적 계획법 표를 채울 수 있다. 기본적으로 dp(j)를 가져올 수 있지만, 만약 H_j Ei라는 것은, 어떠한 시간에 Si에 있다가, 그 후에 Ei에 있고, 그 다음에 Si에 다시 돌아와야 한다는 것을 뜻한다. 그렇다면, 최소 Ei -> Si로 한번은 거꾸로 가는 것이 필요하다는 것을 뜻한다. (거꾸로 간다는 것은 돌아온다는 것을 함의한다.) 이들을 [Ei, Si]..