[211210] 코딩 테스트를 위한 그리디 알고리즘 ( Greedy Algorithms )

모든 게시물은 macOS Monterey 12.0.1 버전 기준으로 작성하였습니다.
'이것이 취업을 위한 코딩 테스트다 with 파이썬' 토대로 작성하였습니다.

 

< 복습 >

 

• for문 쓸 때 무조건 for i in range() 가지 말고 리스트 그대로 iteration 할까도 고려하자.
• if l[i] == 0 or 1 으로 조건문 걸면 False or True로 인식해서 다 참으로 간다.(그런듯?)
• ㅣ = [] 형태로 리스트 초기화 후 for문에 l[i] 인덱싱하면 out of index 나온다.
• 리스트 sorting 할 때 l = l.sort() 하면 값 없어진다. 그냥 l.sort() 써라.
• 리스트 크기를 size(l)로 구할 수 없다. len(l)로 구해라.

 

---

 

그리디 알고리즘

 

번역하면 '탐욕법'이라는 이름에서 알 수 있듯이 그리디 알고리즘은 현재 상황에서

지금 당장 좋은 것만 고르는 방법을 의미한다. 매 순간 가장 좋아 보이는 것을 선택,

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

 

사실 크루스칼, 다익스트라 최단 경로와 같이 잘 알려진 알고리즘을 제외하고는

사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 유형이라는 특징이 있다.

보통 코딩 테스트에서 출제되는 그리디 알고리즘 유형의 문제는 애초에 창의력,

문제를 풀기 위한 최소한의 아이디어를 요구하는 것이지, 암기를 요하지 않는다.

따라서 연습문제로 경험을 쌓고, 함께 출제되는 정렬 알고리즘을 정확히 이해하자.

 

 

위와 같은 문제를 어떻게 해결할 수 있을까? 매번 높은 값을 선택한다고 하자.

 

5 -> 10 -> 4 = 19 (그리디 알고리즘)
5 -> 8 -> 5 = 19
5 -> 7 -> 9 = 21 (최적의 해)

 

예시에서 볼 수 있듯, 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다.

하지만 코딩 테스트에서 대부분 그리디 문제는 알고리즘을 활용하여 최적의 해가

되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제가 되니 걱정하지 말자.

 

 

여기서 떠올려야 하는 가장 간단한 아이디어가 무엇인지 생각해보자.

"가장 큰 화폐 단위부터 돈을 거슬러 주자."가 이 문제 해결의 아이디어다.

이를 파이썬으로 작성해보자.

 

 

화폐의 종류가 K라고 할 때, 소스코드의 시간 복잡도는 O(K)다.

즉, 이 알고리즘의 시간 복잡도는 금액과는 무관하며, 화폐의 종류에만 영향을 받는다.

 

중요한 것은 정당성 분석이다.

가지고 있는 동전 중에서 큰 단위가 늘작은 단위의 배수이므로 작은 단위의 동전들을

종합하여 다른 해가 나올 수 없기 때문이다. 이처럼 어떤 코딩 테스트 문제를 만나면

이를 해결할 수 있는 그리디 알고리즘이 존재하는지 먼저 고민하자. 그럼에도

해결 방법을 알 수 없다면 Dynamic Programming이나 Graph Algorithm으로 

해결할 수 있는지의 고민으로 넘어가는 것이 바람직하다.

 

정당성 분석이 왜 중요하냐면 큰 단위가 늘 작은 단위의 배수가 아닌 경우를 보자.

500원, 400원, 100원으로 800원을 만든다고 치면 500원 1개, 100원 3개가

아니라 400원 2개가 답이다. 즉, 화폐의 단위가 무작위로 주어진다면

이 방법론이 아닌 Dynamic Programming으로 해결할 수 있고, 나중에 다룬다.

---

큰 수의 법칙

 

다양한 수의 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만들어 보자.

단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없다.

