OSNIM

문제 : https://www.acmicpc.net/problem/2293 정답 코드 import sys def solve(): for coin in arr: for j in range(coin, K+1): dp[j] += dp[j-coin] print(dp[K]) return if __name__=="__main__": input = sys.stdin.readline N, K = map(int, input().split()) arr = [int(input()) for i in range(N)] # dp[1]는 1개만 골랐을 때 경우의 수 # dp[0]은 하나의 동전만으로 k원 만드는 경우의 수를 의미 = 1 dp = [1] + [0]*K solve() 결과 및 정리 전형적인 DP 문제 메모리가 4MB라..

문제 : https://www.acmicpc.net/problem/2531 첫번째 풀이 (pypy3 2772ms, python3 시간초과) import sys def solve(): left = 0 right = k answer = 1 while left < N: eat = set() # 초밥을 k개 만큼 먹기 for i in range(left, right): eat.add(arr[i%N]) # c가 없으면 1개 추가하기 eat.add(c) answer = max(answer, len(eat)) # 1칸씩 밀기 left += 1 right += 1 print(answer) return if __name__=="__main__": input = sys.stdin.readline # N: 접시의 수 # d..

문제 : https://www.acmicpc.net/problem/2038 골룽 수열은 1이 1개, 2가 2개 있으니 2번, f(3) = 2 이므로 3이 2번 나타나는 단조 증가하는 수열입니다. 수열을 숫자로 풀면 다음과 같습니다. [1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8..] 첫번째 제출 (시간초과) import sys def solve(dp): left = 1 right = 0 k = 3 while len(dp) < n: dp = dp + [k]*(dp[left]) left += 1 k = k+1 print(dp[n-1]) return if __name__=="__main__": n = int(sys.stdin.read..

문제 : https://www.acmicpc.net/problem/1484 정답 코드 import sys def solve(): curWeight = 1 memoWeight = 1 answer = [] if G G: if diff == 1: break memoWeight += 1 elif powDiff == G: answer.append(curWeight) memoWeight += 1 elif powDiff < G: curWeight += 1 ..

문제 : https://www.acmicpc.net/problem/2230 정답 코드 import sys def solve(): start = 0 end = 0 answer = 2000000000 while end = M: if answer >= subtraction: answer = subtraction start += 1 if start > end: start -= 1 end += 1 elif subtraction < M: end += 1 print(answer) return if __name__=="__main__": input = sys.stdin.readline N, M = map(in..

문제 : https://www.acmicpc.net/problem/1806 첫번째 제출 코드 (시간초과) import sys def solve(): start = 0 end = 0 answer = N+1 while end = S: if answer > (end+1 - start): answer = (end+1 - start) start += 1 if start > end: end += 1 start -= 1 else: end += 1 if answer == N+1: print(0) else: print(answer) return if __name__ == "__main__": input = sys.stdin.readline N, S = map..

문제 : https://www.acmicpc.net/problem/1644 제출 코드 import sys def makeSieve(n): sqrt = int(n**(0.5)) temp = [1] * (n + 1) for i in range(2, sqrt+1): if temp[i] == 1: for j in range(i*2, n+1, i): temp[j] = 0 return [i for i in range(2, n+1) if temp[i] == 1] def solve(): answer = 0 input = sys.stdin.readline N = int(input()) primes = makeSieve(N) start = 0 end = 0 while end < len(primes): if sum(prim..

문제 : https://www.acmicpc.net/problem/2225 import sys def solve(): arr = [[0] *(N+1) for i in range(K+1)] for i in range(1, K+1): for j in range(1, N+1): if j == 1: arr[i][j] = i elif i == 1: arr[i][j] = 1 else: arr[i][j] = arr[i-1][j] + arr[i][j-1] return arr[K][N] if __name__ == "__main__": input = sys.stdin.readline N, K = map(int, input().split()) print(solve()%1000000000) arr의 행은 K(정수의 개수)를 ..

문제 : https://www.acmicpc.net/problem/2003 정답 코드 import sys input = sys.stdin.readline N, M = map(int, input().split()) arr = list(map(int, input().split())) start = 0 end = 0 ans = 0 while end M: start += 1 print(ans) 정리 및 분석 처음에 end를 start와 다르게 해야하는 줄 알고 end를 1부터 시작했습니다. 하지..

