그리디 알고리즘
- 그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것만을 고르는 방법
- 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 한다.
- 그리디 해법은 그 정당성 분석이 중요하다. 그리디 해법이 정당한 이유는 드물게 중요한데, 이를 추론할 수 있는 경우가 많다.
정당성 분석이란 그리디 알고리즘을 사용했을 때, 최적의 해를 구할 수 있는지를 확인하는 것이다.
예제 1. 거스름돈
- 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이 최적의 해를 보장한다.
- 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로, 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.
- 이처럼 큰 단위의 동전이 항상 작은 단위의 배수이므로, 작은 단위의 동전들을 종합해 다른 해가 나올 수 없다.
import java.util.Scanner;
// n 원을 거슬러줘야 하는 경우
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int count = 0;
int[] coinTypes = {500, 100, 50, 10};
for (int i = 0; i < 4; i++) {
count += n / coinTypes[i];
n %= coinTypes[i];
}
System.out.println(count);
}
}실행 결과
1260
6위와 같은경우는 정당성이 성립 한다.
왜냐면 하위 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.
큰 단위가 항상 작은 단위의 배수가 아닌 경우에는 정당성이 성립하지 않는다.
이 때 거스름돈 시간 복잡도는 O(K)이다. K는 동전의 종류이다.
구현
- 구현은 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다.
- 구현 문제는 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제를 뜻한다.
- 풀이를 위한 아이디어는 간단한데 소스코드로 옮기기 어려운 문제를 뜻한다.
구현 유형 예시는 다음과 같다.
- 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제
- 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제
- 적절한 라이브러리를 찾아서 사용해야 하는 문제
일반적으로 알고리즘 문제에서의 2차원 공간은 행렬(Matrix)의 의미로 사용된다.
- 행렬이란 행과 열로 이루어진 직사각형 모양의 배열을 의미한다. 액셀 표와 같은 형태이다.
- 가로축을 행이라고 하고, 세로축을 열이라고 한다. 아래쪽으로 내려갈수록 행이 증가하고, 오른쪽으로 갈수록 열이 증가한다.
예시
상하좌우
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// N을 입력받기
int n = sc.nextInt();
sc.nextLine(); // 버퍼 비우기
String[] plans = sc.nextLine().split(" ");
int x = 1, y = 1;
// L, R, U, D에 따른 이동 방향
int[] dx = {0, 0, -1, 1};
int[] dy = {-1, 1, 0, 0};
char[] moveTypes = {'L', 'R', 'U', 'D'};
// 이동 계획을 하나씩 확인
for (int i = 0; i < plans.length; i++) {
char plan = plans[i].charAt(0);
// 이동 후 좌표 구하기
int nx = -1, ny = -1;
for (int j = 0; j < 4; j++) {
if (plan == moveTypes[j]) {
nx = x + dx[j];
ny = y + dy[j];
}
}
// 공간을 벗어나는 경우 무시
if (nx < 1 || ny < 1 || nx > n || ny > n) continue;
// 이동 수행
x = nx;
y = ny;
}
System.out.println(x + " " + y);
}
}출력 결과
5
R R R U D D
3 4시각
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// H를 입력받기
int h = sc.nextInt();
int count = 0;
for (int i = 0; i <= h; i++) {
for (int j = 0; j < 60; j++) {
for (int k = 0; k < 60; k++) {
// 매 시각 안에 '3'이 포함되어 있다면 카운트 증가
if (String.valueOf(i).contains("3") || String.valueOf(j).contains("3") || String.valueOf(k).contains("3")) {
count++;
}
}
}
}
System.out.println(count);
}
}출력 결과
5
11475위 예제의 유형을 완전 탐색 문제라고 한다.
완전 탐색은 모든 경우의 수를 주저 없이 다 계산하는 해결 방법을 의미한다.
이처럼 완전 탐색은 문제를 해결할 수 있는 가장 무식한 방법이지만,
답을 찾을 수 있다는 점에서 가장 확실한 방법이다.
그러나 완전 탐색을 사용하면 시간 복잡도가 O(N^3)이 되어서 문제를 풀 수 없는 경우도 있다.
왕실의 나이트
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 현재 나이트의 위치 입력받기
String inputData = sc.nextLine();
int row = inputData.charAt(1) - '0';
int column = inputData.charAt(0) - 'a' + 1;
// 나이트가 이동할 수 있는 8가지 방향 정의
int[] dx = {-2, -1, 1, 2, 2, 1, -1, -2};
int[] dy = {-1, -2, -2, -1, 1, 2, 2, 1};
// 8가지 방향에 대하여 각 위치로 이동이 가능한지 확인
int result = 0;
for (int i = 0; i < 8; i++) {
// 이동하고자 하는 위치 확인
int nextRow = row + dx[i];
int nextColumn = column + dy[i];
// 해당 위치로 이동이 가능하다면 카운트 증가
if (nextRow >= 1 && nextRow <= 8 && nextColumn >= 1 && nextColumn <= 8) {
result += 1;
}
}
System.out.println(result);
}
}출력 결과
a1
2- 문자열 정렬
import java.util.Arrays;
public static String reString(String str){
String[] strArr = str.split("");
Arrays.sort(strArr);
StringBuilder result = new StringBuilder();
int sum = 0;
for(String s : strArr){
if(s.matches("[0-9]")){
sum += Integer.parseInt(s);
}else{
result.append(s);
}
}
return result.toString() + sum;
}출력 결과
reString("K1KA5CB7")
-> "ABCKK13"
rocoli에요