22년 12월 13일_효율적인 화폐구성, 프로그래머스 알고리즘, 23년도 정처기 범위 공유

월요일[삶의 이유를 느낀다. 상호작용을 통해 거듭하는 나!]

 

1. 이것이

2. 알고리즘

3. 정처기 범위 체크

 

1>

효율적인 화폐 구성

문제 설명:

N가지 종류의 화폐가 있다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 m원이 되도록 하려고 한다. 이때 각 회폐는 몇 개라도 사용 할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 가은 경우로 구분한다

 

 

//

이번 문제는 적은 금액부터 큰 금액까지 확인하며 차례대로 만들 수 있는 최소한의 화폐 개수를 찾으면 된다. 금액 i를 만들 수 있는 최소한의 화폐개수를 a화폐의 단위를 k라고 했을 때 다음과 같이 점화식을 작성할 수 있다.

a = min(a, a+1)

n, m = map(int, input().split())
# N개의 화폐 단위 정보 입력 받기
array = []
for i in range(n):
	array.append(int(input())
    
# 한번 계산된 결과를 저장하기 위한 dp테이블 초기화
d = [10001]* (m+1)

d[0] = 0
for i in range(n):
	for j in range(array[i], m+1):
    	if d[j-array[i]] != 10001: 
    		d[j] = min(d[j], d[j -array[i] +1)
            
if d[m]  == 10001:
	print(t-1)
else:
	print(d[m])

2>

합성수 구하기

def solution(n):
    answer = 0
    if n <4:
        return 0
    for i in range(n+1):
        a = primenumber(i)
        if a == False:
            answer += 1
    return answer

def primenumber(x):
    for i in range(2, x):   
        if x % i == 0:      
            return False
    return True

다른사람이 한 풀이

def solution(n):
    output = 0
    for i in range(4, n + 1):
        for j in range(2, int(i ** 0.5) + 1):
            if i % j == 0:
                output += 1
                break
    return output

3이하의 합성수는 없으므로 첫번째 반복문에서 4부터 시작

i ** 0.5로 함으로써 반으로 나눔 = 속도 높임

합성수인 경우 (i % j == 0) 답의 개수를 늘리고 break로 다음 숫자 판별 시작

 

2차원으로 만들기

from collections import deque

def solution(num_list, n):
    answer = []
    result = []
    num_list = deque(num_list)
    while len(num_list) > 0:
        for i in range(n):
            a = num_list.popleft()
            result.append(a)
        answer += [result]
        result = []
    return answer

result.clear()를 하면 이전 기입했던 값도 사라져서 result 의 값을 재정의해야함..

def solution(num_list, n):
    answer = []
    i = 0
    while i < len(num_list):
        answer.append(num_list[i:i+n])
        i+=n
    return answer

개수마다 slice를 사용해서 코딩

 

k의 개수

def solution(i, j, k):
    answer = 0
    for z in range(i, j+1):
        z = list(str(z))
        for g in z:
            if int(g) == k:
                answer +=1        
    return answer

def solution(i, j, k):
    answer = sum([ str(i).count(str(k)) for i in range(i,j+1)])
    return answer

count 사용

출처 : https://appia.tistory.com/176

 

출처 : https://appia.tistory.com/176

 

가까운 수

def solution(array, n):
    answer = 0
    a = 0
    array.sort()
    for i in array:
        if i < n :
            a = i
        elif i > n :
            z = n-a
            x = i-n
            if z > x:
                return i
            elif z==x :
                return a
            else: 
                return a
        elif i == n :
            return n

    return array[-1]

다른사람이 한 풀이

def solution(array, n):
    array.sort(key = lambda x : (abs(x-n), x-n))
    answer = array[0]
    return answer

abs - 절댓값으로 치환해주는 함수

나는 각각 뺐다면,  여기는 절댓값으로 빼서 가장 작은 값을 return 

 

한 번만 등장한 문자

def solution(s):
    answer = []
    for key, value in Counter(s).items():
        if value == 1:
            answer.append(ord(key))
    answer.sort()
    return "".join([chr(i) for i in answer])

다른사람이 한 풀이

from collections import Counter

def solution(s):
    counter = Counter(s)
    unqiue_alphabets = filter(lambda alphabet: counter[alphabet] == 1, counter.keys())
    return ''.join(sorted(unqiue_alphabets))

 

3>

정보처리기사출제기준(2020_).pdf

0.18MB

 

 

// yesterday wished to today list.

. 이것이

. 알고리즘

. 정처기 범위 공부

 

tomorrow wish list

. monnite 개발 

. 알고리즘

. 이것이