[이코테] 다이나믹 프로그래밍(Dynamic Programming) 중복되는 연산 줄이기 탑다운 보텀업 다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로 피보나치 수열이 있다. 피보나치수열은 이전 두항의 합을 현재의 항으로 설정하는 특징이 있는 수열이다. ex) 1 1 2 3 5 8 13 21 34 55 89... 수학적 점화식을 프로그래밍으로 표현하려면 재귀 함수를 사용하면 간단하다. #재귀 함수를 이용한 피보나치 구현 def fibo(x): if x == 1 or x == 2: return 1 return fibo(x-1)+fibo(x-2) print(fibo(4)) 하지만 피보나치 수열의 코드를 이렇게 작성하면 심각한 문제가 생길 수 있다. 바로 f(n)에 함수에서 n이 커지면 커질수록 수행 시간이 기하급수적으로 늘어나기 때문이다. 이러한 문제는 다이나믹 프로..

2020. 11. 24.

알고리즘

[프로그래머스] N개의 최소 공배수 문제 설명 두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요. 제한 사항 arr은 길이 1 이상, 15 이하인 배열입니다. arr의 원소는 100 이하인 자연수입니다. 풀이 from fractions import gcd # gcd 라이브러리 호출 def solution(arr): answer = 0 while len(arr) > 1: n,m = arr...

2020. 11. 23.

알고리즘

[프로그래머스] JadenCase 문자열 만들기 문제 설명 JadenCase란 모든 단어의 첫 문자가 대문자이고, 그 외의 알파벳은 소문자인 문자열입니다. 문자열 s가 주어졌을 때, s를 JadenCase로 바꾼 문자열을 리턴하는 함수, solution을 완성해주세요. 제한 조건 s는 길이 1 이상인 문자열입니다. s는 알파벳과 공백 문자(" ")로 이루어져 있습니다. 첫 문자가 영문이 아닐때에는 이어지는 영문은 소문자로 씁니다. ( 첫 번째 입출력 예 참고 ) 풀이 def solution(s): answer = '' s= s.lower() k = s.split(' ') for i in k: k = i.capitalize() answer += k +' ' return answer[:-1] 느낀 점 모든 문자를 소문자로 변환 후 split으로 나눈다. ..

2020. 11. 23.

알고리즘

[프로그래머스] 행렬의 곱셈 문제 설명 2차원 행렬 arr1과 arr2를 입력받아, arr1에 arr2를 곱한 결과를 반환하는 함수, solution을 완성해주세요. 제한 조건 행렬 arr1, arr2의 행과 열의 길이는 2 이상 100 이하입니다. 행렬 arr1, arr2의 원소는 -10 이상 20 이하인 자연수입니다. 곱할 수 있는 배열만 주어집니다. 풀이 def solution(A, B): return [[sum(i*j for i,j in zip(A_row,B_col))for B_col in zip(*B)] for A_row in A] def solution(A, B): answer = [[0 for _ in range(len(B[0]))] for _ in range(len(A))] for i in range(len(A)): ..

2020. 11. 23.

알고리즘

[프로그래머스] 최솟값 만들기 문제 설명 길이가 같은 배열 A, B 두 개가 있습니다. 각 배열은 자연수로 이루어져 있습니다. 배열 A, B에서 각각 한 개의 숫자를 뽑아 두 수를 곱합니다. 이러한 과정을 배열의 길이만큼 반복하며, 두 수를 곱한 값을 누적하여 더합니다. 이때 최종적으로 누적된 값이 최소가 되도록 만드는 것이 목표입니다. (단, 각 배열에서 k번째 숫자를 뽑았다면 다음에 k번째 숫자는 다시 뽑을 수 없습니다.) 예를 들어 A = [1, 4, 2] , B = [5, 4, 4] 라면 A에서 첫번째 숫자인 1, B에서 두 번째 숫자인 5를 뽑아 곱하여 더합니다. (누적된 값 : 0 + 5(1x5) = 5) A에서 두번째 숫자인 4, B에서 세 번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 5 + 16(4x4) =..

2020. 11. 23.

알고리즘

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

2020. 11. 23.

알고리즘