( 서로 다른 인덱스에 해당하는 수라면 그 값이 같아도 다른 것으로 간주한다. )

 

예를 들어 2, 4, 5, 4, 6으로 이루어진 배열에서 M = 8, K = 3이라고 하자.

6 + 6 + 6 + 5 + 6 + 6 + 6 +5 = 46이 정답일 것이다.

배열의 크기 N, 숫자가 더해지는 횟수 M, 초과 한계 K가 주어질 때,

해당 법칙에 따른 결과를 출력하시오.

 

 

나의 방식은 위와 같다. 어떻게든 8번 숫자를 더할 것이고, 접근 방식은 가장 큰 수를

제한 횟수만큼 더하고, 두 번째로 큰 수를 더한 후, 다시 가장 큰 수를 더하는 것이다.

6 + 6 + 6 + 5 + 6 + 6 + 6 + 5 = 46 

입력을 받는 코드 부분이 이해가 가지 않는다면 아래를 참고하길 바란다.

 

https://hae-koos.tistory.com/24?category=1243802

[211202] 코딩 테스트를 위한 파이썬 문법 2편 (Python Basic)

 

참고로 책에 적혀져 있는 답안은 위와 크게 다르지 않은데 While 문을 활용하였다.

---

숫자 카드 게임

 

숫자 카드 게임은 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을

뽑는 게임으로 다음 규칙에 따라 카드를 뽑아야 한다.

 

카드는 N x M 형태로 놓여 있고, 뽑고자 하는 카드가 포함되어 있는 행을 선택한다.

해당 행에서 가장 숫자가 낮은 카드가 본인의 카드가 된다.

 

3	1	2
4	1	4
2	2	2

 

1행과 2행을 고르면 최종적으로 1을 고르지만 3행을 고르면 2를 고르니 

2행을 고르는 것이 최선의 선택임을 알 수 있다. 카드가 N x M 형태로 놓였을 때,

게임의 룰에 맞게 카드를 뽑는 프로그램을 만들어 보자.

 

[ 입력 예시 ]
2 4        # 2 x 4
7 3 1 8
3 3 3 4
-> 출력 = 3

 

문제를 푸는 아이디어는 각 행마다 가장 작은 수를 찾은 뒤에 그 중 가장 큰 수 찾기.

문제 설명은 길어도 문제를 푸는 아이디어 자체는 어렵지 않은 문제다.

라고 책에 적혀 있어서 그대로 쓰고 풀었는데 나에게는 쉽진 않았다,, 어떡하지,,

 

 

처음에 2중 반복문을 쓰려다가 다른 방법을 찾으려고 시간을 꽤 소비했다.

행과 열 모두 입력을 받는지라 행에 for문을 걸면 열은 입력받는대로 거기서

최소를 찾고 이를 정답 리스트에 append하는 방식으로 접근했다. 

추후에 정답 리스트에서 최댓값을 찾아 반환하면 문제 자체는 해결된다.

 

참고로 책에 적혀져 있는 답안은 두 개다.

첫 번째 답안은 나의 답안과 유사한데 굳이 정답 리스트를 사용하지 않았고,

두 번째 답안은 2중 반복문을 이용하였다.

---

1이 될 때까지

 

어떠한 수 N이 1이 될 때까지 두 과정 중 하나를 반복적으로 선택하여 수행한다.

단, 두 번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있다.

 

1. N에서 1을 뺀다.
2. N을 K로 나눈다.

 

예를 들어 N이 17, K가 4라고 가정하자. 17 -> 16 -> 4 -> 1.

세 번의 과정을 통해 17을 1로 만들었으니 이 때 수행 최소 횟수는 3이 된다.

N과 K가 주어질 때 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하자.

 

 

1이 될 때까지라는 문제 제목에 초점을 두고 풀었는데 책의 답안과는 사뭇 다르다.

 

 

시간까지 2초 안에 들어오는 지 확인하고 싶다면 import time

time.time()을 시작 시간과 종료 시간 잡아서 둘을 빼주면 되겠다.

