dev/알고리즘문제풀이13 [ 백준 2637번 ] 장난감 조립 파이썬 [ 백준 2637번 장난감 조립 바로가기] 2637번: 장난감 조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net 논리 input을 받으며 인접행렬 구성 진입차수가 0인 부품들은 기본 부품 각 기본부품들마다 dfs수행, 이 과정에서 만나는 노드들의 값을 기록해놓는다 기록된 값들 중 기본 부품의 것들만 출력한다 코드 import sys from collections import defaultdict def toy_assembly(): def _dfs(curr): # base case: 완제품인 경우 if c.. 2021. 8. 24. [ 백준 2617번 ] 구슬찾기 파이썬 [백준 2617번 구슬찾기 바로가기] 2617번: 구슬 찾기 모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 www.acmicpc.net 논리 같은 함수를 사용하기 위해 인접행렬을 2개 만든다(무거운 순서, 가벼운 순서; transpose 관계) 각 노드마다 dfs를 통해 하위 노드의 개수를 파악한다(무거운 순서, 가벼운 순서 2번 진행) 노드 중 가벼운 것의 개수나 무거운 것의 개수가 중간 초과일 경우 이는 불가능한 노드 --> 개수 파악 코드 import sys def counting(N: int, graph: list[list[int]].. 2021. 8. 24. [ 백준 2294번 ] 동전2 파이썬 [백준 2294번 동전2 바로가기] 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 논리 주어진 동전 중복 제거 target에서 각 동전을 빼는 방법으로 bfs 탐색 target이 0이 되는 경우 반환(target이 음수가 되는 경우 무시) 모든 경우를 탐색해도 target이 0이 되는 경우가 없으면 -1 반환 코드 import sys from collections import deque, defaultdict # using BFS + 중간 기록 def minimum_coins(.. 2021. 8. 24. [ 백준 7569번 ] 토마토 파이썬 [백준 7569번 토마토 바로가기] 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 힌트 더보기 https://www.youtube.com/watch?v=5i-GDvqldc8 논리 모든 토마토기 익는 최단 시간 --> bfs활용 날짜 구분 --> 같은 날짜의 토마토들은 큐에 False로 구분 ex) (오늘토마토1, 오늘토마토2, False, 내일토마토1, 내일토마토2..) 코드 import sys from collections import deque def tomato(): ######.. 2021. 8. 24. 이전 1 2 3 4 다음
