Eunbi

이 프로그램에 출연하는 N명의 요리사는 각각 요리 실력 Pi와 인기도 Ci를 갖고 있다. 이 프로그램의 시청률은 그 날 요리 대결을 펼치는 두 요리사의 요리 실력과 인기도에 의해 결정된다. 남규는 총 N-1번의 경기 동안, 경기 순서와 승패를 잘 정해서 시청률의 총합을 최대화 → N명의 요리사가 있으면 N-1번의 경기를 치루고, 각 경기마다 시청률이라는 값을 지니고 있으며 각 경기들의 시청률의 합을 최대화하는 방법을 구해야 한다. N명의 요리사를 노드로 두고 N-1번의 경기를 간선으로 생각한다면 이는 트리의 형태가 되고, 최소(최대) 스패닝 트리를 구하는 문제로 볼 수 있다. → 어떤 경기(i번째 요리사 vs. j번째 요리사)가 이루어져야 최대 시청률합이 나오는지 알 수 있다. 하지만 어떤 순서로 경기를..

잘라내는 전선을 최소로 하여 꼬여 있는 전선이 하나도 없게 만들려고 한다. → 전선을 잘라내는데 모두 동일한 비용이 든다. 그리고 전선이 꼬여있지 않으려면 왼쪽 전봇대를 커지는 차례로, 연결된 오른쪽 전봇대의 숫자를 확인했을 때 앞서 나온 전봇대 숫자보다 커야 꼬여있지 않은 상태가 된다. 즉, 연결된 오른쪽 전봇대 숫자를 수열로 보고 이 수열에서 가장 길이가 긴 증가하는 부분수열을 구했을 때 가장 적은 비용으로 전봇대의 전선을 자르는 꼴이 된다. 가장 길이가 긴 증가하는 부분수열의 길이를 구하기 → 부분수열에 있는 원소를 구하는 것이 아닌 길이만 구하면 되는 문제이다. #include #include #include using namespace std; int N, x; vector arr; int ma..

Analysis Phase vs. Design Phase Analysis Phase 프로세스, 개념 등에 대한 질문에 초점을 맞춘다. what Analysis Artifacts Questions Answered Use cases domain processes, functional requirements 가 무엇인가 Domain model concepts, terms 이 무엇인가 System sequence diagrams system events & operation 이 무엇인가 Contracts system operations 이 하는 것이 무엇인가 Design Phase 시스템이 요구 사항을 어떻게 충족하는지에 대해 초점을 맞춘다. how 객체 관점에서 logical solution 을 강조 inte..

강한 북서풍이 불고 있다. 이 뜻은 동쪽과 남쪽 사이의 모든 방향으로 항해할 수 있다는 뜻이다. 북쪽이나 서쪽으로 항해하는 것은 불가능하다. → 조건1. 내가 갈 수 있는 섬의 x좌표는 나보다 크거나 같다. 조건2. 조건1을 만족할 때, 내가 갈 수 있는 섬의 y좌표는 나보다 작거나 같다. ==> (입력받을 때 y에 -1를 곱한다면) 조건1. 내가 갈 수 있는 섬의 x좌표는 나보다 크거나 같다. 조건2. 조건1을 만족할 때, 내가 갈 수 있는 섬의 y좌표는 나보다 크거나 같다. x, y 좌표를 오름차순으로 정렬했을 때, 하나씩 탐색하면 x 조건은 자동으로 성립한다. → 따라서 정렬하면 x 좌표값이 필요없게 됨. y 좌표만 보고 y 조건이 성립하는지 판단하는 문제로 변함. 하나씩 탐색을 했을 때 해당 y..