내일은 알고리즘

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

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

약간의 수학적 사고력이 필요한 문제입니다.

우선 두 팀이 가장 늦게 만나는 경우는 결승전에서 만나는 경우입니다. 그럼 총 n개의 팀이 있을 때 결승전까지 몇 단계의 경기가 필요할까요?

n = 2이면 1, n = 3이면 2,  n = 4이면 2, n = 5이면 3... 즉 팀이 n개 이면 정답이 될 수 있는 가장 큰 값은 log(2) N을 올림한 값이 됩니다. 이 값을 매치의 갯수, M이라고 합시다. 우리는 M이 1부터 log(2) N 사이라는 걸 알았습니다. 그렇다면 정확한 M의 값은 어떻게 구할까요?

우선 N = 8인 케이스에서 M이 가장 큰 경우를 생각해보겠습니다.

M이 가장 큰 경우는 위와 같은 모습일겁니다. 결승전에서 만나는 팀은 결승전을 기준으로 왼쪽 팀, 혹은 오른쪽 팀 입니다. 

팀이 N개라면 팀 순서가 2^M/2 이하인 팀이 왼쪽에서 결승전에 오르는 팀이고 팀순서가 2^(M-1) 보다 큰 팀이 오른쪽에서 결승전에 오르는 팀 입니다. 

팀이 8개라면 log(2) 8 = 3이고 2^(3-1) = 4이므로 4 이하인 1~4번 팀은 결승전 기준으로 왼쪽팀이 되고 5~8번 팀은 결승전 기준으로 오른쪽 팀이 됩니다. 이때 두 팀은 모든 팀이 속한 크기가 8인 블록에서는 같은 블록에 속하지만 크기가 4인 블록에선 서로 다른 블록에 있죠.

만약 두 팀이 4강에서 만나는 경우는 어떨까요?

두 팀이 결승전보다 먼저 만난다면 결승전을 기준으로 같은 방향에 있는 팀이라는 뜻입니다. 즉 위 그림처럼 1번 팀, 3번 팀 모두 4이하로 왼쪽에 속합니다. 또 이들은 1~4번 팀을 기준으로 보면 log(2) 4 = 2이고 2^(2-1) = 2 이하인 1번 팀과 2 초과인 3번 팀으로 서로 다른 방향에 있습니다. 이때 두 팀은 크기가 4인 블록에는 함께 속합니다. 크기가 2인 블록에선 서로 다른 블록에 있습니다.

슬슬 규칙을 찾으셨을거라고 생각합니다. 3번과 4번 팀은 8강에서 만나고 이 두 팀은 2를 기준으로 2보다 큰 팀입니다. 이때 두 팀은 크기가 2인 블록에 함께 속합니다. 이보다 더 작은 크기의 블록은 없습니다.

즉 우리는 위에서 부터 블록 사이즈를 줄여가며 어느 단계에서 두 팀이 다른 블록에 있는지를 찾으면 거꾸로 어떤 단계에서 두 팀이 만나는지를 알 수 있습니다.

import math

def solution(n,a,b):
    answer = math.log2(n)
    a, b = a - 1, b - 1
    
    while n > 1:
        n //= 2
        if a // n == b // n:
            answer -= 1
        else:
            break

    return answer

코드는 이렇습니다.

블록의 사이즈가 되는 n 값을 줄여가며 a 와 b를 n으로 나눈 몫이 달라진다면 두 팀은 다른 블록에 속하는 것이고 그 단계에서 만나게 됩니다. 

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

스위핑 알고리즘을 통해 풀 수 있는 문제입니다.

스위핑 알고리즘은 입력 데이터를 정렬한 뒤 한 쪽에서부터 쓸어가듯 (Sweep) 풀어가는 풀이를 말합니다.

우리는 모든 미사일을 최소한의 요격으로 처리해야합니다. 이때 하나의 요격으로 여러 미사일을 처리하려면 주어진 미사일의 구간을 동시에 관통해야 합니다. 따라서 미사일을 구간의 시작과 끝으로 정렬 한 후 한 방향으로 탐색하며 가능한 많은 미사일을 요격하도록 요격 위치를 정하면 됩니다.

a < b < c < d인 좌표 a, b, c, d가 있을 때 구간 [a, c]와 구간 [b, d]를 동시에 관통하려면 요격 미사일은 [b, c]를 통과해야 합니다. 이런 식으로 가능한 범위를 좁혀가다 불가능한 경우에 새로운 요격을 쏜다는 로직입니다. 구간을 미리 정렬해뒀기 때문에 왼쪽 좌표는 신경쓰지 않고 오른쪽 좌표만 체크해줘도 같은 결과가 나옵니다.

def solution(targets):
    answer = 1
    targets.sort(key = lambda x : (x[0], x[1]))
    right = targets[0][1]
    
    for idx in range(1, len(targets)):
        if right <= targets[idx][0]:
            right = targets[idx][1]
            answer += 1
            
        else:
            right = min(right, targets[idx][1])
    
    return answer

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

n이 10만 이하의 자연수입니다. 10만은 2진법으로 나타냈을때 1 1000 0110 1010 0000이고 길이는 17입니다.

우리가 찾아야하는 수는 n보다 크고 이진수로 나타냈을때 1의 갯수가 같은 수 중에 가장 작은 수입니다. 나올 수 있는 최악의 경우를 나이브하게 생각해봅시다.

길이가 17인 이진수에서 1의 갯수는 많아봐야 17개입니다. (10만을 넘기 때문에 실제론 1의 수가 더 적습니다.) 따라서 우리가 찾아야 하는 최악의 수는 1의 갯수가 17개인 n보다 큰 가장 작은 수입니다. 가능한 수 중에서 가장 작은 수는 11 1111 1111 1110 따위가 되겠죠. 이 값이래봐야 50만 근처입니다.

즉 나오지도 않는 최악중 최악의 경우에도 우리가 찾아봐야 하는 수의 갯수는 50만개이고 이 정도면 충분히 시간안에 탐색 할 수 있습니다. 따라서 n보다 큰 수를 모두 이진수로 바꿔가며 1의 수를 카운팅하고 1의 수가 같을때 바로 탐색을 끝냈습니다.

def solution(n):
    c = str(bin(n)[2:]).count('1')
    print(str(bin(100000)))
    while True:
        n += 1
        if str(bin(n)[2:]).count('1') == c:
            return n

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

규칙을 찾으면 풀리는 간단한 완전탐색 문제입니다. 옛날 문제라 레벨이 높게 책정된것 같네요.

카펫의 가로길이가 세로길이 이상이라는 조건이 주어져있기 때문에, 가능한 경우에 대해 테스트해보면 됩니다.

가로길이가 w 세로길이가 h라고 하면 갈색 카펫의 수는 2 * (w + h) - 4이고 노란 카펫의 수는 (w - 2) * (h - 2)입니다.

w >= h인 가능한 모든 w와 h에 대해 탐색해도 내가 시도해봐야할 w와 h 조합이 대략 w^2개이고 w는 2500 이하이기때문에 그렇게 긴 시간이 걸리지 않습니다.

def solution(brown, yellow):
    for i in range(2, brown):
        for j in range(2, brown):
            if j > i:
                break
            if brown == 2 * i + 2 * j - 4 and yellow == (i - 2) * (j - 2):
                return [i, j]