---

 

 

정답으로 나온 코드는 웬만하면 쓰지 않으려고 하는데 내 답보다 훨씬 간결해서 적어둔다.

이렇게 하면 sort할 필요도 없고 코드 자체도 훨씬 직관적이다.. 공부하자..

 

data = input()

result = int(data[0])

for i in range(1, len(data)):
	num = int(data[i])
    if num <= 1 or result <= 1:
    	result += num
    else:
    	result *= num

print(result)

 

• if l[i] == 0 or 1 으로 조건문 걸면 False or True로 인식해서 다 참으로 간다.(그런듯?)
• ㅣ = [] 형태로 리스트 초기화 후 for문에 l[i] 인덱싱하면 out of index 나온다.
• 리스트 sorting 할 때 l = l.sort() 하면 값 없어진다. 그냥 l.sort() 써라.
• 리스트 크기를 size(l)로 구할 수 없다. len(l)로 구해라.

---

모험가 길드

 

 

오,,, 이건 진짜 잘 안 풀려서 답 봤다.. 오름차순 정렬까지는 했지만.. 거기까지.

현재 그룹에 포함된 모험가 수 >= 현재 확인하고 있는 공포도

조건을 만족할 때 그룹을 만들어서 보낸다.

 

 

• for문 쓸 때 무조건 for i in range() 가지 말고 리스트 그대로 iteration 할까도 고려하자.

 

---

구현 : 시뮬레이션과 완전 탐색

 

 

문제 해결에 있어 구현 유형의 문제는 소스코드로 옮기기 어려운 문제를 뜻한다

오른쪽 사진처럼 적절한 라이브러리를 찾아야 쉽게 풀리다는 것은 곧 모르면

굉장히 어렵거나 못 풀 수도 있다는 이야기다. ( 순열, 조합은 itertools 처럼 )

 

따라서 저자는 그 예시로 본 챕터에서 아래를 정리하였다. 따라가보자.

 

완전탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법
시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행하는 방법

 

 

대표적인 시뮬레이션 유형으로 상하좌우 문제를 해결하여 보자.

 

 

파이썬의 인덱싱은 (0,0) 부터 시작한다는 것을 생각하면 조작이 필요함을 알 수 있다.

 

 

풀긴 풀었는데 좀 어렵게 푼 것 같기도 하다.

 

 

완전탐색 유형은 언제 등장해도 이상하지 않으니 저자의 답안도 정리해두자.

 

# N 입력 받기
n = int(input())
x, y = 1, 1
plans = input.split()

# L, R, U, D에 따른 이동 방향
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
move_types = ['L','R','U','D']

# 이동 계획 확인
for plan in plans:
	# 이동 후 좌표 구하기
    for i in range(len(move_types)):
    	if plan == move_types[i]:
        	nx = x + dx[i]
            	ny = y + dy[i]
    # 공간을 벗어나는 경우 무시
    if nx < 1 or ny < 1 or nx > n or ny > n:
    	continue
    x, y = nx, ny

print(x, y)

 

---

 

 

그냥 수학으로 풀었는데..?

 

 

이 문제는 가능한 모든 시각의 경우를 하나씩 모두 세서 풀 수 있는 문제이며,

하루는 86,400초이므로, 모든 경우는 86,400가지다.

따라서 단순히 시각을 1씩 증가시키면서 3이 하나라도 포함되어 있는지 확인한다.

이러한 유형을 완전 탐색(Brute Forcing) 문제 유형이다.

 

 

i, j, k 순서대로 시간, 분, 초다. 이를 그냥 쭉 나열해버리고,

3이 안에 있다면 카운트를 증가시킨다..... 이게 맞지.....

 

---

 

 

 

아직 답은 보지 않았는데 앞에 여행가 여행계획서 문제 답안을 토대로 짰다.

개인적으로 아래 부분이 완전탐색 해결의 핵심이라는 생각이 든다.