[코테 스터디] Week1 그리디 & 구현 개념 정리

* 해당 포스팅은 아래 알고리즘 강의를 듣고 정리한 내용입니다.

https://www.youtube.com/watch?v=2zjoKjt97vQ&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=2

Greedy (그리디 알고리즘)

탐욕법: 지금 당장 좋은 것만 구함 (최소한의 아이디어)

=> 크루스칼/다익스트라와 같이 잘 알려진 알고리즘을 제외하고 출제 시 해당 문제를 풀기 위한 최소한의 아이디어를 적절히 떠올릴 수 있어야 풀리도록 출제

⭐ 정당성 분석 → 단순히 현재 상황에서 가장 좋아보이는 것 => 반복 선택하는 것: 최적해를 보장하는지 검토하는 과정이 필요

탐욕적으로 현재 상황에서 지금 당장 좋은 것만 고르는 방법  = 탐욕법

→ 최적의 해를 구할 수 있는지 검토 과정 필요!

 

EX) 거쳐가는 노드의 합이 최대가 되는 경우

Q1. 최적의 해?

5 → 7 → 9 (21)

Q2. 단순히 매 상황에서 가장 큰 값? 그리디

5 → 10 → 4 (19)

=> 일반적인 상황에서 그리디가 최적의 해를 보장할 수 없을 때가 많음 (최적의 해와 가깝게 가능)

+ 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서 단순히 그리디 알고리즘을 이용해도 최적의 해를 얻을 수 있다는 것을 추론 가능해야 문제 해결이 가능하도록 출제

⭐ 탐욕법으로 얻은 해가 최적의 해가 되는 경우에 한해서 문제 출제

 

예제 1) 거스름돈

최적해 빠르게 구하기 → 단위 큰 수부터 거슬러주기

=> 최적의 해를 보장할 수 있는 이유는 가진 동전 중 큰 단위가 항상 작은 단위의 배수이기 때문

EX) 800원을 거슬러줄 때 500원, 400원, 100원이면 최적해를 보장할 수 없음

화폐 종류가 K면 O(K): 화폐 종류만큼만 반복 수행하면 답 도출

# 카운터에 거스름돈으로 사용할 500, 100, 50, 10원짜리 동전이 무한히 존재
# 거슬러 주어야 할 돈이 N원일 때 거슬러 주어야 할 동전의 최소 개수
# N은 항상 10의 배수
import sys

N = int(sys.stdin.readline())

change = [500, 100, 50, 10]

cnt = 0 # 동전 개수 세는 변수
for i in change:
    cnt += (N // int(i)) # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
    N %= int(i)

print(cnt)

# 화폐 종류가 K라고 할 때, 소스코드의 시간 복잡도는 O(K)
# 거슬러줘야하는 금액과 무관하고, 동전의 총 종류에만 영향

 

예제 2) 1이 될 때까지

최대한 많이 나누면 최소로 계산 가능 → N 값을 줄일 때 2 이상의 수로 나누는 작업이 1 빼는 작업보다 수를 많이 줄일 수 있음

=> 최적의 해를 보장할 수 있는 이유는 N이 아무리 커도 K가 2 이상이고, 계속 나누기만 하면 기하급수적으로 감소하게 됨

* N/K가 N-1이 항상 빠르게 감소 + N이 항상 1이 될 수 있음

# N이 1이 될 때까지 둘 중 하나 반복 수행
# 두 번째 연산은 N/K가 나누어떨어질 때만 가능
# 1. N-1 2. N/K
# N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수
import sys

N, K = map(int, sys.stdin.readline().split())

cnt = 0
while N > 1:
    if N % K == 0:
        N //= K
        cnt += 1
    else:
        N -= 1
        cnt += 1

print(cnt)

