내일은 알고리즘

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

입력값의 갯수와 범위가 100으로 작기 때문에 N*N으로 풀이할 수 있는 문제입니다.

입력되는 수의 크기가 100이기 때문에 두 수를 더해서 만들 수 있는 최대크기도 200입니다.

간단하게 200짜리 boolean 배열을 만들고 모든 경우에 대해 두 수의 합을 체크해준 뒤 boolean 배열을 순회하면서 True인 값들을 정답 배열에 넣어주면 자연스럽게 오름차순으로 정렬이 됩니다.

def solution(numbers):
    answer = []
    make = [False for i in range(201)]
    
    for i in range(len(numbers)):
        for j in range(i+1, len(numbers)):
            make[numbers[i] + numbers[j]] = True
    
    for i in range(len(make)):
        if make[i]:
            answer.append(i)
    
    return answer

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

정렬을 통해 그리디하게 풀이하면 바로 풀리는 문제입니다.

가장 작은 요구값들부터 예산에서 빼주면 됩니다.

def solution(d, budget):
    answer = 0
    d.sort()
    
    for req in d:
        if budget - req >= 0:
            answer += 1
            budget -= req
        else:
            break
    
    return answer

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

3진법으로 변환하는 방법만 알면 간단하게 구현 가능한 문제입니다.

나머지를 List에 저장해 reverse로 뒤집어줘도 되지만 저는 앞뒤로 출납이 가능한 deque자료구조를 활용해 구현했습니다.

from collections import deque

def solution(n):
    answer = 0
    deq = deque()
    
    while n > 0:
        remain = n % 3
        n = n // 3
        
        deq.append(remain)
    
    while len(deq) > 0:
        answer *= 3
        answer += deq.popleft()
    
    return answer

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

기본적인 DFS로 구현이 가능한 문제입니다.

입력에 따라 판매원들의 이름을 Dictionary에 저장해서 Index화 해줍니다. 

이후 판매원들의 referral을 입력받아 자신을 초대한 사원을 가리키게 해주면 위로만 타고 올라가지는 그래프 형태의 구조가 됩니다.

이제 매출이 발생한 입력마다 위로 타고 올라가며 상납금(?)을 더해주면 됩니다.

11~13번에서 런타임 에러가 발생한다면 해당 테스트케이스의 사원들의 초대 형태가 일렬로 길게 이어진 모양이라 타고 올라가다가 스택 오버플로우가 발생한 것입니다.

종료조건이 제대로 잡히지 않았을때 자주 발생하는 에러인데, 생각해 보면 판매에서 얻어지는 이익의 최댓값은 10000입니다. (칫솔 하나의 이익이 100원, 판매수의 최대가 100)

상납금은 10%씩을 납부하는데, 가장 큰 이익이 발생해도 몇 단계만 올라가면 상납금은 0원이 됩니다.

10000 (매출 발생) -> 1000원 상납 -> 100원 상납 -> 10원 상납 -> 1원 상납 -> 0원 상납 (판매자의 5단계 위는 돈을 얻을 수 없다!)

따라서 상납금이 0원이 되는 경우 다음 호출을 하지 않도록 탈출 조건을 잡아주면 됩니다.

if lead == -1 or tax == 0: (돈을 보낼 초대자가 존재하지 않거나, 보낼 돈이 0원일시 더 이상 호출하지 않음)

def solution(enroll, referral, seller, amount):
    result = [0 for i in range(len(enroll))]
    follow = [-1 for i in range(len(enroll))]
    name_dict = {}

    index = 0
    for name in enroll:
        name_dict[name] = index
        index += 1

    for i in range(len(referral)):
        if referral[i] != '-':
            target = name_dict[referral[i]]
            follow[i] = target

    for i in range(len(seller)):
        start = name_dict[seller[i]]
        money = amount[i] * 100
        send_money(follow, result, money, start)

    return result


def send_money(follow, result, money, me):
    lead = follow[me]
    tax = int(money / 10)
    result[me] += money - tax

    if lead == -1 or tax == 0:
        return
    else:
        send_money(follow, result, tax, lead)

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

람다식을 활용한 정렬을 사용하면 쉽게 풀리는 문제입니다.

우선 문제의 조건을 만족하도록 실패율을 구해줍니다. n번째 스테이지에 멈춰있는 인원이 Xn명이라면, n+1번째 스테이지에 도달한 인원은 n번째 스테이지에 도달한 인원 - nX명 이 됩니다.

즉, 첫 스테이지에는 모두가 도달했으므로 실패율이 (첫 스테이지에 멈춘 인원 / 전체 인원)이라면 두번째 스테이지는 (두번째 스테이지에 멈춘 인원 / (전체인원 - 첫 스테이지에 멈춘 인원)) 이 됩니다.

실패율을 계산해 주고, 만약 도달인원이 없다면 그냥 0으로 처리해주고 (divide zero 런타임 에러를 막기 위함) 얻은 실패율을 스테이지의 순서와 함께 묶어 리스트에 저장한 뒤 실패율을 기준으로 내림차순 정렬, 두번째 요소는 스테이지를 기준으로 오름차순 정렬을 해주면 됩니다.

