1. 그리디(Greedy)

영문 greedy는 '탐욕스러운', '욕심 많은'이라고 번역이 되는데, 말 그대로 단순하고 탐욕적이며 근시안적으로 여러가지 해법 중 가장 좋은 방법만 선택하는 것을 그리디 알고리즘이라고 한다. 그 순간에 최적인 것만 선택하여 진행하며 그 선택으로 인해 앞으로 나타날 결과들에 대한 것은 고려하지 않는다. 이러한 방식은 앞의 선택이 뒤의 선택에 영향을 주지 않아야 하며, 부분 집합들의 최적해가 전체 집합에 대해서도 최적의 해가 되어야 한다는 조건이 있다. 이런 조건에 의해서 그리디 알고리즘으로 풀이를 할 경우 엄밀한 증명, 다시 말해 해당 그리디 풀이가 정당한지 검토할 수 있어야 한다.

2. 그리디를 위하여

그리디 문제들을 풀어나가기 위해서는 가장 좋은 풀이법을 선택해야 한다고 했는데 가장 좋은 풀이법이란 대체 무엇인가? 가장 좋은 풀이를 위해서는 풀이를 하기 위한 도구를 많이 가지고 있어야 유리하다. 예로, 등산을 할 때 왼쪽길은 많은 사람들이 다녀 길이 평탄하고 다른 길은 가시밭길에 장애물도 많다면 평탄한 길을 선택하는 것이 최선을 선택겠지만, 슬리퍼를 신고 왼쪽길을 가는 것보다는 등산화를 신고 가는 것이 더 좋을 것이다. 이처럼 풀이를 하는 언어의 문법이나 수학적 지식과 모듈, 그리고 내장 함수들을 더 많이 활용할 수 있다면 더 유리하다는 말이다. 같은 말을 반복하는 것이지만 여러 유형의 문제들을 접해보면서 여러가지의 아이디어를 얻어내고 그 아이디어들과 풀이 도구를 활용할 수 있어야 하기에 많은 문제 풀이를 해가며 실력을 키워야 하는 까다로운 문제이기도 하다.

3.1.1 문제

자연수 n(2 < n < 100.000)이 입력되면 n이 소수이면 1을 아니면 0을 반환하는 프로그램을 완성하시오.

3.1.2 풀이

쉽게 만날 수 있는 소수 판별 문제다. 1과 자신을 제외한 어떤 수로도 나누어지지 않는 수다. 약간의 아이디어로 풀 수 있을 것이다.
반복문으로 2부터 시작하여 하나씩 증가하며 n을 나누어 나머지가 0이 되면 소수가 아니기에 0을 출력하고 멈추면 될 것이고, 반복문이 끝까지 진행하여 끝났다면 1을 출력하면 될 것이다.

n = int(input())
for i in range(2, n): # 2부터 자기 자신의 수 전까지 반복문 실행
    if n % i == 0:
        print(0)
        break # 나누어 떨어졌다면 else 구문으로 가지 못하도록 break한다.
else:
    print(1)

for~else 를 활용하여 반복문 도중 나누어 떨어지면 소수가 아니기에 0을 출력하고 멈추면 된다. for문이 정상적으로 끝까지 진행되었다면 소수이므로 else 구문이 작동하여 1을 반환한다.

3.2.1 문제

자연수 n(2 < n < 100.000)이 입력되면 n 이하의 모든 소수를 출력하는 프로그램을 작성하시오.

3.2.2 풀이

한 단계 까다로워진 문제다. 생각해보면 한 단계만 늘었을 뿐이다. 1번의 문제가 하나의 숫자 n이 주어진 반면, 지금은 숫자 n까지의 모든 수를 판별하면 된다. 반복문을 통해 2부터 n까지 위의 1번 문제를 n번 반복하면 된다.

n = int(input())
for i in range(2, n + 1): # 자연수 n까지 확인해야 하기에
    for j in range(2, i): # 해당 i가 할당될 때마다 2부터 i전까지 나누어서 소수인지 판별한다.
        if i % j == 0:
            break
    else:  # for문은 반복가능한 객체가 하나라도 있어야 하는데, 범위(rangre(2, 2))가 반복가능하지 않기에 바로 else구문으로 내려온다.
        print(i)# 2도 소수이기에 바로 else구문으로 내려오도록 한다.
입력 : 20
출력 : 2 3 5 7 11 13 17 19 

과연 위의 풀이는 합당한가?
n이 주어지는 범위는 10만으로 2중 for문이 진행되면 빅오 표기법에 따라 2차 시간으로 n^2이 되어 연산횟수가 100억회가 되어 시간 초과를 받게 된다.
그래서 체크 배열을 이용하여 소수가 아닌 수를 제외시켜나가며 최종적으로 소수만 남았을 때 남은 소수만 출력하게 만들도록 하는 '에라토스테네스의 체'라는 풀이 방법을 써보자.

3.2.3 에라토스테네스의 체

예로 2라는 수의 배수로 진행되는 4, 6, 8... n까지의 수들은 모두 2의 배수이므로 소수가 아니다. 3의 배수인 6, 9, 12...또한 소수가 아니다. 이런 일련의 규칙을 사용하여 체크 배열을 설정함으로써 n까지의 모든 수를 2중 반복문을 사용하여 하나하나 보는 것이 아니라, 작은 수부터 시작하는 배수들을 먼저 확인한 후 소수를 '체'에 걸리내는 식으로 미리 확인을 해 놓는다. 이러한 방법이 바로 고대 그리스 수학자 에라토스테네스라가 발견했다고 하여 붙여진 에라토스테네스의 체다.

n = int(input())
chArr = [0] * (n + 1) # n까지 확인해야 함으로 +1을 한다.
for i in range(2, n + 1):# 소수 중 가장 작은 수부터 진행
    if chArr[i] == 0:# 아래의 반복문에서 'i'가 '이전 i'의 배수라면 1로 체크가 되어있기에 if 조건문의 실행문을 실행하지 않는다.
        print(i) # 이전 수들의 배수가 아니기에 소수라고 판별하여 출력(가장 작은 수부터 시작했기에 가능한 방법)
        for j in range(i * 2, n + 1, i):
            chArr[j] = 1
입력 : 20
출력 : 2 3 5 7 11 13 17 19 

그리디 적으로 보았을 시 소수 판별, 특히 에라토스테네스의 체를 이용하여 2부터 소수를 판별해가는 방법은 합당하다고 볼 수 있다. 하지만 문제에서 시작점과 끝점을 따로 지정하여 출력하라고 했을 때 어떤 방법을 쓸 것인가? 예로 '10부터 시작하여 100까지의 수 중에서 소수를 출력하라'라고 한다면 위의 코드로는 10이 바로 소수로 책정되기에 오류가 날 수 있다. 아니면 '10'부터 시작이지만 '2'부터 시작해놓은 후 '10'부터 출력해도 가능하다. 여기에서 더 연산 횟수를 줄일 방법은 없는지 다음 챕터에 계속하겠다. 에라토스테네스의 체에는 하나의 아이디어가 더 들어가 있다.