[2023 알고리즘 스터디] 3조 박제형 2주차 - 백준 3135, 9237, 11058, 19941

그리디 알고리즘

• 그리디 알고리즘(탐욕법)은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다.
• 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다.
• 정당성 분석 - 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토한다.
• 일반적인 상황에서 그리디 알고리즈은 최적의 해를 보장할 수 없을 때가 많다.
• 하지만 코딩테스트에서의 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제된다.

대표적인 그리디 알고리즘 문제 - 거스름 돈

→ 가장 큰 화폐 단위로부터 돈을 거슬러 주는 것이 최적의 해를 보장하는 이유?

: 큰 단위가 항상 작은 단위의 배수이기 때문에

(ex. 만약 800원을 거슬러 주어야 하는데 화폐 단위가 500, 400, 100 이라면?)

시간 복잡도 분석

• 화폐의 종류가 K라고 할 때, 소스코드의 시간 복잡도는 O(K)이다.
• 이 알고리즘의 시간 복잡도는 거슬러줘야 하는 금액과는 무관하며, 동전의 총 종류에만 영향을 받는다.

 

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

구현(Implementation)

• 구현이란, 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정
• 흔히 구현 문제는 풀이를 떠올리는 것은 쉽지만, 소스코드로 옮기는 어려운 문제를 지칭한다.

구현 문제의 예시

• 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
• 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제
• 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제
• 적절한 라이브러리를 찾아서 사용해야 하는 문제

 

• 일반적으로 알고리즘 문제에서의 2차원 공간은 행렬(Matrix)의 의미로 사용된다. (2차원 list)
• 시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 방향 벡터가 자주 활용된다.

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

# 현재 위치
x, y = 2, 2

for i in range(4):
    # 다음 위치
    nx = x + dx[i]
    ny = y + dy[i]
    print(nx, ny)

 

# 3135 - 라디오

https://www.acmicpc.net/problem/3135

3135번: 라디오

a, b = map(int, input().split())
N = int(input())
favorite = [] # 즐겨찾기 목록 list

for i in range(N): # 즐겨찾기 입력
    favorite.append(int(input()))

min = abs(a-b) 

click=0
for x in favorite: # 즐겨찾기 목록 탐색하면서 a-b 보다 차가 적으면 min update
    if min > abs(x-b):
        min = abs(x-b)

if min != abs(a-b): # min이 update 되었으면(즐겨찾기 내 채널이 a-b보다 작으면) click++
    click+=1

if min>0: # 남은 차 만큼 click ++ 
    click+=min

print(click)

# 9237 - 이장님 초대

https://www.acmicpc.net/problem/9237

9237번: 이장님 초대

n = int(input())
t = list(map(int, input().split()))
t.sort(reverse=True) # 리스트 t 내림차순 정렬

max =  t[0] + 1 # 가장 오래 걸리는 나무가 완전히 자라는 날짜를 기준으로 max 설정

# i(심는 날짜) + t[i](걸리는 시간) + 1(심는 데 하루 걸림) 계산을 통해서 각 나무별 완전히 자라는 날짜 파악
for i in range(1, len(t)): # 모든 나무를 탐색하며 max값보다 늦게 자라는 나무가 있을 경우 max 변경
    if max < i + t[i] + 1:
        max = i + t[i] + 1

print(max+1) # 이장님은 나무가 완전히 자란 다음날에 부르므로 +1

# 11508 - 2+1 세일

https://www.acmicpc.net/problem/11508

11508번: 2+1 세일

n = int(input())
cost = []

# 각 유제품 별 값 입력받음
for i in range(n):
    cost.append(int(input()))

# 값 내림차순 정렬 (내림차순으로 정렬하여 3개씩 묶어야 가장 저렴하게 구매할 수 있음)
cost.sort(reverse=True)

result = 0

# cost를 내림차순한 값들 중 3의 배수 번째를 제외하고 result에 더함
for i in range(n):
    if i > 0 and (i+1) % 3 == 0:
        continue
    result += cost[i]

print(result)

# 19941 - 햄버거 분배

https://www.acmicpc.net/problem/19941

19941번: 햄버거 분배

N, K = map(int, input().split())
seq = list(input()) # 문자열이 아닌 list로 받기 (문자열로 받으면 하나 단위로 수정 불가능)

cnt=0

for i in range(len(seq)):
    if seq[i] == 'P':
        for j in range(i-K, i+K+1):
            if 0<=j<len(seq) and seq[j] == 'H': # index(j)의 범위를 여기서 조절해 주었음 -> range(min(0, i-K), max(N, i+K+1))와 같이 할 수 도 있음
                cnt += 1
                seq[j] = 'X' # 먹은 햄버거는 X로 변경
                break

print(cnt)