내일은 알고리즘

https://school.programmers.co.kr/learn/courses/30/lessons/250137

문제에서 시키는대로 구현하면 되는 시뮬레이션 문제입니다. 

몬스터의 마지막 공격이 있을때까지 데미지를 계산하며 체력을 회복합니다. 이때 붕대를 x초 감게 되면 추가적으로 체력을 회복하는것을 신경써야 합니다. 구현에는 다음 과정들이 필요합니다.

1. 시간을 늘려가며 체크해 공격이 들어왔다면 데미지 계산, 체력이 0 이하라면 -1을 return

2. 공격이 들어오지 않았다면 붕대를 1초 더 감고 체력을 회복

2-1. 붕대를 x초째 감았다면 체력을 추가 회복, 붕대를 감은 연속 횟수를 0으로 초기화

def solution(bandage, health, attacks):
    h, idx, b, e = health, 0, 0, attacks[-1][0]
    
    for i in range(e + 1):
        if i == attacks[idx][0]:
            h -= attacks[idx][1]
            b = 0
            idx += 1
        else:
            b += 1
            h = min(health, h + bandage[1])
        
            if b == bandage[0]:
                b = 0
                h = min(health, h + bandage[2])
        
        if h <= 0:
            return -1
    
    return h

https://school.programmers.co.kr/learn/courses/30/lessons/135808

간단한 그리디 유형의 문제입니다. 사과를 m개씩 묶어서 팔아야 하는데 m개 중 `가장 낮은 점수 x m`의 가격을 받을 수 있습니다. 간단하게 사과를 내림차순으로 정렬하고 앞에서 부터(점수가 높은 사과부터) m 개씩 끊어가며 판매하면 됩니다. 

예시를 통해 검증을 해보겠습니다. 예시 1번에서 사과의 점수가 [1, 2, 3, 1, 2, 3]이고 4개씩 묶어 팔아야 한다고 합니다. 이를 내림차순으로 정렬하면 [3, 3, 2, 2, 1, 1]이 되고 얻는 가격은 앞에서부터 4개를 선택해 얻은 [3, 3, 2, 2]에서 가장 낮은 점수인 2 x 4 = 8입니다. 

사과 n개가 존재하고 이를 내림차순으로 정렬한 값이 [A1, A2, A3, ...Am, ... An]이라고 해 봅시다. 내림차순으로 정렬했기 때문에 각 사과들의 가격은 A1 >= A2 >= A3 ...>= Am... >= An의 대소를 가집니다. 앞에서부터 m개의 사과를 선택했을 때 얻는 금액은 `Am x m` 입니다. Am보다 가격이 작거나 같은 어떤 사과 Ax (m < x <= n)를 선택하면 얻는 금액은 `Ax x m`이 됩니다. Am >= Ax이므로 m을 곱해봐야 대소관계가 변하지 않음을 알 수 있습니다. 따라서 매 순간마다 가능한 사과들 중에 가격이 큰 m개를 순서대로 고르는것이 가격합을 가장 크게 만드는 방법입니다.

def solution(k, m, score):
    score.sort(key = lambda x : -x)
    
    answer, i = 0, m - 1
    
    while i < len(score):
        answer += score[i] * m
        i += m
    
    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/161989

문제 밑부분에 레벨이 2에서 1로 조정되었다고 적혀있네요. 아마 그리디 문제로 올라왔다가 너무 쉬워서 레벨이 조정된 것 같습니다. 

실제로 풀이도 간단합니다. 벽을 칠해야 하는 부분을 만나면 그 부분을 왼쪽 끝으로 놓고 최대한 칠해줍니다. 이 값을 기억해 뒀다가 다음에 칠해야 하는 부분이 칠한 부분 밖이라면 칠한 횟수를 늘려주고 같은 행동을 반복합니다.

코드도 간단하네요.

def solution(n, m, section):
    answer = 0
    e = 0
    for s in section:
        if s > e:
            answer += 1
            e = s + m - 1
    
    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/161990

간단한 구현문제입니다.

바탕화면의 모든 파일을 한 번에 선택하기 위해서는 좌상단, 우하단의 점들 안에 모든 파일의 좌표가 존재해야합니다. 최소값 좌표와 최댓값 좌표 두개를 미리 준비해놓고 #이 존재하는 좌표마다 각각의 x, y 혹은 r, c에 대해 최소 최대를 갱신해주면 됩니다.

