728x90
반응형
[알고리즘] 그리디 알고리즘(백준 11047, 1541, 11399, 1931, 1026 -Java)
알고리즘 공부를 계속 미루는 제 자신을 보고 이대로는 안되겠다 싶어 😇
본격적으로 코딩테스트를 준비(+알고리즘 공부) 해보려고 합니다.
물론 혼자하면 작심삼일이 될거 같아
무료 Do it! 알고리즘 코딩테스트 with JAVA - 인프런 | 강의
강의 커리큘럼에 맞춰 공부해보자!!
[무료] Do it! 알고리즘 코딩테스트 with JAVA - 인프런 | 강의
IT기업 코딩테스트 대비를 위한 [자료구조 및 알고리즘 핵심이론 & 관련 실전 문제 풀이 강의] 입니다. - JAVA 편 -, - 강의 소개 | 인프런
www.inflearn.com
그리디 알고리즘
그리디 알고리즘은 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘 입니다.
현재 상태에서 최선을 선택하다 보면 결국에는 최선의 결과가 나올것이다 라고 가정을 합니다.
그리디 알고리즘 핵심 이론
1) 해 선택: 현재 상태에서 가장 최선이라고 생각되는 해를 선택
2) 적정설 검사: 현재 선택한 해가 전체 문제의 제약 조건에서 벗어나지 않는지 검사
3) 해 검사: 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사(해결 못하면 1번으로 돌아간다.)
백준 11047
11047번: 동전 0
대표적인 그리디 알고리즘 문제 입니다.
풀이
public class Quiz11047_2 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
// 동전 종류
int n = Integer.parseInt(st.nextToken());
// 동전으로 만들어야 하는 금액
int k = Integer.parseInt(st.nextToken());
// 동전 배열
Integer[] coin = new Integer[n];
for(int i = 0; i < coin.length; i++) {
coin[i] = Integer.parseInt(br.readLine());
}
int count = 0;
int mock = 0;
// 가장 단위가 큰 동전부터 탐색
for(int i = n-1; i >= 0; i--) {
// 목표 금액에서 동전으로 나눈다.
mock = k / coin[i];
// 몫이 0 이면 동전(coin[i])을 사용할 수 없다.
if(mock != 0) {
// 몫 만큼 해당 동전을 사용한다.
count += mock;
// 목표 금액(k)에서 동전(coin[i])으로 나눈 나머지로 목표금액(k)을 변경한다.
k = k % coin[i];
}
}
System.out.print(count);
br.close();
}
}백준 1541
1541번: 잃어버린 괄호-를 만나면 그 이후에 등장하는 문자열은 다 빼면 최소 숫자가 됩니다.^^
풀이
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = br.readLine();
// -를 만나기 전에는 다 더하고, -를 만나면 이후에는 다 빼면 된다.
// -앞 문자열, -뒤 문자열로 나눔
// 55+10-50+40-30 -> [50+10, 55+40, 30]
String[] strArr = str.split("-");
int result = 0;
// -를 만나면 크기가 2이상인 배열이 된다.
for(int i = 0; i < strArr.length; i++) {
int temp = mySum(strArr[i]);
// 첫 문자열은 더함(-를 만나기 전 문자열)
if(i == 0) result += temp;
// 이후 문자열은 뺀다(이후 문자열은 -를 만났기 때문에 빼야한다.)
else result -= temp;
}
System.out.print(result);
}
private static int mySum(String s) {
int sum = 0;
// +를 기준으로 문자열을 나눈다.
// 50+40 -> [50, 40] -> 90
String[] temp = s.split("[+]");
for(String str : temp) {
sum += Integer.parseInt(str);
}
return sum;
}
}백준 11399
11399번: ATM
오름차순으로 정렬한 뒤 배열의 합을 구하고 그 배열의 합을 계속 더하면 해결할 수 있는 문제 입니다.
for(int i = 0; i < time.length; i++) {
sum += time[i]; // 배열의 합을 구함
result += sum; // 배열의 합의 합을 구함
}
풀이
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
int[] time = new int[n];
for(int i = 0; i < n; i++) {
time[i] = Integer.parseInt(st.nextToken());
}
// 오름차순 정렬
Arrays.sort(time);
int result = 0;
int sum = 0;
for(int i = 0; i < time.length; i++) {
sum += time[i]; // 배열의 합을 구함
result += sum; // 배열의 합의 합을 구함
}
System.out.print(result);
br.close();
}
}백준 1931
처음에는 loop 2개를 사용해서 문제를 해결했으나, 시간초과가 발생했습니다.. ㅠ
백준 1931번 : 회의실배정 - JAVA 자바
회의 종료 시간 기준으로 오름차순 정렬을 해야 해결할 수 있습니다.
최대한 많은 회의를 하기위해서는 종료시간이 빨라야 하기 때문 입니다.
서로 겹치지 않는 활동에 대해 종료시간이 빠르면 더 많은 선택을 할 수 있습니다.
✅ 이때 주의해야할 점이 있습니다.
바로 종료시간이 같을때 입니다.
예를들어 아래와 같은 입력이 있다고 합시다.
7 7
3 7
1 2종료시간으로만 오름차순 정렬하면 다음과 같습니다.
1 2
7 7
3 7정답은 (1, 2) -> (3, 7) -> (7, 7) 이렇게 3이어야 합니다.
하지만 종료시간만으로 오름차순 정렬 한다면
(1, 2) -> (7, 7) 이렇게 2가 됩니다…. (3, 7)이 선택이 안되는 것 이죠..
따라서 종료시간이 같을 때는 시작시간으로 기준으로 오름차순 정렬해야 합니다.
풀이
public class Quiz1931 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 회의 수
int n = Integer.parseInt(br.readLine());
/**
* 각 회의 시간이 겹치면 안됨
* 회의실 사용할 수 있는 최대 갯수
*/
List<List<Integer>> table = new ArrayList<>();
List<Integer> list = new ArrayList<>();
for(int i = 0; i < n; i++) {
table.add(new ArrayList<>());
}
// 회의 시간표 저장
for(int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
table.get(i).add(start);
table.get(i).add(end);
}
// 회의 종료 시간 기준으로 오름차순 정렬
Collections.sort(table, new Comparator<List<Integer>>() {
@Override
public int compare(List<Integer> o1, List<Integer> o2) {
// 종료시간이 같을 경우에는 회의 시작시간 기준으로 오름차순 정렬
if(o1.get(1) == o2.get(1)) {
return Integer.compare(o1.get(0), o2.get(0));
} else {
return Integer.compare(o1.get(1), o2.get(1));
}
}
});
// 첫 회의를 배정한다.
// 첫 회의의 끝나는 시간과 다음 회의 시작 시간 비교
int count = 1;
// 선두 회의의 끝나는 시간
int endTime = table.get(0).get(1);
for(int i = 1; i < n; i++) {
// 후발 회의의 시작 시간
int startTime = table.get(i).get(0);
if(endTime <= startTime) {
count++;
// 선두 회의의 끝나는 시간
endTime = table.get(i).get(1);
}
}
System.out.print(count);
br.close();
}
}백준 1026
B배열은 재정렬 하면 안된다고해서 우선순위 큐를 사용해서 문제를 풀었습니다.
풀이
public class Quiz1026 {
public static void main(String[] args) throws IOException {
// S = A[0] × B[0] + ... + A[N-1] × B[N-1]
// S 값이 최소가 되게 A를 정렬
// S가 최소가 되기 위해서는 B의 최댓값과 A의 최솟값을 곱하면 된다.
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 배열의 크기
int n = Integer.parseInt(br.readLine());
// 배열 A
Integer[] A = new Integer[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 0; i < n; i++) {
A[i] = Integer.parseInt(st.nextToken());
}
// 배열 A 오름차순 정렬
Arrays.sort(A);
// 배열 B
// B 배열은 재정렬하면 안됨.
Queue<Integer> queue = new PriorityQueue<>(Comparator.reverseOrder());
st = new StringTokenizer(br.readLine());
for(int i = 0; i < n; i++) {
queue.add(Integer.parseInt(st.nextToken()));
}
int result = 0;
int i = 0;
while (!queue.isEmpty()) {
result += A[i] * queue.poll();
i++;
}
System.out.print(result);
br.close();
}
}백준 13305
13305번: 주유소
다음 주유소의 거리만큼 주유를 하다가 가격이 싼 주유소를 찾으면 남은 거리만큼 주유를 하면 됩니다.
풀이
public class Quiz13305 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 도시 갯수
int city = Integer.parseInt(br.readLine());
// 도로 길이
// 편의를 위해 도로 마지막은 0을 넣음 따라서 배열의 크기를 city와 동일하게 한다.
StringTokenizer st = new StringTokenizer(br.readLine());
long[] roadLen = new long[city - 1];
for(int i = 0; i < roadLen.length; i++) {
roadLen[i] = Long.parseLong(st.nextToken());
}
// 기름 가격
st = new StringTokenizer(br.readLine());
long[] price = new long[city];
for(int i = 0; i < price.length; i++) {
price[i] = Long.parseLong(st.nextToken());
}
// 처음에는 무조건 기름을 넣어야 한다.
// 기름이 비싼 곳에서 적게 넣고
// 기름이 싼곳에 많이 넣으면 된다.
// 1. 기름이 싼곳을 찾을 때 까지 다음 주유소까지 거리만큼 기름을 넣는다.
// 2. 기름이 싼곳을 찾으면 남은 목표 거리만큼 기름을 넣는다.
long result = 0;
long min = price[0];
for(int i = 0; i < roadLen.length; i++) {
// 현재 주유소 기름값이 이전 주유소 기름값 보다 저렴하면
if(min > price[i]) {
// 제일 저렴한 기름값 변경
min = price[i];
}
// 저렴한 가격으로 주유하고 다음 주유소로 간다.
result += (min * roadLen[i]);
}
System.out.print(result);
br.close();
}
}728x90
반응형
'0 + 알고리즘(Algorithm)' 카테고리의 다른 글
| [알고리즘] 이분 그래프(백준 1707, 1953, 12893 -Java) (0) | 2023.03.25 |
|---|---|
| [알고리즘] 그래프 기본 개념 찍먹하기 -Java (2) | 2023.03.25 |
| [알고리즘] 이진 탐색(백준 1920, 10815, 10816, 1654, 2805, 2110 -Java) (0) | 2023.03.24 |
| [알고리즘] 너비 우선 탐색(BFS: Breadth First Search, 백준 2178, 1697, 12851, 1012 -Java) (0) | 2023.03.19 |
| [알고리즘] 깊이 우선 탐색(DFS: Depth First Search, 백준 11724, 2606, 11724, 2667 -Java) (0) | 2023.03.16 |