Home

1. 문제 https://programmers.co.kr/learn/courses/30/lessons/43165 2. 풀이 2.1. dfs를 이용한 문제 풀이 아래와 같이 dfs를 이용하여 모든 경우의 수를 전부 체크합니다. 최대 경우의 수가 $ 2^{20} $ 밖에 되지 않아서 쉽게 처리할 수 있습니다. answer = 0 def dfs(numbers, target, depth, num_sum): global answer if depth == len(numbers): if target == num_sum : answer += 1 re...

1. 문제 https://programmers.co.kr/learn/courses/30/lessons/12949 2. 풀이 numpy를 이용하여 numpy의 array 곱을 구한 후에 바로 list로 변경하여 답으로 출력합니다. import numpy as np def solution(arr1, arr2): return np.dot(np.array(arr1), np.array(arr2)).tolist()

1. 문제 https://programmers.co.kr/learn/courses/30/lessons/12905 2. 풀이 dp를 이용하여 문제를 해결해야 합니다. dp_map에 현재 인덱스에서 가능한 최대 정사각형의 크기를 기록해놓습니다. 각 칸을 모두 돌면서 왼쪽, 위, 왼쪽 대각선 위를 살펴보고 해당 값에서 가장 작은 값 + 1로 갱신합니다. 이는 직접 그려보면서 이해하면 더 쉬운데, k 크기의 정사각형을 현재 위치에서 만들기 위해서는 위의 3개의 위치에서 k-1 이상의 값을 가져야 하기 때문입니다. … … ...

1. 문제 https://programmers.co.kr/learn/courses/30/lessons/12941 2. 풀이 2.1. dfs 를 사용한 시간 초과 풀이 특별한 방법이 떠오르지 않아서 dfs를 사용한 완전탐색을 이용하였으나 시간 초과되었습니다. 트리의 높이가 1000 라서 시간을 극복할 수 없습니다. answer = 98765432100 N = 0 def dfs(depth, A, B, value): global is_visited, answer if value >= answer: return if depth == N: answ...

1. 문제 https://www.welcomekakao.com/learn/courses/30/lessons/42583 2. 풀이 시뮬레이션으로 문제를 해결하면 됩니다 다리 사이즈, 대기 트럭 만큼 deque 생성을 해줍니다. 다리를 지나고 있는 트럭이 존재하지 않을 때 까지 while 문을 수행합니다. 대기열에 트럭이 있고, 다리를 지나고 있는 트럭이 없는 경우에 해당 숫자는 0으로 채워집니다. 시간을 1씩 증가시키면서, 다음 들어올 트럭이 다리에 있는 트럭의 무게의 합과 더하여 무게를 초과하지 않으면 다리에 있는 차에 넣고 아닌 경우에는 다리에 들어오지 ...

1. 문제 https://programmers.co.kr/learn/courses/30/lessons/42842 2. 풀이 전체 직사각형과 노란 직사각형의 가능한 세로 크기를 모두 구한다. 하나씩 꺼내보면서 가로와 세로에 각각 -2 된 값보다 작거나 같은 경우(내부에 속하려면 전체 격자 크기의 가로, 세로 크기 -2보다 작거나 같아야 하기 때문)를 구해서 return import math def make_grid_num(rec_grid_num, start_idx): # 가능한 직사각형의 세로 크기를 모두 구한다. sizes = [] half = (int)(math.sqrt(rec_...

1. 문제 https://programmers.co.kr/learn/courses/30/lessons/42578 2. 풀이 해시를 사용하면 손쉽게 풀 수 있는 문제입니다. 딕셔너리에 옷 종류를 key로, 옷 이름은 집합 value에 넣어줍니다. 모든 값을 넣고 옷 종류마다 +1 을 해준 값을 정답해 곱해줍니다. (+1은 옷을 안 입는 경우입니다.) -1 한 값을 정답으로 해줍니다(모두 벗은 경우) def solution(clothes): answer = 1 spy_dic = {} for wear, kind in clothes: # 딕셔너리에 옷 종류를 key로 옷 이...

1. 문제 https://programmers.co.kr/learn/courses/30/lessons/42883 2. 풀이 2.1. 시간 초과 풀이 만들어야 하는 자리 수는 number의 길이 - 빼야할 숫자 k 입니다. 숫자를 결정할 때 가장 높은 자리 숫자부터 정해야 합니다. 높은 자리 숫자는 현재 string 에서 최소한 빼야할 숫자 k - 1개 만큼이 뒤에 포함되어 있어야 합니다. 예를 들어, ‘2223454’ 에서 4개의 숫자를 빼야 되면 자리 수는 3자리이고, 첫 숫자는 뒤에 최소한 4 - 1 = 3개 만큼의 숫자 ‘454’ 앞에 있어야 하기 때문에 ‘222...

1. 문제 https://programmers.co.kr/learn/courses/30/lessons/12945 2. 풀이 배열을 하나씩 증가시키면서 이전 수 2개를 더해주고 return 해주는 간단한 문제입니다. def solution(n): F = [0, 1] for i in range(2, n+1): F.append((F[i-1] + F[i-2]) % 1234567) return F[n]

1. 문제 https://programmers.co.kr/learn/courses/30/lessons/42577 2. 풀이 2.1. 딕셔너리(해쉬)를 이용한 풀이 prefix_dic이라는 dictionary 에 모든 단어를 집어 넣습니다. for문을 돌면서 문자 길이 -1 까지 체크를 하면서 dictionary에 해당 문자열이 존재하는지 확인합니다. 문자열의 길이가 20이 최대이기 때문에 속도에 문제가 없는 소스코드입니다. def solution(phone_book): answer = True prefix_dic = {} for x in phone_book: ...