문제 - N개의 회의를 모두 진행할 수 있는 최소 회의실 개수 구하기 - 각 회의는 시작 시간과 끝나는 시간이 주어짐 - 한 회의실에서 동시에 두 개 이상의 회의가 진행될 수 없음 - 회의는 한 번 시작되면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있음 - 회의의 시작 시간은 끝나는 시간보다 항상 작음 해결방법 회의 시작시간이 순서없이 입력되고 있기 때문에 회의 시간을 입력 받을 때, 시작 시간을 기준으로 정렬을 해주었다. 시작 시간을 기준으로 정렬을 하고 회의실을 하나씩 배정하면서 끝나는 시간을 기록해두었고, 끝나는 시간보다 시작 시간이 큰 회의가 있다면 해당 회의실에 다음 회의로 일정을 잡으면 되기 때문에 haveMeetingRoom 변수로 들어갈 수 있는 회의실..
문제 - 매우 큰 도화지에 자를 대고 선을 그음 - 자의 한 점에서 다른 한 점까지 그음 - 선을 그을 때에는 이미 선이 있는 위치에 겹쳐서 그릴 수도 있는데, 여러 번 그은 곳은 한 번 그은 곳의 차이를 구별할 수 없음 - 그려진 선(들)의 총 길이를 구하는 프로그램 작성 해결방법 주어진 점들을 x(출발점)가 작은 순으로 정렬을 해준다. (이때, x가 같다면 y가 작은 순으로 정렬할 수 있도록 했다.) 모든 점들의 리스트에서 한 선씩 받아오는데 이전에 그었던 선의 범위 안에 속하면 계산하지 않고, 범위에 속하면서 더 그을 수 있으면 더 그은 부분만을 계산해주고 아예 범위를 벗어나서 선을 그은 부분은 그 길이만큼 계산할 수 있도록 코드를 구성하였다. 처음에 범위를 제대로 특정하지 않고 이전 y값과 비교하..
문제 - 오늘부터 N+1일째 되는 날 퇴사하기 위해, 남은 N일 동안 최대한 많은 상담을 하려 함 - 각각의 상담은 상담을 완료하는데 걸리는 기간 T[i]와 상담을 했을 때 받을 수 있는 금액 P[i]로 이루어짐 - 상담을 적절히 했을 때, 얻을 수 있는 최대 수익을 구하기 해결방법 DP 배열을 만들어 퇴사 날까지 얻을 수 있는 수익을 최대로 저장하면서 계산했다. 최대값을 저장해두면서 각 날짜에 상담을 했을 때, 얻을 수 있는 수익을 구하고 저장하면서 문제를 해결했다. 코드 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader..
문제 - 축구를 하기 위해 모인 사람은 총 N명 - 스타트 팀과 링크 팀으로 사람들을 나눠야 함 - 두 팀의 인원수는 같지 않아도 되지만, 한 명 이상이어야 함 - 각 사람에게 번호를 1 ~ N까지 배정하고 능력치를 조사함 - S[ij]는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치 - 팀의 능력치는 팀에 속한 모든 쌍의 능력치의 합 - 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려 함 해결방법 부분집합으로 팀을 구성할 수 있는 인원들을 뽑은 뒤, 각 팀별로 능력치를 합산하고 차이를 비교해 정답을 구할 수 있도록 구성하였다. 부분집합을 구하는 코드는 아래 포스팅을 참고하면 좋을 것 같다. [알고리즘] 부분집합(Subset) 부분집합(Subset) 개념 - 집합에 포..
문제 - 수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수 구하기 - 예를 들어, S = [5, 1, 2]라면 구할 수 있는 부분 수열은, 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5) - 만들 수 없는 가장 작은 자연수는 4 해결방법 아무 것도 안 뽑는 경우부터, 전체 다 뽑는 경우까지의 조합의 경우를 다 더한 부분 집합을 이용하여 주어진 수로 만들 수 있는 수들의 조합을 구하였다.(subset 함수) 부분 집합을 구할 때, 뽑힌 수들을 모두 더하여 리스트를 만들어둔 뒤 정렬하고, 차례로 하나씩 검사하여 만들 수 없는 가장 작은 자연수를 찾을 수 있도록 하였다. (setResultCheck 함수) 코드 import java.io...
문제 - 현재 3대 운동 중량 500 - 하루가 지날 때마다 중량이 K만큼 감소 - N개의 서로 다른 운동 키트 보유 - 운동 키트들은 각각의 중량 증가량을 가지고 있으며, 사용할 때마다 즉시 중량이 증가 - 운동 기간동안 항상 중량이 500 이상으로 유지가 되도록 N일간의 운동 플랜을 세우고 이 경우의 수를 출력 해결방법 운동 키트 적용 순서를 순열을 이용하여 정하고, 적용 순서가 정해지면 하루하루 중량이 감소하고 운동을 통해 보충한 중량 증가량을 계산하여 500 이상을 유지하는지를 확인할 수 있도록 하였다. permutation 함수를 이용하여 순열을 통해 운동 키트 적용 순서를 짰고, N개(운동 키트 개수)만큼 순서를 짰다면 중량을 계산하여 조건에 따라 경우의 수를 계산하였다. 코드 import j..
문제 - 1번 방에서 출발해서 n번 방으로 도착이 목표 - 갈 수 있다면 Yes, 갈 수 없다면 No 출력 - 각 방 안에는 번호가 붙은 문이 있을 수 있고, 각 문은 해당하는 번호의 방으로 통함 - 방 안에는 레프리콘이나 트롤이 있을 수도 있음 - 레프리콘이 있는 방에 들어가면 소지금이 일정 양 이하로 떨어지지 않게 채워줌 (일정량 미만이면 그만한 양이 되도록 채워주고, 이상이면 그대로 둠) - 트롤이 있는 방에 들어가면 일정량의 통행료를 지불해야 함 해결방법 방문한 곳을 체크하면 각 방을 DFS로 탐색하여 목표하는 방까지 탐색하였다. 문제에 제시된 조건에 따라 레프리콘과 트롤을 만났을 때, 조건을 처리해주었으며 소지금이 바닥나면 해당 함수를 탈출할 수 있게 구현하였으며, 재귀적으로 탐색할 수 있도록 ..