본문 바로가기

Coding test

 (123)
[프로그래머스/k진수에서 소수 개수 구하기/파이썬] 소스코드 def solution(n, k): changedNum = '' checkPrime = '' answer = 0 while n != 0 : changedNum += str(n%k) n = n//k changedNum = changedNum[::-1].split('0') for i in (changedNum): if i != '': if isPrime(int(i)): answer += 1 return answer def isPrime(number): if number==1: return False for i in range(2, int(number**(0.5))+1): if number%i==0: return False return True 알고리즘 문제를 나눠보면 다음과 같이 2개만 구현하면 된..
[1912/백준/파이썬] 연속합 - DP 소스코드 A = int(input()) numlist = list(map(int,input().split())) for i in range (1,A): numlist[i] = max(numlist[i],numlist[i]+ numlist[i-1]) print(max(numlist)) 알고리즘 numlist= [10 ,-4 ,3 ,1 ,5, 6 ,-35 ,12, 21, -1] 일 때 [10, 6, 3, 1, 5, 6, -35, 12, 21, -1] [10, 6, 9, 1, 5, 6, -35, 12, 21, -1] [10, 6, 9, 10, 5, 6, -35, 12, 21, -1] [10, 6, 9, 10, 15, 6, -35, 12, 21, -1] [10, 6, 9, 10, 15, 21, -35, 12, ..
[11053/백준/파이썬] 가장 긴 증가하는 부분 수열 - DP 소스코드 A = int(input()) numlist = list(map(int,input().split())) dp = [1]*A for i in range (A): for j in range (i): if numlist[i] > numlist[j]: dp[i] = max(dp[i],dp[j]+1) print(max(dp)) 알고리즘 numlist= [10, 20, 10, 30, 20, 50,] 위의 예시를 바탕으로 만약 6개의 계단이 있다고 생각을 해보자 무조건 숫자가 커야 올라가는 것이다. - 1번 계단 10 : 1번 밟으면 끝이다. - 2번 계단 20 : 1번 계단 -> 2번계단 2번 밟는다. - 3번 계단 10 : 숫자가 커야 올라갈 수 있으므로 20 -> 10은 안된다. 10 -> 10 한번 ..
[프로그래머스/파이썬/구명보트] 문제 설명 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다. 구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다. 사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요..
[백준/1149/파이썬] RGB거리 소스코드 N = int(input()) color = [] for i in range (N): color.append(list(map(int,input().split()))) for i in range (1,N): color[i][0] += min(color[i-1][1],color[i-1][2]) color[i][1] += min(color[i-1][0],color[i-1][2]) color[i][2] += min(color[i-1][1],color[i-1][0]) print(min(color[-1])) 알고리즘 color = [[30, 19, 5],[64, 77, 64],[15, 19, 97],[4,71,57],[90,86,84],[93,32,91]] [[30, 19, 5], [69, 82, 83],..
[백준/14501/파이썬] 퇴사 소스코드 N = int(input()) work = [] for i in range (N): work.append(list(map(int, input().split()))) dp = [0] * (N+1) for i in range(N): for j in range(i+work[i][0],N+1): if dp[j] 1일차에 3일을 일할 수 있으면 4일부터 일을 하는 것 if dp[j] < dp[i] + work[i..
[백준/11401/파이썬] 소스코드 def power(a, b): if b == 0: return 1 if b % 2: return (power(a, b//2) ** 2 * a) % p else: return (power(a, b//2) ** 2) % p p = 1000000007 N, K = map(int, input().split()) fact = [1 for _ in range(N+1)] for i in range(2, N+1): fact[i] = fact[i-1] * i % p A = fact[N] B = (fact[N-K] * fact[K]) % p print((A % p) * (power(B, p-2) % p) % p ) 알고리즘 페르마의 소정리를 이용하여 푸는 문제였다. 페르마의 소정리는 다른 블로그에 잘 적혀있으니 ..
[백준/2579/파이썬] 계단오르기 소스코드 N = int(input()) s = [] for i in range (N): s.append(int(input())) dp = [0]* (N) dp[0] = s[0] dp[1] = s[0]+s[1] dp[2] = max(s[1]+s[2],s[0]+s[2]) for i in range(3,N): dp[i] = max(dp[i - 3] + s[i - 1] + s[i], dp[i - 2] + s[i]) print(dp[N-1]) 알고리즘 계단을 오르는 방법은 2가지가 있다. 1. 연속된 2계단 오르고 2칸 오르기 2. 한칸 밟고 1칸 밟기 이해를 돕기 위해 마지막 계단을 생각해보면 1. 마지막 계단(N)은 밟아야한다. 2-1. N-1을 밟으면 N-3에서 올라와야한다(연속된 3개는 못 오르므로) 2-..

티스토리툴바