[BOJ/백준] 1463번 1로 만들기

문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 풀이 n = int(input()) d = [0] * (n+1) d[0] = 0 d[1] = 0 for i in range(2,n+1): if n == 0 : continue #현재의 수에서 1을 빼는 경우 d[i] = d[i -1] +1 if i % 3 == 0: # 3으..

• format_list_bulleted Algorithm
• · 2020. 11. 26.
• textsms

[BOJ/백준] 2839번 설탕 배탈

문제 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다. 상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000) 출력 상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확..

• format_list_bulleted Algorithm
• · 2020. 11. 26.
• textsms

[이코테] 다이나믹 프로그래밍(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이 커지면 커질수록 수행 시간이 기하급수적으로 늘어나기 때문이다. 이러한 문제는 다이나믹 프로..

• format_list_bulleted Algorithm
• · 2020. 11. 24.
• textsms

[프로그래머스] 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...

• format_list_bulleted Algorithm
• · 2020. 11. 23.
• textsms

[프로그래머스] 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으로 나눈다. ..

• format_list_bulleted Algorithm
• · 2020. 11. 23.
• textsms

[프로그래머스] 행렬의 곱셈

문제 설명 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)): ..

• format_list_bulleted Algorithm
• · 2020. 11. 23.
• textsms

<