백준 2294번: 동전2

import sysinput=sys.stdin.readlinen,k=map(int,input().split())coins=[int(input()) for i in range(n)]lst=[1e8 for i in range(k+1)]lst[0] =0for i in coins: for j in range(i,k+1): lst[j]=min(lst[j-i]+1,lst[j])if lst[k]==1e8: print(-1)else: print(lst[k])  디피 문제라는걸 알고 어떤식으로 해야 점화식을 잘 세워야할지 고민했다.큰 문제를 작은 문제들로 나누어서 해결하고 마지막에 이제 문제를 해결해야된다고 생각을 했다.처음에 내 생각에는 지금 k라는 수에 coins의 수들 중 가장 근접한 ..

• format_list_bulleted 알고리즘/백준
• · 2024. 10. 3.
• textsms

백준 14888번: 연산자 끼워넣기

import sysinput = sys.stdin.readlineN = int(input())num = list(map(int, input().split()))op = list(map(int, input().split())) # +, -, *, //maximum = -1e9minimum = 1e9def dfs(depth, total, plus, minus, multiply, divide): global maximum, minimum if depth == N: maximum = max(total, maximum) minimum = min(total, minimum) return if plus: dfs(depth + 1, total + nu..

• format_list_bulleted 알고리즘/백준
• · 2024. 8. 5.
• textsms

백준6603: 로또

from itertools import combinationsdef func(arr): for i in arr: c_lst=list(combinations(i[1:],6)) # print(c_lst) for j in c_lst: print(' '.join(map(str, j))) print()arr=[]while True: lst=list(map(int,input().split())) if lst[0]==0: break arr.append(lst)func(arr)이것도 조합라이브러리를 이용하는 문제이다. 입력된 각 리스트에서 첫 번째 원소를 제외한 나머지 원소들로 구성된 6개의 조합을 생성하고, 이를 ..

• format_list_bulleted 알고리즘/백준
• · 2024. 8. 5.
• textsms

백준1256번: 사전

dp와 조합론으로 푸는 문제이다.import sysfrom math import combinput=sys.stdin.readlinen,m,k=map(int,input().split())result=[]if comb(n+m,n)0 and m>0: cb=comb(n+m+1,n-1) if cb>=k: result.append('a') n=n-1 else: result.append('z') m=m-1 k=-cb result.extend(['a']*n) result.extend(['z']*m) print(''.join(result))처음에 풀었을때는  comb(n..

• format_list_bulleted 알고리즘/백준
• · 2024. 8. 5.
• textsms

백준 1759번: 암호 만들기

이것도 조합 문제이다. 입력된 수와 조건을 바탕으로 해당하는 암호들만 출력해주면 되는 문제이다.import sysfrom itertools import combinationslst1=[]input = sys.stdin.readlinel, c = map(int, input().split())clist = list(input().split())lst=list(combinations(clist,l))for i in lst: lst1.append(sorted(i))lst1.sort()[print("".join(i)) for i in lst1]처음에는 itertools 라이브러리로 모든 조합의 경우들을 list에 담아둔후, 오름차순을 해주려고 했다. 근데  최소 한 개의 모음(a, e, i, o, u)과 최..

• format_list_bulleted 알고리즘/백준
• · 2024. 7. 8.
• textsms

백준 11051번: 이항 계수 2

이전 조합론에서 난이도가 한단계 더 높아진 문제이다. 이항계수(조합수)를 구해서 10007로 나머지를 구하는 문제이다.그냥 이론을 코드로 구현한다긴 보다는, dp로 간단하게 풀수 있는 방법을 찾아야하는 문제이다.import sysfrom math import combinput = sys.stdin.readlinen, m = map(int, input().split())nlist=[i for i in range(1,n+1)]print((comb(n,m)%10007))그전에 라이브러리를 이미 알아서 금방 푼 문제지만, 이런 라이브러리가 안통할수 있는 문제가 있으므로 다른 알고리즘을 공부해야한다.

• format_list_bulleted 알고리즘/백준
• · 2024. 7. 8.
• textsms