본문 바로가기

알고리즘 문제147

[알고리즘 문제] 백준2217 - 로프 이 문제는 주어진 로프를 사용해서 들어올릴 수 있는 최대 중량의 값을 구하는 문제이다. 입력으로 각 로프가 들어올릴 수 있는 최대 중량이 주어지고, 출력은 이 로프들을 사용하여 들어올릴 수 있는 최대 중량을 출력하면 된다. 이 문제의 조건은 다음과 같다. 1. 각 로프가 들어올릴 수 있는 무게는 다르다. 2. k개의 로프를 사용하여 w중량을 들어올린다면, 각각의 로프에는 모두 고르게 w/k만큼의 중량이 걸리게 된다. 3. 로프를 모두 사용하거나, 임의로 몇개의 로프를 골라서 사용해도 된다. 문제해결 아이디어는 다음과 같다. 1. 먼저 입력받은 중량값을 정렬한다. 이는 최대중량을 가진 로프부터 검사하기 위해서 이다. 2. 들어올릴 수 있는 중량이 가장 큰 로프를 list에 넣고, 그 다음 로프와 협력햇을 .. 2019. 6. 5.
[알고리즘 문제] 백준2875 - 대회or인턴 이 문제는 여학생,남학생들로 만들 수 있는 팀의 최대값을 구하는 문제이다. 팀을 만드는데 조건은 다음과 같다. 1. 팀의 구성원은 여학생2명, 남학생1명이다. 2. 학생들 중 k명은 반드시 인턴쉽 프로그램에 참여해야 한다. 3. 인턴쉽에 참여하는 학생은 대회에 참여하지 못한다. 이번 문제는 그리디알고리즘을 사용했는데, 아이디어는 다음과 같다. 1. 현재 학생들로 만들 수 있는 최대팀을 구한다. 2. 남은 학생들이 인턴쉽에 참여하는 학생들을 만족하는지 검사한다. 3. 만족하면 현재 팀의 개수를 출력하고, 그렇지 않으면 팀의 개수를 줄이면서 그 만큼의 학생수를 충원하면서 인턴쉽에 참여하는 학생들의 수를 만족할 때 까지 반복한다. import java.util.*; public class Main { publ.. 2019. 6. 5.
[알고리즘 문제] 백준1931 - 회의실배정 이번 문제는 회의실배정문제로 그리디 알고리즘을 사용하여 풀 수 있는 문제입니다. 문제는 생각보다 어렵지 않습니다. N개의 회의와 각각의 회의의 시작시간과 종료시간이 있습니다. 다음 아래의 조건을 만족하도록 회의 시간표를 짜야하는데, 여기서 최대 사용할 수 있는 회의수를 출력하는 것입니다. 1. 회의진행시간이 겹치면 안된다. 2. 회의는 한번 시작하면 중간에 중단될 수 없다. 3. 회의의 시작시간과 끝나는 시간이 같을 수도 있다, 이는 시작하자마자 끝나는 것으로 간주한다. 예를들어서, 현재 회의 시간이 [ 1,4 ]이고 다음 회의시간이 [ 2,7 ]이라면, 이는 시간표에 등록될 수 없습니다. 하지만 [4, 8], [5, 5]인 경우는 시간표에 등록할 수 있겠죠. 왜냐하면 회의의 시작시간이, 현재 진행중인 .. 2019. 6. 4.
[알고리즘 문제] 중복없는 구간 import java.util.*; public class Main { static int arr[]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); arr = new int[n]; for (int i = 0; i < n; i++) { arr[i] = sc.nextInt(); } int start = 1; // start에서는 성공 int end = n+1; // end에서는 실패 while (start + 1 < end) { int mid = (start + end) / 2; if (check(mid)) { // mid 길이에서 중복없이 가능 한지 start = mid; .. 2019. 5. 17.

티스토리툴바