Level 2 Mathematics 문제 : https://programmers.co.kr/learn/courses/30/lessons/92335 코딩테스트 연습 - k진수에서 소수 개수 구하기 문제 설명 양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다. 0P0처럼 소수 양쪽에 0이 있는 경우 P0처럼 소 programmers.co.kr 제출 코드 def checkPrime(num): if num 0: n, mod = n // base, n % base result += str(mod) # 역순인 진수를 뒤집어 줘야 원래 변환 하고자하는 base가 출력 return result[::-1] def so..

Level 2 완전탐색 문제 : https://programmers.co.kr/learn/courses/30/lessons/42839 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr 정답 코드 from itertools import permutations def prime(num): sieve = [1] * (num + 1) MAX = int(num ** (0.5)) for i in range(2, MAX + 1): # i 가 소수라면 if sieve[i] == 1: # 배수는 모두 소수가 아니..

Level 2 정렬 문제 : https://programmers.co.kr/learn/courses/30/lessons/42747# 코딩테스트 연습 - H-Index H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다. 어떤 과학자가 발표 programmers.co.kr 첫번째 제출 코드 def solution(citations): answer = 0 MAX = max(citations) n = len(citations) citations.sort() for h in range(0, MAX + 1): for i in range(n): if citations[i] < ..

Level 2 정렬 문제 : https://programmers.co.kr/learn/courses/30/lessons/42746# 코딩테스트 연습 - 가장 큰 수 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 programmers.co.kr 제출 코드 def solution(numbers): answer = '' arr = [str(x)*3 for x in numbers] arr.sort(reverse = True) for num in arr: temp = num[:len(num)//3] answer +=..

Level 1 완전탐색 문제 : https://programmers.co.kr/learn/courses/30/lessons/42840 코딩테스트 연습 - 모의고사 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 programmers.co.kr 정답 코드 def solution(answers): ans = [] giveup1 = [1, 2, 3, 4, 5] giveup2 = [2, 1, 2, 3, 2, 4, 2, 5] giveup3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5] cnt = [0, 0, 0] for i in range(len(answers)):..

문제 : https://www.acmicpc.net/problem/17609 첫번째 풀이 (시간초과) import sys def solve(): string = input().strip() if len(string)%2 == 0: #뒤집었는데 똑같은 경우 #그 외는 없음 left = list(string[:len(string)//2]) right = list(string[len(string)//2:]) right.reverse() if left == right: return 0 return 2 else: for i in range(len(string)): temp = string[:i] + string[i+1:] left = list(temp[:len(temp) // 2]) right = list(tem..

Level 2 스택/큐 문제: https://programmers.co.kr/learn/courses/30/lessons/42584 코딩테스트 연습 - 주식가격 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,00 programmers.co.kr from collections import deque def solution(prices): answer = [] for i in range(len(prices)-1): price = 1 for j in range(i+1, len(prices)-1): if prices[i]

Level 2 스택/큐 문제 : https://programmers.co.kr/learn/courses/30/lessons/42583 코딩테스트 연습 - 다리를 지나는 트럭 트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 programmers.co.kr 정답 코드 from collections import deque def solution(bridge_length, weight, truck_weights): answer = 0 trucks = deque(truck_weights) # 트럭의 무게 onBrigde = deque([]) # [다리 위에 있는..

Level 2 스택/큐 문제 : https://programmers.co.kr/learn/courses/30/lessons/42587 코딩테스트 연습 - 프린터 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린 programmers.co.kr 첫번째 풀이 from collections import deque def solution(priorities, location): answer = 0 q = deque(priorities) idx = deque([i for i in range(len(q))]) cnt = 1 while q: M = max(q) pri = q.pople..

Level 2 스택/큐 문제 : https://programmers.co.kr/learn/courses/30/lessons/42586 코딩테스트 연습 - 기능개발 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 programmers.co.kr 첫번째 정답 코드 from collections import deque def solution(progresses, speeds): answer = [] proQ = deque(progresses) spdQ = deque(speeds) while proQ: per = proQ.popleft() speed = spdQ.pop..

Level 3 해시 문제 : https://programmers.co.kr/learn/courses/30/lessons/42579 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 programmers.co.kr 제출 코드 def solution(genres, plays): answer = [] dic = {} #장르별로 플레이와 인덱스 추가 for i in range(len(genres)): # 딕셔너리도 append 가능 if genres[i] in dic: dic[genres[i]].append([plays[i], i]) else: d..