[이코테] 숫자 카드 게임

문제 풀면서 작성한 메모

풀이 과정

---

1. 문제를 정독하면서 메모한다. 주의해야 할 것은 ※으로 표시한다.

입력 첫째 줄에 행의 개수 N, 열의 개수 M이 주어지고, 둘째 줄부터 N개의 줄에 걸쳐 각 카드에 적힌 숫자가 주어진다. 입력 조건과 필요한 변수를 메모했다.

2. 알고리즘을 떠올리고 적용하려고 노력한다.

역시 그리디 알고리즘 실전 문제이므로 알고리즘은 알고 있었다. 그리디 알고리즘은 현재 상황에서 가장 좋은 것을 선택하는 알고리즘이다. 행을 선택하면 뽑는 카드가 자동으로 정해지므로, 어떤 행을 선택하느냐가 중요하다. 최종적으로 가장 높은 숫자의 카드를 뽑기 위해서는 행마다 가장 숫자가 낮은 카드를 미리 계산할 수밖에 없다. 행마다 가장 숫자가 낮은 카드를 구하고, 그 카드들 중 가장 높은 숫자의 카드를 뽑으면 된다. 

 

그리디 알고리즘은 정렬 알고리즘과 자주 짝을 이뤄 출제된다. 이 문제에서도 '가장 숫자가 높은', '가장 숫자가 낮은'과 같은 기준을 통해 정렬 알고리즘을 알 수 있다. 그런데 숫자가 큰 순서대로, 혹은 작은 순서대로 정렬할 필요 없이 가장 큰 숫자와 가장 작은 숫자만 알면 되므로 max 함수와 min 함수를 사용하기로 한다. 

3. 필요한 변수에 대해서는 변수명을 작성한다.

이전 문제 답안 예시를 보니 변수명이 모두 소문자로 시작했다. 이에 맞춰 행의 개수와 열의 개수는 문제에 명시된 바와 달리 소문자로 변수명을 지었다. 각 숫자 카드를 card로, 숫자 카드를 담은 2차원 n x m 배열을 cards라 이름 지었다. 

4. 바로 문제 풀지 말고 주석을 달며 의사 코드를 작성한다.

# n, m 입력받아 저장

# cards 배열 생성
# 행 수 만큼 반복
## 행마다 cards에 append

# minCards 배열 생성
# 행마다 반복
## minCard 계산
## minCards에 append

# minCards에서 max 계산해서 return

 

입력 첫째 줄에 n과 m을 입력받아 저장한다. 입력 둘째 줄부터 n개의 줄에 걸쳐 각 카드에 적힌 숫자가 주어지므로 n만큼 반복하여 cards에 각 행의 card를 담은 리스트를 append 한다. 그래야 2차원 배열을 만들 수 있다. 그리고 각 행마다 가장 작은 숫자를 저장하기 위해 minCards와 minCard도 선언했다. n만큼 반복하여 minCards에 minCard를 append 한다. 마지막으로 minCards에서 max 함수를 이용해서 가장 큰 수를 구한다.

5. 의사 코드에 맞춰 구현한다.

# n, m 입력받아 저장
n, m = map(int, input().split())

# cards 배열 생성
cards = []
# 행 수 만큼 반복
for i in range(n):
  ## 행마다 cards에 append
  cards.append(list(map(int, input().split())))

# minCards 배열 생성
minCards = []
# 행마다 반복
for row in cards:
  ## minCard 계산
  minCard = min(row)
  ## minCards에 append
  minCards.append(minCard)

# minCards에서 max 계산해서 return
print(max(minCards))

 

주석대로 잘 구현했으나 for문을 두 번 돌 필요 없이 한 번으로도 해결할 수 있다는 생각이 들었다. 

 

# n, m 입력받아 저장
n, m = map(int, input().split())

finalCard = 0
# 행 수 만큼 반복
for i in range(n):
  ## 행마다 cards에 append
  row = list(map(int, input().split()))
  ## minCard 계산
  minCard = min(row)
  ## finalCard 계산
  finalCard = max(finalCard, minCard)

# minCards에서 max 계산해서 return
print(finalCard)

 

for문을 하나로 만들어 바로 minCard를 구했다. 그리고 finalCard를 따로 선언하여 minCard와 비교하여 더 큰 수를 저장했다. 이렇게 하면 cards와 minCards 배열을 만들 필요가 없다. 

답안 예시

---

3-3.py min() 함수를 이용하는 답안 예시

# N, M을 공백을 기준으로 구분하여 입력 받기
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) # 최종 답안 출력

 

이 예시는 내 최종 답안과 똑같다! result가 finalCard고, min_value가 minCard이다.

3-4.py 2중 반복문 구조를 이용하는 답안 예시

# N, M을 공백을 기준으로 구분하여 입력 받기
n, m = map(int, input().split())

result = 0
# 한 줄씩 입력 받아 확인하기
for i in range(n):
    data = list(map(int, input().split()))
    # 현재 줄에서 '가장 작은 수' 찾기
    min_value = 10001
    for a in data:
        min_value = min(min_value, a)
    # '가장 작은 수'들 중에서 가장 큰 수 찾기
    result = max(result, min_value)

print(result) # 최종 답안 출력

 

이 예시는 내가 작성한 2중 반복문 구조와 달리 cards와 minCards 배열을 만들지 않고 가장 작은 수만 저장하여 더 효율적이었다. 

개념 정리

---

그리디 알고리즘

현재 상황에서 지금 당장 좋은 것만 고르는 방법

-> 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

 

그리디 알고리즘의 경우 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해 준다. 이는 정렬 알고리즘을 사용했을 때 만족시킬 수 있어 그리디 알고리즘 문제는 자주 정렬 알고리즘과 짝을 이뤄 출제된다.

 

그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정당한지 검토해야 한다. 책에 나온 거스름돈 문제를 그리디 알고리즘으로 해결할 수 있는 이유는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다. 따라서 처음에 문제를 만났을 때는 항상 최적의 해를 보장할 수 있을 때까지 이것저것 다양한 아이디어를 고려해야 한다.

 

어떤 코딩 테스트 문제를 만났을 때, 바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하고, 문제를 해결할 수 있는 탐욕적인 해결법이 존재하는지 고민해보자. 만약 오랜 시간을 고민해도 그리디 알고리즘으로 해결 방법을 찾을 수 없다면, 그때는 이후 배우게 될 다이나믹 프로그래밍이나 그래프 알고리즘 등으로 문제를 해결할 수 있는지를 재차 고민해보는 것도 한 방법이다.

코드

---

GitHub - leeejihyun/algorithm: 알고리즘 문제 풀이

출처

---

나동빈, 『이것이 취업을 위한 코딩 테스트다 with 파이썬』, 한빛미디어(2021), p96-98