fail_rate.sort(key=lambda x:(-x[0], x[1]))

x[0]이 실패율로 내림차순 정렬을 위해 마이너스 부호를 붙여주고, x[1]은 스테이지 번호로 오름차순 정렬이 됩니다.

def solution(N, stages):
    answer = []
    
    fail_rate = [[0, i+1] for i in range(N)]
    stage_user = [0 for i in range(N+1)]
    total_user = len(stages)
    
    for stage in stages:
        stage_user[stage - 1] += 1
    
    for i in range(N):
        if total_user == 0:
            fail_rate[i][0] = 0
        else:
            fail_rate[i][0] = stage_user[i] / total_user
            total_user -= stage_user[i]
    
    fail_rate.sort(key=lambda x:(-x[0], x[1]))
    
    for i in fail_rate:
        answer.append(i[1])
    
    return answer

print(solution(	5, [2, 1, 2, 6, 2, 4, 3, 3]))

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

기본적인 반복문과 사칙연산, 약수의 원리 정도만 알면 쉽게 풀이가 가능한 문제입니다.

left <= num <= right 범위의 숫자들에 대해서 반복문을 돌려 탐색하고 1과 자기 자신은 반드시 약수이므로 약수의 갯수 2개를 잡아두고 시작합니다. (단 1은 자기 자신이 1이므로 1부터 시작합니다.)

나를 제외한 약수의 최댓값은 num/2이므로 탐색도 거기서 멈춰주시면 됩니다.

def solution(left, right):
    answer = 0
    
    for num in range(left, right+1):
        count = 2 if num != 1 else 1
        for div in range(2, (num//2) + 1):
            if num % div == 0:
                count += 1 
        if count % 2 == 0:
            answer += num
        else:
            answer -= num
    
    return answer

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

DP 유형의 문제입니다.

삼각형을 좌측으로 정렬해 계단 형태의 2차원 배열로 생각하고 풀면 쉽게 풀립니다.

삼각형을 내려오는 방향은 좌하단, 우하단 두가지만 가능합니다.

즉 내 위치가 i 번째 행의 j 번째 열이라면 내 위치로 오기 위해선 반드시 (i-1, j-1) 또는 (i-1, j)을 지나야 합니다.

따라서 해당 위치로 오는 경로의 최댓값은 (i-1, j-1) 또는 (i-1, j)로 가는 경로 중 큰 값에 해당 위치의 값을 더한 값이 됩니다.

마찬가지 규칙이 처음 0,0에서부터 시작해 연산해주면 됩니다. 단, 가장 좌측 (i행 0열)과 가장 우측 (i행의 i열)은 내려오는 경로가 한가지만 가능하므로 따로 계산해주어야합니다.

우리가 찾아야할 최댓값은 삼각형의 높이 == i번째 행의 원소중 최댓값입니다. 

def solution(triangle):
    answer = 0
    height = len(triangle)
    dp = [[0 for i in range(height)] for j in range(height)]

    dp[0][0] = triangle[0][0]

    for i in range(1, height):
        dp[i][0] = dp[i - 1][0] + triangle[i][0]
        for j in range(1, i):
            dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j]
        dp[i][i] = dp[i - 1][i - 1] + triangle[i][i]

    for i in range(height):
        answer = max(answer, dp[height - 1][i])
    
    return answer

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

Greedy 유형의 연습문제입니다.

여분의 체육복을 누구에게 빌려줄지가 중요할것 같지만, 앞에서부터 가능한 경우를 채워가면 풀이가 가능합니다.

만약 뒤에서 체육복이 필요하게 되면 앞의 체육복을 빼앗아야 하는데 앞의 체육복을 뺏는 경우는 어차피 총합은 같은 제로섬 동작이고 뒤에서 빌리는게 가능하면 최대값이 바뀌므로 가능한한 앞쪽부터 채우는게 유리합니다.

주의할 점은 여분의 체육복이 있는 상태에서 체육복을 도둑맞는 경우 무조건 자신이 착용한다는 것을 구현해줘야 합니다.

이 경우는 체육복의 수가 줄어들 수 있습니다.

Ex) 3번과 4번이 여벌을 소유하고 2,3번이 체육복을 도둑맞는 경우 1번(자기것) 2번(3번의 것) 3번(4번의 것) 4, 5번으로 5명 모두 체육복을 입을 수 있지만 문제의 조건에서 3번은 자기가 우선적으로 자기것을 입습니다. 즉 2번은 3번의 여벌 체육복을 빌리지 못해 답은 4가 됩니다.

def solution(n, lost, reserve):
    answer = 0
    student = [True for i in range(n)]
    spair = [False for i in range(n)]
    
    for i in lost:
        student[i-1] = False
    
    for i in reserve:
        if student[i-1]:
            spair[i-1] = True
        else:
            student[i-1] = True
        
    
    for i in range(n):
        if student[i]:
            answer += 1
        
        else:
            for j in range(-1,2):
                if 0 <= i+j < n and spair[i+j]:
                    spair[i+j] = False
                    answer += 1
                    break
    
    return answer