변수를 선언할 때 초기값이 입력사이즈 안에 들어가지 않도록 주의해주세요.

def solution(wallpaper):
    lr, lc, rr, rc = 100, 100, -1, -1
    
    for i in range(len(wallpaper)):
        for j in range(len(wallpaper[0])):
            if wallpaper[i][j] == '#':
                lr = min(lr, i)
                lc = min(lc, j)
                rr = max(rr, i + 1)
                rc = max(rc, j + 1)
    
    return [lr, lc, rr, rc]

https://school.programmers.co.kr/learn/courses/30/lessons/172928

레벨 1 치고 구현 난이도가 약간 있는 시뮬레이션 문제입니다. 이 문제에서 우리가 구현할 기능들을 추려보자면 다음과 같습니다.

1. 산책을 시작하는 좌표를 찾기

2. 입력으로 주어진 방향과 이동 거리를 분석

3. 이동이 가능한지(공원 밖을 나가지 않는지, 이동 경로에 장애물이 있는지) 판단하기

4. 이동이 가능하다면 이동시키기

그대로 구현을 하고 주어진 입력대로 모두 이동한 후에 최종 좌표를 return 하면 됩니다.

def solution(park, routes):
    delta = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    dset = {"N":0, "S":1, "W":2, "E":3}
    r, c, n, m = 0, 0, len(park), len(park[0])
    
    def cango(r, c, d, w):
        nonlocal n, m
        
        for i in range(w):
            r += delta[d][0]
            c += delta[d][1]
            
            if r < 0 or r >= n or c < 0 or c >= m or park[r][c] == 'X':
                return [-1, -1]
            
        return [r, c]
    
    for i in range(n):
        for j in range(m):
            if park[i][j] == 'S':
                r = i
                c = j
    
    for route in routes:
        d, w = route.split(' ')
        d = dset[d]
        w = int(w)
        
        res = cango(r, c, d, w)
        if res[0] != -1:
            r, c = res[0], res[1]
                
    return [r, c]

https://school.programmers.co.kr/learn/courses/30/lessons/136798

약수를 구하는 아이디어만 떠올리면 쉽게 풀리는 구현 문제입니다.

간단히 1부터 n까지 수가 가지는 약수를 카운트 해주고, 주어진 limit보다 큰 경우 limit로 갱신해서 누적합을 만들어 주면 됩니다. 단, 약수를 구할 때는 시간초과를 고려해야합니다. 

n의 약수를 구할 때 1부터 n까지 모든 자연수 x에 대해 1부터 x/2까지 일일히 나누어 떨어지는치를 체크한다면 이 문제의 n이 10만이기때문에 10만 x 5만 = 50억이라는 어마어마한 연산이 필요합니다.

약수를 나누어 구하는 대신 1부터 n까지 모든 자연수 x에 대해 자신의 배수들을 모두 찾으면 거꾸로 그 배수는 자신의 약수가 몇개인지를 알 수 있습니다. 이 경우엔 10만개의 수에 대해 10만 ÷ x번 연산을 하게 되고 이 값은 대략 1152620이라고 합니다. (해당 연산이 조화급수로 챗 gpt의 도움을 빌렸습니다.) 위에서 필요했던 50억번의 연산에 비해 0.02%에 불과한 매우 작은 연산입니다.

간단히 작성한 코드는 아래와 같습니다. 1 ... n으로 x를 키워가며 x의 배수들마다 1씩 더해주면 그 수들은 x로 나누어 떨어지는 수입니다. 

def solution(number, limit, power):
    answer = 0
    arr = [1] * (number + 1)
    
    for i in range(2, number + 1):
        d = i
        while d <= number:
            arr[d] += 1
            d += i
    
    for i in range(1, number + 1):
        if arr[i] <= limit:
            answer += arr[i]
        else:
            answer += power
            
    return answer

리스트 컴프리헨션을 이용해 코드를 좀 더 줄일 수도 있습니다.

def solution(number, limit, power):
    answer = 0
    arr = [1] * (number + 1)
    
    for i in range(2, number + 1):
        d = i
        while d <= number:
            arr[d] += 1
            d += i

    return sum([arr[i] if arr[i] <= limit else power for i in range(1, number + 1)])

