백준 1012번 -유기농 배추

BFS와 DFS 모두 활용할 수 있는 연습문제라고 생각하면 된다. 너비 우선 탐색(BFS)을 사용하는 이유최단 경로 탐색에 유리하다.BFS는 탐색을 가까운 노드부터 순차적으로 넓혀가며 수행하기 때문에, 시작 지점에서 특정 목표 지점까지의 최단 경로를 찾을 때 유리하다. 예를 들어 미로 탐색에서 출발점에서 도착점까지의 최단 경로를 찾을 때, BFS는 가장 먼저 목표 지점에 도달하는 경로가 최단 경로가 되므로 이를 바로 반환할 수 있다.모든 노드를 고르게 탐색한다.BFS는 한 지점에서 출발하여 깊이를 하나씩 늘리며 탐색하므로, 모든 노드를 고르게 탐색한다. 모든 인접 노드들을 차례로 확인하며 탐색하므로 특정 노드들이 더 깊게 우선 탐색되는 일이 없다. 이 점은 깊이 우선 탐색(DFS)과 다르며, 특히 그래프..

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

백준 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