반응형
다들 연휴는 잘 보내셨나요?
오늘은 죽지도 않고 돌아온 알고리즘 스터디 3주차 블로깅입니다.
알고리즘 스터디 3주차 주제는 그리디(Greedy) 알고리즘인데요,
그리디 알고리즘이 뭐냐면~
💡 그리디 알고리즘(탐욕법, Greedy Algorithm) 이란?
Greedy가 탐욕이라는 뜻인데요 최적의 값을 구해야 하는 상황에서 사용되는 근시안적인 방법론으로 각 단계에서 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘입니다.
이때, 항상 최적의 값을 보장하는 것이 아니라 최적의 값의 근사한 값을 목표로 합니다.
주로 문제를 분할 가능한 문제들로 분한한 뒤 각 문제들에 대한 최적해를 구하고 이를 결합하여 전체 문제의 최적해를 구하는 경웨 주로 사용됩니다.
💡 근시안적 방법론이란?
- 단기적인 목표에 초점을 맞춘 전략적 접근 방법입니다.
- 현재 문제 해결에 집중하며, 장기적인 전망보다는 즉각적인 성과를 우선시합니다.
💡 근사 알고리즘(Approximation Algorithm)이란?
- 최적의 해를 구하기 어려운 문제에서 최적에 가까운 해를 구하는 알고리즘입니다.
- 항상 최적해를 보장하진 않지만, 실용적인 해결책을 빠르게 찾는 데 유용합니다.
💡 그리디 알고리즘의 핵심 속성
1. 탐욕 선택 속성 (Greedy Choice Property)
- 각 단계에서 가장 좋은 선택을 하는 것이 전체적으로도 최적의 결과를 낳는 경우에 성립합니다.
2. 최적 부분 구조 (Optimal Substructure)
- 전체 문제의 최적해가, 부분 문제의 최적해로 구성될 수 있는 경우에 해당합니다.
- 즉, 문제를 나눠 각각 해결하고 이를 합치면 전체 해답이 됩니다.
💡그리디 알고리즘 문제 풀이 단계
- 문제의 최적해 구조 결정
- 선택 절차(Selection Procedure) 정의
- 선택 수행
- 적절성 검사(Feasibility Check)
- 조건 불충족 시 해당 해 제외
- 모든 선택이 완료되면 해답 검사(Solution Check)
- 조건 만족 시 해답으로 인정
💡 단계별 개념 정리
1. 선택 절차 (Selection Procedure)
- 현재 상황에서 가장 이상적인 선택을 수행합니다.
- 한번 선택된 항목은 다시 변경되지 않습니다.
2. 적절성 검사 (Feasibility Check)
- 선택한 항목이 문제 조건을 만족하는지 확인합니다.
- 조건을 만족하지 않으면 제외합니다.
3. 해답 검사 (Solution Check)
- 최종적으로 선택된 항목들이 전체 문제의 조건을 만족하는지 확인합니다.
- 조건을 만족할 경우 해답으로 인정됩니다.
💡 그리디 알고리즘 vs 동적 계획법(DP)
비교 항목그리디 알고리즘 (Greedy)동적 계획법 (Dynamic Programming)
| 접근 방식 | 각 단계에서 최적 선택 | 작은 문제 해를 저장하여 활용 |
| 성립 조건 | 탐욕 선택 속성, 최적 부분 구조 | 중복 부분 문제, 최적 부분 구조 |
| 중복 계산 처리 | X | O (메모이제이션 사용) |
| 특징 | 빠르지만, 항상 최적 해를 보장하진 않음 | 느릴 수 있으나 항상 최적 해 가능 |
| 적용 예시 | 최소 동전 개수, 활동 선택 문제 등 | 피보나치 수열, 배낭 문제 등 |
라고 합니다~
이제 3주차 문제를 풀어볼게요.
1. 회의실 배정
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 회의 개수 입력 받기
int n = sc.nextInt();
// 각 회의의 시작 시간과 종료 시간을 저장할 2차원 배열 선언
int[][] meetings = new int[n][2];
// 회의 정보 입력 받기
for (int i = 0; i < n; i++) {
meetings[i][0] = sc.nextInt(); // 시작 시간
meetings[i][1] = sc.nextInt(); // 끝나는 시간
}
// 회의를 끝나는 시간 기준으로 정렬
// 끝나는 시간이 같으면 시작 시간을 기준으로 정렬
Arrays.sort(meetings, (a, b) -> {
if (a[1] == b[1]) {
return a[0] - b[0]; // 끝나는 시간이 같을 경우 시작 시간 기준으로 오름차순
}
return a[1] - b[1]; // 끝나는 시간 기준으로 오름차순 정렬
});
// 선택된 회의 수를 저장할 변수
int count = 0;
// 마지막으로 선택된 회의의 끝나는 시간을 저장할 변수
int lastEndTime = 0;
// 정렬된 회의 리스트를 순회하면서 회의 선택
for (int i = 0; i < n; i++) {
// 현재 회의의 시작 시간이 마지막으로 선택한 회의의 끝나는 시간보다 같거나 크면 선택 가능
if (meetings[i][0] >= lastEndTime) {
lastEndTime = meetings[i][1]; // 현재 회의의 끝나는 시간을 갱신
count++; // 선택한 회의 수 증가
}
}
// 결과 출력: 겹치지 않게 선택할 수 있는 회의의 최대 개수
System.out.println(count);
}
}
문제 설명
- 하나의 회의실에서 여러 개의 회의를 겹치지 않도록 최대한 많이 배정해야 하는 문제입니다.
- 각 회의는 시작 시간과 종료 시간이 주어지며 끝나는 시간과 다음 시작하는 시간이 같아도 두 회의는 겹치지 않은 것으로 간주합니다.
- 목표는 회의실을 사용할 수 있는 최대 회의 수를 구하는 것입니다.
코드 로직 설명
- 먼저 입력된 회의 개수를 바탕으로 이차원 배열을 만들어 각 회의의 시작 시간과 종료 시간을 저장합니다.
- 그 다음 회의들을 정렬합니다. 정렬 기준은 종료 시간이 빠른 순서이며, 종료 시간이 같을 경우 시작 시간이 빠른 순서입니다.
- 종료 시간이 빠른 회의를 먼저 선택해야 이후 회의를 더 많이 넣을 수 있기 때문입니다.
- 정렬이 끝나면 회의를 하나씩 확인하며 이전에 선택한 회의의 종료 시간 이후에 시작하는 회의만 선택합니다.
- 이를 위해 마지막으로 선택한 회의의 종료 시간을 저장하는 변수를 사용합니다.
- 조건에 맞는 회의를 선택할 때마다 개수를 하나씩 증가시키고 종료 시간 변수도 현재 회의의 종료 시간으로 갱신합니다.
- 마지막으로 선택한 회의의 총 개수를 출력하면 됩니다.
2. 잃어버린 괄호
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 수식 입력 받기
String expression = sc.nextLine();
// 수식을 '-' 기호를 기준으로 나누기
// '-'를 기준으로 괄호를 묶으면 전체 값을 최소화할 수 있음
String[] parts = expression.split("-");
// 첫 번째 부분은 괄호를 씌울 수 없기 때문에 무조건 더해줌
int result = sum(parts[0]);
// 두 번째 부분부터는 괄호로 묶어 전체를 한꺼번에 빼줌
for (int i = 1; i < parts.length; i++) {
// 각 파트를 '+' 기준으로 나누고 합한 다음 result에서 빼기
result -= sum(parts[i]);
}
// 계산 결과 출력
System.out.println(result);
}
// 문자열을 '+' 기준으로 나눈 후 각 숫자를 모두 더한 값을 반환하는 함수
private static int sum(String str) {
// '+' 기호를 기준으로 나누기
String[] tokens = str.split("\\+");
int total = 0;
// 나뉜 각 숫자를 정수로 바꾸어 더해줌
for (String token : tokens) {
total += Integer.parseInt(token); // 문자열 숫자를 정수로 변환 후 누적
}
return total; // 전체 합 반환
}
}
문제 설명
- 수식에는 숫자와 +, - 기호만 있으며 괄호는 모두 지워진 상태입니다.
- 세준이는 괄호를 다시 적절히 넣어 전체 수식의 값을 최소로 만들고자 합니다.
- 연산은 입력 순서대로 진행되며 연산자 우선순위는 고려하지 않습니다.
- 목표는 괄호를 활용해 수식의 계산 결과가 최소가 되도록 하는 것입니다.
코드 로직 설명
- 입력으로 주어진 수식을 문자열로 읽습니다.
- 수식을 - 기호를 기준으로 나누어 문자열 배열로 저장합니다.
- 첫 번째 덩어리는 괄호로 묶을 수 없기 때문에 내부의 + 연산을 모두 수행해 더합니다.
- 두 번째 덩어리부터는 각 덩어리 안에 있는 숫자들을 전부 더한 뒤 전체 결과에서 빼줍니다.
- 위 과정을 반복해 식 전체의 값을 계산합니다.
- 계산된 최종 결과를 출력합니다.
3. 동전 0
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 1. N: 동전 종류 수, K: 목표 금액 입력
int N = sc.nextInt();
int K = sc.nextInt();
// 2. 동전 가치 배열 선언
int[] coins = new int[N];
// 3. 동전 가치 입력 받기
for (int i = 0; i < N; i++) {
coins[i] = sc.nextInt();
}
int count = 0; // 필요한 동전 개수의 합
// 4. 큰 동전부터 사용하기 위해 뒤에서부터 순회
for (int i = N - 1; i >= 0; i--) {
if (coins[i] <= K) {
// 현재 금액 K에서 해당 동전을 몇 개 쓸 수 있는지 계산
int use = K / coins[i];
count += use; // 사용한 동전 개수 누적
K -= use * coins[i]; // 사용한 금액만큼 차감
}
}
// 5. 결과 출력: 최소 동전 개수
System.out.println(count);
}
}
문제 설명
- 준규는 N종류의 동전을 가지고 있고 각 동전은 매우 많이 가지고 있습니다.
- 모든 동전은 그 가치가 앞의 동전보다 항상 배수이며 오름차순으로 정렬되어 있습니다.
- 목표는 이 동전들을 사용해 정해진 금액 K원을 만들 때 필요한 동전 개수의 최솟값을 구하는 것입니다.
- 각 동전은 필요한 만큼 사용할 수 있고 반드시 K원을 정확히 만들어야 합니다.
코드 로직 설명
- 먼저 동전의 종류 수 N과 만들고자 하는 금액 K를 입력받습니다.
- 각 동전의 가치를 배열에 차례로 저장합니다.
- 가장 큰 동전부터 확인하며 K보다 작거나 같은 동전을 찾습니다.
- 해당 동전을 최대한 많이 사용하여 K에서 그만큼을 차감합니다.
- 이 과정을 반복하면서 K가 0이 될 때까지 동전을 선택하고 동전 개수를 누적합니다.
- 최종적으로 누적된 동전 개수를 출력합니다.
끗~~~~~~~~~~!
반응형
'WINK-(Web & App) > 알고리즘 스터디' 카테고리의 다른 글
| [2025 1학기 알고리즘 스터디] 신지은 #3주차 (0) | 2025.05.07 |
|---|---|
| [2025 1학기 알고리즘 스터디] 박현빈 #3주차 (0) | 2025.05.07 |
| [2025 1학기 알고리즘 스터디] 김민재 #3주차 (0) | 2025.05.07 |
| [2025 1학기 알고리즘 스터디] 김규현 #3주차 (0) | 2025.05.05 |
| [2025 1학기 알고리즘 스터디] 남윤찬 #3주차 (0) | 2025.05.02 |