# 최대한 나누는 작업을 많이 하도록 구현
# 풀이 (반복문 부분만 추가) -> 시간 복잡도 logN
while True:
    target = (N // K) * K # N이 K로 나눠떨어지지 않을 때, 가장 가까운 K로 나눠떨어지는 수 찾기
    # target은 K로 나누어 떨어지는 수
    cnt += (N - target) # 1을 빼야하는 횟수 먼저 더하기
    # ex) N = 25, K = 3 이라면 target = 25 // 3 * 3 = 24, cnt = 25 - 24 = 1
    N = target 

    if N < K:
        break 
    cnt += 1
    N //= K

# 마지막으로 남은 수 1씩 빼기
cnt += (N-1) # N = 0이 나오면 ... -1임
print(cnt)

 

예제 3) 곱하기 혹은 더하기

대부분의 경우, +보다 x가 값을 더 증가하게 만듦

더하거나 곱하는 두 수 중 0 또는 1이면 더하는 게 효율적

# 각 자리가 숫자 0~9로만 이루어진 문자열 S가 주어졌을 때,
# 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 X 혹은 + 연산자를 넣어
# 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램 작성 (모든 연산은 왼 -> 오)

import sys
S = sys.stdin.readline().strip()

cnt = int(S[0]) # 더하거나 곱해서 만드는 수

for i in S[1:]:
    str_to_int = int(i)
    if str_to_int <= 0 or cnt <= 1:
        cnt += str_to_int
    else:
        cnt *= str_to_int

print(cnt)

 

예제 4) 모험가 길드

오름차순 정렬 → 공포도 낮은 애부터 정렬

현재 그룹에 포함된 모험가 수 → 현재 확인하고 있는 공포도보다 크거나 같다면 그룹으로 생성

항상 최소한의 모험가 수만 포함하고, 모험가가 남아있을 수 있음

# 한 마을에 모험가 N명, 공포도 측정
# 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여
# 최대 몇 개의 모험가 그룹을 만들 수 있는가?
import sys
N = int(sys.stdin.readline())
N_list = list(map(int, sys.stdin.readline().split())) # 원소 하나씩 쪼개서 list에 넣기 split!!

N_list.sort()
cnt = 0 # 인원 수
result = 0 # 그룹 수

for i in N_list:
    cnt += 1 # i에 해당하는 사람 포함하기
    if cnt >= i: # 인원수가 i(공포도)보다 크면
        result += 1 # 그룹 결성
        cnt = 0 # 다시 인원수 초기화

print(result)
# 잘리는 숫자의 마지막이 기준이 된다고 생각하면 조금 쉬움
# ex) 1 2 2 2 3 이면 1 / 2 2 / 2 3 이렇게 잘리는데 result에 값이 하나 추가되려면
# 2 2의 경우, 두 번째 2에 해당할 때 result의 값이 올라가게 된다. 그러므로 세 번째 그룹의 3은 3을 충족하는 만큼 개수가 없으니 안됨

 

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

머릿 속에 있는 알고리즘을 소스코드로 바꾸는 과정

 

풀이 떠올리기 쉽지만 소스코드로 옮기기 어려운 문제 유형

1) 알고리즘 간단한데 코드가 매우 길어지는 경우 (언어에 따라 유형이 다름)

2) 실수 연산 다루고 특정 소수점 자리

3) 특정 기준에 따라 문자열 끊어 처리

4) 적절한 라이브러리 사용 ex. 모든 순열/조합 찾기(itertools)

 

일반적으로 2차원 배열 사용 => Matrix(행렬) 사용 (파이썬: 2차원 리스트)

* Matrix: 2차원 데이터 => 일종의 표와 같은 형태로 쉽게 나타낼 수 있도록 하는 수학 개념

 

2차원 공간의 방향벡터를 자주 활용

dx = [ 0, -1, 0, 1] 행 (앞부터 동, 북, 서, 남)

dy = [1, 0, -1, 0] 열 (앞부터 동, 북, 서, 남)

 

⭐ 다음 위치 구하기

x, y = 0, 0 #현재 위치에 대한 x, y 좌표
for i in range(4):
	nx = x + dx[i]
	ny = y + dy[i]

 

2차원 공간 방향벡터를 활용한 문제) 상하좌우 

