Greedy Algorithm & Implementation

그리디 알고리즘 (Greedy Algorithm)

- 그리디 알고리즘(탐욕법)은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미
- 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디얼르 떠올릴 수 있는 능력을 요구
- 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는 검토하여 문제를 풀어야 한다 (모든 경우 지금 당장 좋은 것만 고르는 방법이 최고의 방법이 아니므로)

대표적으로 동전 거스름돈 문제가 있다.
500원 / 100원 / 50원 / 10원 짜리 동전이 무한히 존재하는데 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구하라. 단, 돈 N은 항상 10의 배수이다.

N이 1,280원이라면?

500 - 2
100 - 2
50 - 1
10 - 3
이렇게 해서 최소 동전 개수는 8개가 될 것이다.

이 문제에서 왜 가장 큰 화폐 단위부터 돈을 거슬러 주는게 최적의 해를 보장하는 이유가 무엇일까?
- 가지고 있는 동전 중 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문


이걸 코드로 옮기면 다음과 같다.
간단한 문제이므로 해설은 하지 않겠다.

money = [500, 100, 50, 10]
money_count = 0

N = int(input())

for i in money:
    share = N // i  # 몫 ->> 해당 화폐로 거슬러 줄 수 있는 동전 개수 세기
    remainder = N % i # 나머지 ->> 동전 개수 나머지 금액
    
    money_count += share
    N = remainder
    
print(money_count)
  


구현(Implementation)

- 구현이란, 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정
- 모든 문제가 구현이라고 생각할 수 있지만 일반적으로 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 지칭
- 알고리즘은 간단한데 코드가 길어지는 문제 등등
- 개인적으로 삼성 코테나 다양한 구현문제는 BFS, DFS 등 을 섞어서 복잡하게 내는 '빡구현'이라고 표현하는 문제들이 자주 출제된다.

그 중 구현 중 대표적인 문제 유형으로 시뮬레이션이나 완전 탐색 문제에서는 2차원 공간에서의 방향 벡터가 자주 활용되는데, 다음 코드가 자주 활용될 것이다.
* 시뮬레이션: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 유형
* 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 하는 문제 유형


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

# init position
x, y = 2, 2

for i in range(4):
    # 다음 위치
    nx = x + dx[i]
    ny = y + dy[i]
    print(nx, ny) # 동 서 남 북 순서로 탐색하게 된다.

# result
# 2 3
# 2 1
# 3 2
# 1 2


# 또한, 파이썬으로 구현하다보면 리스트가 1000만 이상인 경우 메모리 용량 제한으로 못 풀 경우가 있을 수 있을거고 수행시간이 1초라는 시간을 뒀을때 약 2000만 번의 연산을 수행한다고 가정하고 문제를 풀면 실행 시간 제한에 안정적일 것이다.
-> 시간 제한이 1초이고, 데이터의 개수가 100만 개라면 시간 복잡도 O(NlogN) 이내의 알고리즘을 이용해서 풀어야한다.


대표적인 시뮬레이션 문제를 살펴보자

상하좌우 문제
ex)여행가 A는 N x N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1 x 1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 (1,1)이며, 가장 오른쪽 아래 아래 좌표는 (N,N)에 대항한다. 여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1,1) 이다.
우리 앞에는 여행가 A가 이동할 계획이 적힌 계획서가 놓여 있다.
L,R,U,D (왼쪽, 오른쪽, 위쪽, 아래쪽) 한칸씩 이동하라는 명령이고, 정사각형 공간을 벗어나는 움직임은 무시된다. 이때, 여행가 A 가 최종적으로 도착할 지점의 좌표 (X,Y)를 구해라
5 (공간의 크기 N)
R R R U D D (계획서 A)
정답 : 3 4

N = int(input())
A = list(input().split(' '))
pos = [1,1]

move_x = [0,0,1,-1]
move_y = [1,-1,0,0]
move_types = ['R', 'L', 'D', 'U']
for move in A: # 이동 계획 하나 씩 확인
    for i in range(4):
        
        if move == move_types[i]:
            nx = pos[0] + move_x[i]
            ny = pos[1] + move_y[i]
    
    # 공간을 벗어나는 경우 그 해당 계획은 무시한다
    if nx < 1 or ny < 1 or nx > N or ny > N:
        continue
    
    # 이동 수행
    pos[0] = nx
    pos[1] = ny

print(pos[0], pos[1])

 

 

 

 

 

위 내용들은 이코테 youtube 및 책을 참고하였습니다

이코테 링크

책 링크