궤도

문제 풀이 말도 안되는 상상이지만 이런 생각을 해보자. 모든 도시의 주유소에 차와 연결할 수 있는 아주 긴 호스가 있다고 말이다. 다만 특정 주유소와 호스를 연결하려면 그 주유소까지 가야할 것이다. 그럼 저 자동차의 이동과정을 살펴보자. 일단 출발하기 전 주유를 해야한다. 다음 주유소까지 2km이니 2km 만큼의 기름을 첫번째 주유소에서 주유한다. => 5x2 = 10 두번째 주유소에 도착했다. 지난 주유소보다 가격이 저렴해 여기서 충전하기로 한다. 보라색 호스를 연결하고 3km 만큼의 기름을 주유한다. => 2x3 = 6 세번째 주유소에 도착했다. 연결된 호스의 주유소보다 가격이 비싸 이전 주유소에서 호스를 통해 기름을 받아오기로 했다. => 2x1 = 2 네번째 주유소에 도착했다. 도착지에 왔으니 기..

문제 풀이 풀이는 간단한데, 코드 작성이 까다로울 수 있는 문제이다. 먼저 예제 입력1에 대해 괄호를 치면 어떻게 될까? 55-(50+40)이 될 것이다. 그렇다면 이번엔 55-50+40+10-45+22 뭐 이런식이 있다고 치자. 여기에 괄호를 치면 55-(50+40+10)-(45+22)가 될 것이다. 눈치챘겠지만, 마이너스를 기준으로 양옆에 괄호를 치면 최솟값이 나온다. 그럼 마이너스 하나하나 찾아서 괄호를 쳐야할까? 그런 귀찮은 짓을 할 이유는 없다. 55-(50+40+10)-(45+22) 이 식은 55-(50+40+10+45+22) 이렇게 바꾸어도 똑같은 식이다. 즉, 마이너스가 처음 등장하는 지점을 기준으로 A - B의 형태를 만들어 A, B의 식을 각각 더한뒤 그 둘을 빼주면 최솟값이 나온다. ..

문제 풀이 운영체제때 배운 디스크 스케쥴링 알고리즘들이 떠오르는 문제이다. 거기까지 가지 않더라도 문제를 읽어보면 대충 직감적으로 아~ 이거 인출시간 제일 덜 걸리는 사람 순으로 정렬하면 되겠네~ 할 것이다. 인출시간이 덜 걸리는 순으로 정렬했다고 치고 각 사람마다 기다리고 인출하는데 걸리는 총 시간은 어떻게 될까? 이 식을 보고 무언가 감이 온다면 그대로 코드로 작성하면 된다. 혹시 아직 감이 안왔을 수도 있으니...기다리는 사람의 배열을 arr이라고 하고 걸리는 총 시간을 sum이라고 하면 sum = arr[0]*N + arr[1]*(N-1) + arr[2]*(N-2) + ... + arr[N-1]*1 이다. 소스코드 #include #include using namespace std; int arr..

문제 풀이 개인적인 비하인드 때문에 나혼자 140만원 문제라고 부르는 회의실 배정 문제이다. 이 문제에서 중요한 것은 시작하는 시각일까 끝나는 시각일까? 당연히 끝나는 시각이다. 0시에 시작해서 12시에 끝나는 것보다야 3시에 시작해서 4시에 끝나는게 회의실을 좀 더 효율적으로 사용할 수 있는 방법일 것이다. 그렇다면 끝나는 시각이 작은 순서로 정렬한다고 치고 같은 때에 끝나는 회의가 2개 이상 있다면 어떤 회의를 우선으로 해야할까? 끝나는 시각이 같고, 시작하는 시각이 다른 다음과 같은 회의 A, B가 있다. 회의 A를 먼저 투입했을땐, 회의 A가 끝난 뒤 회의 B를 진행할 수 있다. 회의 B를 먼저 투입했을땐, 회의 B가 끝난 뒤에 회의 A를 진행할 수 없다. 이미 4시인데 2시부터 해야했을 회의 A..

문제 풀이 거스름돈 문제는 여러가지가 있지만 이 문제처럼 특수한 경우에는 그리디 알고리즘을 적용할 수 있다. 그 특수한 경우가 무엇일까? 바로 모든 동전들의 가치가 배수관계일 때이다. 만약 가치가 1, 7, 10원인 동전 3개가 있고 14원을 거슬러 줘야 한다고 하자. 그리디 알고리즘을 적용하면 10원 1개, 1원 4개 총 5개의 동전을 사용하지만 최적해는 7원 2개 총 2개의 동전을 사용하는 것이다. 아무튼 이 문제는 모든 동전들의 가치가 배수관계이니 맘편하게 그리디 알고리즘을 적용하자. 가장 가치가 큰 동전부터 가치가 작은 동전 순서로 거스름돈과 비교하면 된다. 소스코드 #include using namespace std; int coin[11]; int greedyCoin(int N, int K) ..