내일은 알고리즘

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

명함의 가로, 세로 크기의 최댓값을 포함하도록 지갑의 크기를 정해야 하는데, 명함을 돌릴 수 있으므로 명함의 긴 방향을 일치시키도록 돌리는 아이디어로 풀이할 수 있습니다.

극단적인 예를 들어, 1x10 10x1 두개의 명함을 이 상태대로 담으려면 10x10 사이즈의 지갑이 필요하지만, 하나의 명함을 돌리면 1x10 크기의 지갑에 담을 수 있습니다.

이런 상태를 만들기 위해서 w와 h값 중 한 방향을 정해 긴 쪽이 모두 일치하도록 돌려주고 최댓값을 찾으면 됩니다.

def solution(sizes):
    width = 0
    height = 0
    
    for size in sizes:
        w = size[0]
        h = size[1]
        
        if w < h:
            temp = h
            h = w
            w = temp
        
        if w > width:
            width = w
        if h > height:
            height = h   
    
    return width * height

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

2016년이 윤년이란 정보에 주의해서 입력의 일수에 월 별 지난 일 수를 저장해 줍니다.

예를 들어, 1월은 6일은 지난 월이 없어 그대로 6일 이지만 2월 6일은 1월이 지났기 때문에 31을 더해 37일이 됩니다.

또, 문제의 정보에서 생각해 보면 1월 1일(=1일)이 금요일이란 정보를 얻을 수 있습니다. 일주일은 7 단위로 반복되기 때문에, Index 1이 금요일인 길이 7의 배열을 만들어줍니다.

이제 입력된 날짜를 일수로 변환하고 7로 나눈 나머지의 Index 속 값을 취하면 쉽게 요일을 구할 수 있습니다.

def solution(a, b):
    month = [0,0,31,60,91,121,152,182,213,244,274,305,335]
    day = ['THU','FRI','SAT','SUN','MON','TUE','WED']

    daynum = month[a] + b
    answer = day[daynum % 7]
    return answer

solution(5,24)

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/49189

기본적인 BFS로 풀이가 가능한 문제입니다.

기본 문제라 Lv.3로 놓인거지 요즘 레벨로는 2레벨 중에서도 쉬운문제가 아닐까 싶습니다...

node의 갯수가 edge의 갯수보다 훨씬 많기 때문에 인접행렬 대신 인접리스트를 사용해 구현했습니다.

(node의 갯수가 2만개로 인접행렬로는 2만*2만 = 4억 사이즈가 됩니다.)

BFS를 이용해 시작점에서 부터의 거리가 한 칸씩 먼 노드들을 탐색했고, 매번 탐색한 노드의 갯수를 저장해서

더 탐색할 노드가 없는 경우엔 이전 턴에 탐색한 노드의 갯수를 리턴했습니다.

from collections import deque


def solution(n, edge):
    answer = 0
    adjList = [[] for i in range(n+1)]
    visited = [False]*(n+1)
    
    for i in edge:
        start = i[0]
        end = i[1]
        
        adjList[start].append(end)
        adjList[end].append(start)
    
    queue = deque()
    queue.append(1)
    visited[1] = True

    while(len(queue) != 0):
        answer = size = len(queue)
        
        for i in range(size):
            start = queue.popleft()
            
            for e in adjList[start]:
                if(not visited[e]):
                    visited[e] = True
                    queue.append(e)
    
    return answer


n = 6
vertexs = [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]

print(solution(n,vertexs))