https://school.programmers.co.kr/learn/courses/30/lessons/12980

0에서 n으로 가는것 보다 거꾸로 n에서 0으로 오는 방법을 생각하면 쉽게 풀리는 문제입니다. 탐욕법(Greedy) 풀이라고 봐도 되겠네요.

어떤 위치 x에서 0으로 갈때 x가 2의 배수라면 배터리를 쓰지 않고 x / 2로 순간이동할 수 있습니다. 순간이동을 하면 배터리를 쓰지 않기 때문에 순간이동이 가능할 때는 무조건 순간이동을 하는게 유리합니다. 따라서 n이 0이 될 때까지 2의 배수라면 /2를, 2의 배수가 아니라면(홀수라면) 1을 빼서 짝수로 만들며 풀이하면 됩니다.

def solution(n):
    a = 0
    
    while n > 0:
        if n % 2 == 0:
            n //= 2
        else:
            n -= 1
            a += 1
    return a

https://school.programmers.co.kr/learn/courses/30/lessons/42885

기본적인 탐욕법(Greedy) 문제입니다.

그리디란 매 상황에서 최선의 선택을 하는 풀이를 말합니다. 이 문제에서 한 보트에는 최대 2명이 탈 수 있으며 2명의 무게합 제한도 있습니다.

이때 가장 적은 보트로 모든 사람을 태우는 방법은 무엇일까요?

우선 보트에 최대한 2명을 많이 태워야 한다는 아이디어는 바로 떠올릴 수 있습니다. 1명씩 태우는 것보다 2명을 태울때 마다 사용하는 보트의 수가 1씩 줄어들죠.

그럼 최대한 2명을 많이 태우려면 어떻게 해야 할까요?

정답은 짝지을 수 있는 무거운 사람을 가장 가벼운 사람과 짝짓는다 입니다. 예를 들어볼까요?

무게 제한이 10이고 4명의 무게가 [1, 2, 5, 6, 8] 이라고 해봅시다. 가장 무거운 무게가 8인 사람을 무게가 1인 사람과 짝지으면 한 보트에 태울 수 있습니다. 이 사실은 당연하지만 이때 이런 생각을 하시는 분도 있을겁니다. 무게가 8, 2인 둘을 태우면 더 가벼운 무게가 1인 사람을 남길 수 있는데 이 방법을 고려하지 않아도 될까요? 

반례를 찾아봅시다. 작은 무게가 먼저 나오게 정렬된 a, b, c, d 가 있습니다. (a <= b <= c <= d) 우리는 a + d 대신 b + d를 태워서 이득을 보는 경우를 찾으려고 합니다. 즉 a + c는 보트에 탈 수 있지만 b + c는 보트에 탈 수 없는 경우를 찾는겁니다.

그럼 우리는 제한 무게 limit가 존재할 때, a + c <= limit < b + c 가 되게 하는 값들을 찾는겁니다.

a, b, c, d의 무게 순서를 알기 때문에 c와 d의 정확한 차이는 몰라도 d보다 작거나 같은 c는 d - x (x >= 0)로 다시 쓸 수 있습니다. 위 식에 대입을 해보면 limit < b + d - x가 되어야합니다. 그런데 우리는 a + d 대신 b + d를 태우려고 하기 때문에 b + d <= limit 성립해야합니다. 즉 b + d <= limit이고 여기서 x를 뺀 b + d - x는 당연히 limit보다 작거나 같다는 사실을 알 수 있습니다.

따라서, b + d를 보트에 태울 수 있다면 b + c를 보트에 태울 수 있는것도 당연한 사실이 되고 두 조합을 모두 보트에 태울 수 있으므로 고려하지 않아도 됩니다. 주어진 무게들을 정렬 한 뒤 현재 가장 무거운 사람과 가벼운 사람을 묶어 태울 수 있다면 태우고, 불가능하다면 무거운 사람을 혼자 보트에 태우며 필요한 보트의 수를 카운팅하면 됩니다.

def solution(people, limit):
    answer, left, right = 0, 0, len(people) - 1
    people.sort()
    
    while left <= right:
        if people[left] + people[right] <= limit:
            left += 1
            right -= 1
        else:
            right -= 1
        answer += 1
    
    return answer