주저리
이코테 책을 통한 개념 학습 보다 문제를 집중적으로 단권화 해서 접근하기 보다, 부분적으로 부족하고 필요하다고 생각해 왔던 부분만을 중심으로 정리하고 문제를 접근하고 해결하는 과정을 거치며 필요한 역량을 갖추었다고 생각했다.
하지만, 이러한 생각은 착각이었던 것 같다. 진짜 코테를 여럿 겪으며, 실질적인 개념이 차근차근 바르게 정립되어 있는 것과 더불어 수학 문제, 구현 문제 등 기본 개념의 정립이 필요하다는 생각을 하게 되었다.
이에 따라, 이코테의 개념과 문제를 빠르게 짚고 정리할 필요와 해당 책의 기본 개념에 나오지 않고 추후에 심화 문제에서도 나올 내용일지라도, 필요한 기본 개념으로 판단되는 내용들을 함께 정리하고자 한다.
특히, 그리디 알고리즘 문제의 개념은 분명 어렵지 않다.
어디든 적용해 볼 수 있다.
다만, 정합하지 않을 수 있다.
속도가 빠를 수는 있지만 최적해가 아닐 수 있으며,
유형화된 문제도 있는가 하면 실제 문제들을
구현과 정렬의 난이도를 높여 해당 문제들의 소요시간을 늘리는 전략을 사용한다.
즉, 기본 개념과 더불어 기본적인 피지컬에 해당하는 구현에 관한 익숙도가 무엇보다 중요한게 그리디 알고리즘 문제의 특징이다.
필자의 경우, 현재 프로그래머스와 더불어, 백준을 통해 문제를 풀고 있다. 두 개의 플랫폼을 함께 사용하다 보니, 문제를 접하고 접근하고 해결하는 과정의 Tip이 늘어나는 것 같다. 하지만 실제 문제 상황의
제한된 시간 내의 문제에 관한 빠른 캐치와 구현에서는
아직 만족할 만한 성과를 내고 있지 못하다.
해당 부분의 성과를 성공적으로 낼 수 있기 위한 반복을 목표로
이번 같은 정리를 준비했다.
Greedy 알고리즘의 기본 문제
[1] 거스름돈 문제는 어딜가나 만나기 쉬운 그리디 문제 중 하나다.
하지만 이 문제의 유형 중 하나가 그리디의 유형에 해당하는 거지.
반드시 그리디로 풀어야 하는 것은 아니다.
다만, 그리디로 풀었을 때 최고의 성능을 낼 수 있다.
이러한 이유는 더 다른 변수의 선언도 없거니와,
탐색의 경우도 필요한 만큼만 할 수 있기 때문이다.
이러한 특징 속에서 그리디의 속성을 뽑아내는 다양한 언어들이 있다.
- 다음의 값에 영향을 끼치지 않는 독립적인 값이어야 한다.
- ex) 500원, 100원은 800원이라는 값이 있을 때 독립적으로 서로의 선택이 다른 선택에 영향을 끼치지 않는다.
- ex) 500원, 400원, 100원의 경우 800원에서 500원을 선택하면 400원을 2개 선택하는 결과에 영향을 끼친다. 위와 같은 경우는
그리디 알고리즘을 적용할 수 없는 경우다.
게다가 위의 알고리즘의 구현은 상당히 간단하다.
기본적으로 최초의 나는 while에 뺄셈으로 구현하는 경우가 많았다.
지금도 해당 방법이 먼저 떠오른다.
하지만 효율성을 조금 더 고려하고 책에서도 나오는 방법을 고민해 본다면 나눗셈과 나머지를 통한 값의 변환을 통한 방법을 추천한다.
문제에 관한 간단한 설명. 1260원이라는 거스름돈이 있다.
해당 거스름돈을 500원, 100원, 50원 10원의 거스름돈을 활용해(해당 거스름돈은 무한히 있다.) 가장 적은 량의 거스름돈을 주고자 하는 코드를 작성하시오.
java code
public class ex {
public static void main(String[] args) {
int n = 1260;
int count = 0;
int[] coin_types = {500,100,50,10};
for(int coin : coin_types){
count += n/coin;
n%=coin;
}
System.out.println(count);
}
}python code
n = 1260
count = 0
coin_types = [500,100,50,10]
#//가 정수 나눗셈 기호구나
for coin in coin_types:
count += n//coin
n %= coin
print(count)책이 파이썬으로 되어 있기도 하고, 파이썬을 아예 모르지도 않아서
함께 작성하게 되었다. 다만, 온전히 파이썬을 이해하고 있지는 않아서
//의 기호가 정수 나눗셈을 실행한다는 걸 알게 되었다.
해당 부분을 최초에 이해하지 못하고 Java의 주석처리로 오인했던
웃픈 기억이 있지만, 이런 부분들이 하나하나 쌓이고 이해력을 높일 수 있지 않을까 싶다.
자Java Code가 확연히 길다.
하지만, 두 언어는 근본적으로
컴파일 언어,인터프립터 언어라는 근본적인 차이를 가지고 있다.
물론 앱 개발하면 속도는 사실 그렇게 엄청난 변수를 만들지 않을 수도 있다. 워낙 크다 보니...
파이썬이 경쟁력을 갖추는 간결성과 넓은 확장성에도 불구하고
여전히 느리다는 단점이 크기 떄문에 파이썬을 현재에는 보조적인 수단으로 생각하고 있다.
다만, 코테 또는 계속 배워야 하는 개발자라는 업을 할 사람이다 보니
그도 게을리 할 생각은 없기에 위와 같이 모든 예제에 자바와 파이썬 코드를 앞으로 추가하겠다.
위의 문제들을 제외하고도 총 3가지의 예제 문제가 첨부되어 있다.
하지만, 이 문제들을 보기 전에 정렬에 관한 이야기를 먼저 할 필요가 있다.
그리디와 정렬.
사실 정렬은 거의 모든 알고리즘 문제에서 필수처럼 작용하는 기법이라고 생각된다.
배열의 부분합과 같은 영역이 아니라면,
이분탐색과 같은 문제도 정렬을 하지 않은 상태에서는 작동을 보장할 수 없다.
즉, 정렬이 매우 주요한데, 이 정렬을 사용하는 방법이 익숙하지 않으면, Java의 경우 구현의 속도 및 코테에서 좋은 성적을 거두기가 어렵다.
이와 관련해서는 스케쥴링 문제라고 불리어지는 문제들을 살펴볼까 한다.
예제는 백준. 프로그래머스 문제 각각 하나씩을 선별했다.
정렬 방법은 3가지를 소개한다. 이때 클래스를 별도로 선언하는 경우는
문제와 별도의 예시로 제공한다.
단, 클래스를 별도로 선언하고 Comparable<T> 만 선언하는 이유는
해당 인터페이스의 자바 내에서의 기능이 유일하기 때문에
조금 더 수월하기 때문임을 미리 밝힌다.
람다의 경우는 문제 실제 코드를 통해 공유한다.
Comparator의 사용과 , Comparable의 사용 두 가지 모두를 기술했다.
해당 코드의 경우 파이썬은 추후에 추가할 수 있도록 하겠다.
0.별도의 클래스를 통한 Comparable의 선언
public class Person implements Comparable<Person> {
private String name;
private int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public int getAge() {
return age;
}
@Override
public int compareTo(Person otherPerson) {
if (this.age < otherPerson.age) {
return -1;
} else if (this.age > otherPerson.age) {
return 1;
} else {
return 0;
}
}
}위와 같은 기본 구현이 있다.
실질적으로는 해당 오버라이드 역시 이렇게 작성한다.
@Override마저도 기능적으로는 아무것도 하지 않기 때문에
작성하지 않아도 된다.
//내림차순
@Override
public int compareTo(Person otherPerson) {
return this.age - otherPerson.age;//오름차순
@Override
public int compareTo(Person otherPerson) {
return otherPerson.age - this.age;다만 위의 예시와 같이. 정렬을 하는 것이 Class를 새로 정의하고
사용하는데 있어서는 필요하다.
일반적으로 클래스를 새로 정의하는 이유는 위와 같이 String, int와
같은 동일하지 않은 타입의 정보를 하나의 정보로 묶어서 관리할 필요가 있을 때 사용한다. 게다가 이를 정렬하는 기준을 Comparator 를 구현함으로써 이루어진다.
위와 같은 과정의 이해가 어렵다면 댓글을 달아주시면 관련한 부분을 포스팅 하도록 하겠다.
다음으로는 실전적으로 사용하는 람다를 활용한 코드를 살펴 보자.
적어도 문제 내용을 먼저 리딩하기를 추천한다.
해당 코드의 설명과 비교는 학습적인 측면이 강하다.
1.백준 1951번 회의실 배정
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
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, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
if (o1[1] == o2[1]) return o1[0] - o2[0];
return o1[1] - o2[1];
}
});
int count = 1;
int end = meetings[0][1];
// 종료가 빠른순 선택
for (int i = 1; i < n; i++)
if (end <= meetings[i][0]) {
count++;
end = meetings[i][1];
}
System.out.println(count);
}
}import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
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, (o1, o2) ->{
if (o1[1] == o2[1]) return o1[0] - o2[0];
return o1[1] - o2[1];
}
);
int count = 1;
int end = meetings[0][1];
// 종료가 빠른순 선택
for (int i = 1; i < n; i++)
if (end <= meetings[i][0]) {
count++;
end = meetings[i][1];
}
System.out.println(count);
}
}2.프로그래머스 Lv2. 요격 시스템
우선 이 문제의 경우, 지문이 길다.
하지만 스케쥴링한다.는 유형의 개념을 접해 봤다면! 해당 문제의 실질적인 코딩이 그렇게 어렵지는 않다.
추가적으로 개구간에 관한 내용이 나오는데
해당 부분에 관한 이해도 있으면 좋을 것 같아 블로그를 가지고 왔다.
특히나, 긴 지문의 문제 연습이 중요한 것 같다. 여러가지 개념이 나오는 경우도 있고,
이런 지문에 단련된다면 실제 코테에서 강점을 가질 수 있지 않을까 싶다.
개인적으로 반환 하는 결과값의 확인을 먼저 하는 걸 추천한다.
이를 통해, 문제에 필요한 내용과 최종 결과에 대한 생각을 정리할 수 있기 때문인데, 이 문제의 경우 개구간이라는 개념도 같이 넣어놔서 기본적으로 수학에 관한 내용도 꾸준히 학습해 주세요. :) 같은 느낌이다.
import java.util.Arrays;
import java.util.Comparator;
class Solution {
public int solution(int[][] targets) {
Arrays.sort(targets, new Comparator<int[]>() {
public int compare(int [] o1, int[] o2){
if(o1[1] == o2[1])
return o1[0] - o2[0];
return o1[1] - o2[1];
}
});
int end = targets[0][1];
int answer = 1;//최초 요격
for(int[] target : targets)
if(end <= target[0]){
end = target[1];
answer++;
}
return answer;
}
}import java.util.Arrays;
class Solution {
public int solution(int[][] targets) {
Arrays.sort(targets, (o1, o2) -> {
if(o1[1] == o2[1]) return o1[0] - o2[0];
return o1[1] - o2[1];
});
int end = targets[0][1];
int answer = 1;//최초 요격
for(int[] target : targets)
if(end <= target[0]){
end = target[1];
answer++;
}
return answer;
}
}
두 문제의 코드가 데칼 코마니처럼 같은 걸 알 수 있다.
하지만, 실제 코딩에서는 Comparator를 활용하는 걸 추천한다.
이를 통해 할 수 있는 간결성이 구현에 더 이점이 있기 때문!
여기까지 정렬에 관한 내용을 알아 보았고,
다시 Greedy 알고리즘을 기본 문제 3가지를 살펴 보자.
3문제 모두 쉬운 유형에 속한다.
또한 자바와 python의 경우 형태가 다르다.
자바는 함수형으로 입력값이 예제의 값으로 주어지는 형태로 했으며
Python의 경우 입력값을 받아야 하는 형태로 책에 기술된 내용을 바탕으로 했다.
입력값을 주는 경우가 실제 테스트에서는
지속적으로 값을 넣어야 하는 불편함 때문에 이와 같은 방법을 선택했다.
1번 문제 큰 수의 법칙
특히 1번 문제의 경우, 백준2869번 달팽이는 올라가고 싶다와도 유사한 문제다.
위 문제는 수학적으로 문제를 해석해야지만 풀리고 예시 상황만 주어지는 것이 아니니
해당 문제를 통해 직접 연습해 보는 걸 추천한다.
문제를 간단하게 설명하면, 이 문제의 경우 첫째 줄과 두 번째 줄로 구성이된다.
각각의 숫자는 띄어쓰기를 통해 구분되며,
첫 번째 줄에는 3개의 정수가 주어진다. 첫 번째 정수 N은 2번째 줄에 나오는 숫자의 개수.
두 번째 정수 M은 총 더해야 하는 숫자의 개수이며, 세 번째 정수 K는
이때 정수를 반복할 수 있는 횟수다.
두 번째 줄에는 N 만큼의 수의 정수가 공백으로 구분되어 주어진다.
(단, 같은 숫자가 다른 위치에 있는 것은 서로 다른 수로 반복되지 않는 것으로 여긴다.)
이 때, 두 번째 줄에 주어진 수를 활용하여 M번의 덧셈을 실행하여 최대의 정수가 되게 만드는 것이 문제다.
위 문제의 경우, 반복의 횟수 K와 더불어, 전체 더할 수 있는 회수 M 2가지를 고려해야 한다.
서적에서는 단순한 풀이 방법과 수학적 풀이 방법 2가지를 제공하고 있다.
단순한 풀이의 경우, 정말 단순하게 구현한 것이기 때문에 큰 수에 대응하지 못한다.
이러한 풀이는 문제를 통과하더라도, 좋은 코드를 고민하고 생각해야 하는 입장에서 좋은 방식은 아니다.
이에 따라, 수학적 풀이만을 우선적으로 공유한다.
Java Code
import java.util.Arrays;
public class 큰수의법칙_수학적접근 {
private static void solution(int[] arr,int M, int K){
int answer = 0;
Arrays.sort(arr);
int max = arr[arr.length-1];
int next = arr[arr.length-2];
int count = (M/(K+1))*K;
count += M % (K+1);
answer += count *max;
answer += (M-count) * next;
System.out.println(answer);
}
public static void main(String[] args) {
int[] arr = {5,8,3};
solution(arr,8,3);
arr = new int [] {2,4,5,4,6};
solution(arr,8,3);
}
}Python Code
n,m,k = map(int, input().split())
data = list(map(int,input().split()))
data.sort()
first = data[n-1]
second = data[n-2]
count = int(m/(k+1))*k
count += m % (k+1)
result = first * count
result += (m - count) * second
print(result) 2번 문제 숫자 카드 게임
문제 설명
여러 개의 숫자가 적힌 카드가 M*N의 형태로 주어진다.
첫째 줄에는 M N이 공백을 구분해 주어지며
이하의 줄에는 M번만큼 N 길이의 숫자들이 주어진다.
이때, 각 줄의 가장 큰 수를 제외하고 가장 작은 수 중 가장 큰 수를 구하시오.위의 문제만 보면 조금 내용이 이상해 보일 수 있다.
예시를 보면
2 4
7 3 1 8
3 3 3 4라고 할 때
출력값은 3이된다.
각 줄의 가장 큰 수는 8과 4이며 해당 줄에서 가장 큰 수를 제외하고 가장 작은 수는 각각 1, 3이다.
이 중 가장 큰 수이기 때문에 3이 되는 형태가 문제의 유형이다.
이처럼 문제가 이해가 되지 않으면 예제를 보는 것도 도움이 될 수 있지만,
예제 자체가 함정이 될 수도 있으니 꼭 지문의 바른 이해가 중요하다!
Java Code
import java.util.Arrays;
public class 숫자카드게임 {
//행에서의 최솟값이 최대인 값을 구하는 문제!
private static void solution(int[][] board){
int max = Integer.MIN_VALUE;
for(int[] i : board){
max = Math.max(max, Arrays.stream(i).min().getAsInt());
}
System.out.println(max);
}
public static void main(String[] args) {
int[][] borad = {{3,1,2},{4,1,4},{2,2,2}};
solution(borad);
}
}Python Code
n,m = map(int,input().split())
result = 0
for i in range(n):
data = list(map(int, input().split()))
min_value = min(data)
result = max(result, min_value)
print(result)3번 문제 1이 될 때까지
문제설명
N과 K라는 숫자가 주어질 때,
이 N은 두 가지를 할 수 있다.
- 1을 뺄 수 있다.
- N이 K로 나누어 떨어질 때 K로 나눌 수 있다.
이때, 1이 되는 최소의 회수를 구하시오.
이처럼 입력값은 N과 K가 공백을 나누어 첫째줄에 주어지며, 이를 풀면 되는 문제다.
이 문제도 간단한 일반 구현과 수학적 구현이 있는데, 이 문제는 오히려 수학적 구현이
더 일반적으로 생각나기 쉽다고 개인적으로 생각하기에 해당 문제 역시 효율적인 수학적 코드를 공유한다.
이 문제는 많이 나누면 되는 간단한 문제다. 1을 뺀다는 부분만 존재하기 때문에 쉬워진다.
가령,3을 뺀다던지 +1도 할 수 있다던지와 같은 조건들이 더 추가 되었다면 더 어려운 문제가 되었을 것이다.
Java Code
public class 일이될때까지 {
//K의 배수로 만드는 문제.
private static void solution(int N, int K){
int answer = 0;
while(N > 1){
int need =0;
if(N % K == 0){
N /= K;
need += 1;
}else{
need = N % K;
N -= need;
}
answer+=need;
}
System.out.println(answer);
}
public static void main(String[] args) {
solution(25,5);
solution(17,4);
solution(1000000000,3);
}
}Python Code
n,k = map(int, input().split())
result = 0
while True:
target = (n//k) * k
result += (n-target)
n = target
if n < k:
break
result += 1
n //= k
result += (n-1)
print(result)위와 같은 정말 기본적인 문제들만이 책의 초반에는 소개되고 있기 때문에
앞에 시간을 들여, 조금 더 어렵고 난이도 있는 문제를 첨부했다.
그리디의 심화에서는 어떤 깊이의 차이가 있는지 살펴볼 대목이다.
