거누의 개발노트

DP DP, 즉 다이나믹 프로그래밍(또는 동적 계획법)은 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제해결 패러다임으로 볼 수 있다. 피보나치 수열로 예를 들어 본다면, def fibo(n): if n in [1, 2]: return 1 return fibo(n-1) + fibo(n-2) assert fibo(10) == 55 assert fibo(100) == 354224848179261915075 # 안끝난다. 이런식으로 재귀 함수로 푼다면 100번째 값을 찾을 때는 fibo(1)번째, fibo(2)번째를 찾았던 n번째수를 계속해서 찾아나갈 것이다. 그렇지만 찾아 나간 결과를 저장..

문제 설명 위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다. 삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요. 제한사항 삼각형의 높이는 1 이상 500 이하입니다. 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니 풀이 def solution(triangle): for i in range(1, len(triangle)): for j in range(len(triangle[i])..

문제 집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다. 이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.) 편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다..

문제 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다. 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, 15..

문제 국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것이다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정한다. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다. 예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 140, 150이라고 하자. 이 경우, 상한액을 127로 잡으면, 위의 요청들에 대해서 각각 120, 1..

이번주도 마찬가지로 시간이 너무 빠르다. ( 매번 시간이 빨라서 이 말 밖에 안나온다...ㅎ ) 어느정도 적응이 된건지 아니면 쉬운 문제를 푸는건지 몰라도 조금씩 늘어가고 있는건 보인다. ( 그래도 다행이다. 사실 첫주차 불안했다. ) 이번주차부터 TIL을 꼬박꼬박 써서 수월하게 적을 수 있을 것 같다. 1일차 1일차는 트리와 이진트리에 대해서 배웠다. https://geonoo.tistory.com/106 자료구조/알고리즘 - 이진트리(1) 트리란? 뿌리와 가지로 구성되어 거꾸로 세워놓은 나무처럼 보이는 계층형 비선형 자료 구조이다. 큐(Queue)와 스택(Stack)은 자료구조에서 선형 구조라고 한다. 선형 구조란 자료를 구성하고 있는 geonoo.tistory.com 2일차 이진 탐색 트리의 검색,..

이진탐색? 배열이 정렬되어있을 경우, 절반씩 줄여나가면서 탐색하는 기법 1억 개 목록을 선형탐색할 때, 1억 번을 연산해야 한다. 이진탐색으로 찾는다면, 27번 안에 찾을 수 있다. import math math.log2(100000000) # 26.575424759098897 파이썬 while로 이진탐색 구현 def binary_search(arr, target, start, end): while start target: end = mid-1 else: start = mid+1 print(binary_search([1,2,3,4,5,6,7,8,9],8,0,8)) # 7 파이썬 이진탐색 내장 함수 bisect import bisect arr1 = [i for i in range(1,100,2)] # [1..

문제 정수 행렬 matrix에서 target 값을 검색하는 효율적인 알고리즘을 작성하십시오. 이 행렬에는 다음과 같은 속성이 있습니다. (m x n -> matrix) 각 행의 정수는 왼쪽에서 오른쪽으로 오름차순으로 정렬됩니다. 예제 입력 matrix = [ [1,4,7,11,15], [2,5,8,12,19], [3,6,9,16,22], [10,13,14,17,24], [18,21,23,26,30] ] , target = 5 예제 출력 Output: true 작성한 코드 class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: for i in range(len(matrix)): j = bisect.bisect..