[이것이 취업을 위한 코딩 테스트다 with 파이썬] Chapter 11. 그리디 & 구현

1. 그리디(Greedy) 알고리즘 

그리디 알고리즘은 말 그대로, 탐욕법이라고도 불림

현재 상황에서 지금 당장 좋은 것만 고르는 방법. 즉, 매 순간 가장 좋아 보이는 것을 택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않음.

코딩테스트 문제에서 가장 큰 순서대로, 가장 작은 순서대로와 같은 기준이 나오면 대체로 그리디 알고리즘

 

대표적인 예시 - 거스름돈 문제

문제

당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수는? 

 

해결 Tip

가장 큰 화폐 단위부터 돈을 거슬러 준다.

주어진 N이 1,260원일 경우, 거슬러줘야 할 동전의 최소 개수

500	100	50	10
2	2	1	1

n = int(input()) # 거슬러주어야 할 돈

money_list = [500, 100, 50, 10]
result = n # 남은 돈
count = 0 # 개수

for i in money_list:
    count += result // i
    result -= i * (result // i)

    if result == 0:
        break
  
print(count)

 

 

 

2. 구현 

코딩테스트에서 구현이란? 머릿속에 있는 알고리즘을 소스코드로 바꾸는 것

일반적으로 알고리즘에서 2차원 공간은 행렬의 의미로 사용

시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 방향벡터가 자주 활용

# 동, 북, 서, 남
dx = [0, -1, 0, 1] # 행
dy = [1, 0, -1, 0] # 열

 

대표적인 예시 - 상하좌우 문제

문제

여행가 A는 N * N 크기의 정사각형 공간 위에 서 있다. 가장 왼쪽 위 좌표는 (1, 1), 가장 오른쪽 아래 좌표는 (N, N)이다. 여행가 A는 상(U), 하(D), 좌(L), 우(R) 방향으로 이동이 가능하며, 시작 좌표는 항상 (1, 1)이다. 첫째 줄에 공간의 크기를 나타내는 N이 주어지고, 둘째 줄에 여행가 A가 이동할 계획서 내용이 주어진다. 여행가 A가 최종적으로 도착할 지점의 좌표 (X, Y)는? 

N = 5이고, 계획서 내용이 R R R U D D 일 경우, 출력은 3 4이다.

n = int(input())
x, y = 1, 1 # 초기값
list = input().split()

    # L, R, U, D
dx = [0, 0, -1, 1] # 행
dy = [-1, 1, 0, 0] # 열
move_types = ['L', 'R', 'U', 'D']

for i in list:
    for j in range(len(move_types)):
        if i == move_types[j]:
            nx = x + dx[j]
            ny = y + dy[j]

    # 경로를 벗어나는 경우 무시
    if nx < 1 or ny < 1 or nx > n or ny > n:
        continue
    # 이동 수행  
    x, y = nx, ny

print(x, y)