Software Engineering Note

문제: LUNCHBOX / 그리디(탐욕적인 방법) [해결책 / 후기] 힌트 - 먹는 시간이 오래 걸리는 사람을 먼저 처리한다. 입력이 A, B, C, D 네명에 대하여 다음과 같을 때 M: 4 2 6 1 E: 5 2 2 1 아래와 같이 시간 흐름을 그려보니 문제가 좀 명확해졌다. (총 14분의 시간이 걸림) 빨간 숫자는 식사가 끝나는 시간을 나타낸다. 1) 먹는 시간이 오래걸리는 사람 기준으로 내림차순으로 정렬하고 2) 전자렌지가 사용가능한 시점을 기준으로 시간을 측정하였다. 코드: https://github.com/xgate/algospot/blob/master/GREEDY/LUNCHBOX.cpp[출처] [AOJ 문제] Microwaving Lunch Boxes|작성자 DevMoon

문제: REPEATLESS / 경우의 수 [해결책 / 후기] 제한 시간이 10000ms(10초)라고 해서 만만하게 볼 문제가 아니었다. 처음에는 모든 수에 대해서 중복되는 수로 구성되어 있는지를 조사하였지만 여지없이 TLE .. OTL 그러다 해결책이 떠올랐다. 이 문제는, 10개의 숫자 중 n개의 수를 중복 없이 뽑는 문제와 비슷해보인다. (순열..!!) nPr = n! / (n-k)! (n개의 수에서 k개를 중복없이 뽑는 경우의 수) 그래서 해결책을 두 부분으로 나눌 수 있었다. 1) 순열을 이용해서 몇 자리 수인지 결정. n번째 수가 2자리 수인가? 3자리수인가?를 결정 하는 것이다.만약 정답이 3자리 수(100 < n < 1000)라면, 이 수는 적어도 10개의 수 중 2개를 뽑는 방법의 가지수보..

문제: ORDERING / 그래프 [해결책 / 후기] 유명한 문제인 것 같다. 위상정렬이라는 것도 처음 알게 되었다. 내용은 일의 순서를 정하는 것. 문제 해결을 위해서 반드시 위상정렬을 이용해야 하는건 아닌 듯하다. 다음과 깉이 생각해볼 수 있겠다. 1. 작업을 그래프로 추상화 * 각 작업은 그래프에서 하나의 정점(vertice)이 된다. * 작업 A를 마치고 B를 한다는 것은 A에서 B로 가는 간선(edge)을 긋는 것이다.* 이때 B의 입력차수는 1증가 한다. 입력 차수가 있다는 것은 이전에 처리해야할 작업이 있음을 의미한다. 2. 작업 순서 (1) 정점 사이에 간선을 긋는다.(2) 입력 차수가 0인 작업들을 "우선순위 큐"에 넣는다. 그냥 큐를 사용하면 오답이 되는데, 문제에 "사전순"이라는 조건..