알고리즘90 Algorithm - 침몰하는 타이타닉(그리디) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [침몰하는 타이타닉] 유럽에서 가장 유명했던 유람선 타이타닉이 침몰하고 있다. 이 유람선에는 N명의 승객이 타고 있다. 구명보트를 타고 탈출해야 하는데 타이타닉에 있는 구명보드는 2명 이하로만 탈 수 있으며, 보트 한 개에 탈 수 있는 총 무게도 M kg 이하로 제한되어 있다. N명의 승객 몸무게가 주어졌을 때, 승객 모두가 탈출하기 위한 구명보트의 최소 개수를 출력하는 프로그램을 작성하시오. *입력 설명 첫 번째 줄에 자연수 N(5 ≤ N ≤ 1000)와 M(70 ≤ M ≤ 250)이 주어진다. 두 번째 줄에 N개로 구성된 몸무게 수열이 주어진다. (단, 몸무게.. 2021. 11. 22. Algorithm - 창고 정리(그리디) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [창고 정리] 창고에 상자가 일렬의 가로방향으로 쌓여 있다. 만약 가로의 길이가 7이라고 하면, 아래의 그림과 같이 1열은 높이가 6으로 6개의 상자가 쌓여 있고, 2열은 3개의 상자, 3열은 9개의 상자가 쌓여 있고 높이는 9라고 읽는다. 창고 높이 조정은 가장 높은 곳에 상자를 가장 낮은 곳으로 이동하는 것을 말한다. 가장 높은 곳이나 가장 낮은 곳이 여러 곳이면 그 중 아무곳이나 선택하면 된다. 위의 그림을 1회 높이 조정하면 아래와 같아진다. 창고의 가로 길이와 각 열의 상자 높이가 주어진다. m회의 높이를 조정한 후 가장 높은 곳과 가장 낮은 곳의 차이를.. 2021. 11. 19. Algorithm - 씨름선수 선발(그리디) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [씨름선수 선발] 현수는 씨름 감독이다. 현수는 씨름 선수를 선발하기 위해 공고를 냈으며, N명의 지원자가 지원을 했다. 현수는 각 지원자의 키와 몸무게 정보를 알고 있으며, 현수는 씨름 선수의 선발 원칙을 다음과 같이 정했다. "다른 모든 지원자와 일대일 비교를 하여 키와 몸무게 중 적어도 하나는 크거나, 무거운 지원자만 뽑기로 했습니다." 만약, A라는 지원자보다 키도 크고 몸무게도 무거운 지원자가 존재한다면 A지원자는 선발되지 않는다. *입력 설명 첫 번째 줄에 지원자의 수 N(5 ≤ N ≤ 50)이 주어진다. 두 번째 줄부터 N명의 키와 몸무게 정보가 차례.. 2021. 11. 19. Algorithm - 회의실 배정(그리디) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [회의실 배정] 한 개의 회의실이 있는데 이를 사용하고자 하는 n개의 회의들에 대하여 회의실 사용표를 만들려고 한다. 각 회의에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대 수의 회의를 찾고자 한다. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작할 수 있다. 위의 조건을 모두 만족시키는 프로그램을 작성하시오. *입력 설명 첫 번째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 두 번째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 .. 2021. 11. 19. Algorithm - 마구간 정하기(결정 알고리즘) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [마구간 정하기] N개의 마구간이 수직선상에 있다. 각 마구간은 x1, x2, x3, ... , xN의 자표를 가지며, 마구간의 좌표가 중복되는 일은 없다. 현수는 C마리의 말을 가지고 있는데, 이 말들은 서로 가까이 있는 것을 싫어한다. 각 마구간에는 한 마리의 말을 넣을 수 있고, 가장 가까운 두 말의 거리가 최대가 되도록 마구간에 말을 배치하고 싶다. C마리의 말을 N개의 마구간에 배치했을 때, 가장 가까운 두 말의 거리가 최대가 되며 그 최대 값을 출력하는 프로그램을 작성하시오. *입력 설명 첫 번째 줄에 자연수 N(3 ≤ N ≤ 200,000)과 C(2 .. 2021. 11. 19. Algorithm - 뮤직 비디오(결정 알고리즘) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [뮤직 비디오] AAA레코드에서는 불세출의 가수 BBB의 라이브 동영상을 DVD로 마들어 판매하려고 한다. DVD에는 총 N개의 곡이 들어가는데, DVD에 녹화할 때에는 라이브에서의 순서가 그대로 유지되어야 한다. 순서가 바뀌는 것을 가수 BBB가 매우 싫어한다. 즉, 1번 노래와 5번 노래를 같은 DVD에 녹화하기 위해서는 1번과 5번 사이의 모든 노래도 같은 DVD에 녹화해야 한다. 또한, 한 노래를 쪼개서 두 개의 DVD에 녹화하면 안된다. AAA레코드 입장에서는 이 DVD가 팔릴 것인지 확신할 수 없기 때문에 이 사업에 낭비되는 DVD를 가급적 줄이려고 한.. 2021. 11. 19. 이전 1 ··· 8 9 10 11 12 13 14 15 다음
