[이.코.테] 그리디 (1) -- 숫자 카드 게임

 

 

그리디 알고리즘이란?

어떠한 문제가 있을 때, 단순 무식하게, *탐욕적으로 푸는 알고리즘.

(탐욕적: 현재 상황에서 가장 좋은 것만 고르는 방법)

현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

 

즉, 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형.

단, 많은 유형을 접해보고 문제를 풀어보며 훈련을 해야한다.

창의력이 중요함!

 

그리고 문제 풀이를 위해 해법을 찾을 때, 이것이 정당한지 검토해야 답을 도출할 수 있다.

문제 유형 파악이 어렵다면 그리디 알고리즘을 의심하고,

오랜 시간 고민해도 그리디 알고리즘으로 해결방법을 찾을 수 없다면, 그때는 다른 알고리즘 방법을 떠올려보다.

 

 

 

# 여러 개의 숫자 카드 중 가장 높은 숫자가 쓰인 카드 한장을 뽑는 게임
# 행을 선택 -> 가장 숫자가 작은 카드 뽑음
# 행마다 가장 작은 숫자를 뽑지만, 최종적으로는 가장 높은 숫자를 뽑아야 한다.
# 즉, 각 행의 가장 작은 숫자들 중 가장 큰 수를 찾아야 한다.

# n: 행, m: 열
n, m = map(int, input("3 4").split())
num = []

# 한 줄 씩 입력을 받고, 거기서 가장 작을 수를 뽑는다.
for _ in range(n):
    num.append(min(map(int, input().split())))

# 가장 작은 수들 중에서 가장 큰 수를 리턴.
# 이렇게 결과물을 모두 담고 한번에 계산할 경우, 메모리를 필요 이상으로 쓰게 된다.
print(max(num))

'''
## min() 함수 이용

result = 0
for i in range(n):
    data = list(map(int, input().split()))
    min_value = min(data)
    result = max(result, min_value)
    # 이렇게 하면 숫자를 전부 담지 않고 그때그때 값을 비교하므로 메모리 사용이 덜할 것 같다.
'''
'''
## 2중 반복문 구조 이용  

result = 0
for i in range(n):
    data = list(map(int, input().split()))

    # 각 숫자는 1 이상 10,000 이하의 자연수 
    # => 나올 수 없는 가장 큰 수(10001)를 설정하여 무조건 첫 비교 시 min_value 에 값 할당하도록 함.
    min_value = 10001
    for a in data:
        min_value = min(min_value, a)

    result = max(result, min_value)
'''