# 여행가 A는 N * N 크기의 정사각형 공간 위에 서있다. 1 * 1 크기의 정사각형으로 나누어져
# 가장 왼쪽 위 좌표는 (1, 1)이며, 가장 오른쪽 아래 좌표는 (N * N)에 해당
# 여행가 A는 상 하 좌 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1, 1)
# L: 왼쪽으로 한 칸 이동
# R: 오른쪽으로 한 칸 이동
# U: 위로 한 칸 이동
# D: 아래로 한 칸 이동
import sys

N = int(sys.stdin.readline())
A = list(map(str, sys.stdin.readline().split()))

x, y = 1, 1
dx = [0, -1, 0, 1] # 동, 북, 서, 남
dy = [1, 0, -1, 0]
movie_types = ["R", "U", "L", "D"]

for i in A:
    for j in range(len(movie_types)):
        if i == movie_types[j]:
            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)

예제 1) 시각

가능한 모든 시각의 경우, 하나씩 세기

하루: 86400초(60초 * 60분 * 24시간) → 시각 1씩 증가시키며 3 포함된 경우 찾기

= BruteForce (완전탐색)

# 정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도
# 포함되는 모든 경우의 수를 구하는 프로그램 작성
# ex) 1을 입력했을 때 다음은 3이 하나라도 포함되어 있으므로 세어야 하는 시각
# 00시 00분 03초
# 00시 13분 30초
# 반면에 다음은 3이 하나도 포함되어 있지 않으므로 세면 안 되는 시각
# 00시 02분 55초
# 01시 27분 45초
import sys
N = int(sys.stdin.readline()) # 몇시인지 입력받는 것

cnt = 0
for i in range(N+1):
    for j in range(60):
        for k in range(60):
            if "3" in str(i) + str(j) + str(k):
                cnt += 1
print(cnt)

 

예제 2) 왕실의 나이트

# 8*8 표면상에서 나이트가 이동할 수 있는 경우의 수 출력
# 행 위치 = 1~8 / 열 위치 = a~h
# 요구사항대로 구현만 하면 돼
# 나이트의 8가지 경로 확인 후, 해당 경로로 이동 가능한지 확인만 하면 돼

import sys

# 현재 나이트의 위치 입력받기
n = sys.stdin.realine()
row = int(n[1]) # 두 번째 위치의 문자 -> 숫자로 바꾼 게 나이트가 존재하는 행
column = int(ord(n[0])) - int(ord('a')) + 1 # 문자를 아스키코드로 바꾸고 a를 아스키코드로 바꾼 값에 1을 더해 열 위치 찾음

# 나이트가 이동할 수 있는 8가지 방향 정의 
# dx, dy로 나누지 않고 하나의 리스트로도 풀 수 있음
steps = [(-2,-1), (-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1)]

# 8가지 방향에 대하여 각 위치로 이동이 가능한지 확인
result = 0
for step in steps:
    # 이동하고자하는 위치 확인
    next_row = row + step[0]
    next_column = column + step[1]
    # 해당 위치로 이동이 가능하면 카운트 증가
    if next_row >= 1 and next_row <= 8 and next_column >= 1 and next_column <= 8:
        result += 1
print(result)

 

예제 3) 문자열 재정렬

문자열 입력 시, 문자열 정렬 → 리스트에 저장

숫자 입력 시, 합계

# 알파벳 대문자와 숫자(0~9)로 구성된 문자열이 입력
# 모든 알파벳을 오름차순으로 정렬하여 이어서 출력한 뒤, 숫자를 더한 값을 이어서 출력
import sys
S = sys.stdin.readline().strip()

str_list = list() # 문자열 리스트
sum = 0 # 숫자 합계

for i in S:
    if i.isalpha(): # 알파벳인 경우, 리스트 삽입
        str_list.append(i)
    else:
        sum += int(i)
str_list.sort()
if sum != 0:
    str_list.append(str(sum)) # 리스트 가장 뒤에 삽입할 때 sum은 숫자니까 문자열로 변환 먼저..

print(''.join(str_list)) # 리스트를 문자열로 변환