모눈종이에 사각사각

🍎 [백준 1707] 이분 그래프 문제링크 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net ⚾ 코드 (PyPy3 제출) from collections import deque K = int(input()) def bfs(graph, i): q = deque() q.append(i) while q: now = q.popleft() for node in graph[now]: if visited[node] == visited[now]: return F..

🍎 [백준 1697] 숨바꼭질 문제링크 https://www.acmicpc.net/problem/1697 ⚾ 코드 from collections import deque N, K = map(int, input().split()) visited = [False for _ in range(200001)] # visited = False or True dx = [1, -1, 2] # move result = 0 q = deque() # start visited[N] = True q.append([N, 0]) while q: x, count = q.popleft() if x == K: # if subin and her sister equal, break result = count break for i in ran..

🍎 [백준 1654] 랜선 자르기 문제링크 https://www.acmicpc.net/problem/1654 이전에 풀었던 2805번 나무 자르기 문제와 굉장히 유사한 문제였다. ⚾ 코드 import sys k, n = map(int, input().split()) array = [int(sys.stdin.readline()) for _ in range(k)] start = 1 end = max(array) while start

🍎 [백준 2805] 나무 자르기 문제링크 https://www.acmicpc.net/problem/2805 ⚾ 코드(pypy3) import sys input = sys.stdin.readline n, m = map(int, input().split()) tree = list(map(int, input().split())) end = max(tree) start = 0 while start mid: remain += i-mid if remain < m: end = mid-1 else: start = mid+1 print(end) 🔔 해결 과정 & 깨달은 점 - 해당 문제는 전형적인 이진탐색 문제이다. - 입력 값이 20억이므로 이진 탐색을 시도해보자. - 처음에 cm가 아닌, 인덱스의 중앙값으로 시도를..

🍎 [백준 2294] 동전2 문제 링크 https://www.acmicpc.net/problem/2294 ⚾ 코드 코드 1 n, k = map(int, input().split()) dp = [100001]*100001 coins = [int(input()) for _ in range(n)] coins.sort() for coin in coins: for now in range(1, k+1): if now % coin != 0: dp[now] = min(dp[now], dp[now-coin]+1) else: dp[now] = min(dp[now], now//coin) if dp[k] == 100001: print(-1) else: print(dp[k]) 코드 2 n, k = map(int, input()..

🍎 [백준 11727] 2×n 타일링 2 문제링크 https://www.acmicpc.net/problem/11727 ⚾ 코드 n = int(input()) dp = [0]*(n+1) dp[1] = 1 dp[2] = 3 for i in range(3, n+1): dp[i] = (dp[i-1]+(dp[i-2]*2)) % 10007 print(dp[n]) 🔔 해결 과정 & 깨달은 점 - 다음은 내가 문제를 풀면서 생각한 아이디어 이다. - 각 N은 (이전(N-1)의 경우의 수 + 2*1 타일 추가한 것) + (전전(N-2)의 경우의 수 + 2*2 타일 또는 2*1 타일 2개 추가한 것) 으로 이루어져 있다. - 새로 추가하는 타일 이외의 경우의 수는 이전의 N의 경우의 수에 포함되어 있기 때문에 따로 생각하..

🍎 개미 전사 🏀 문제 (문제 요약) 개미 전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 한다. 식량 창고는 일직선으로 이어져 있다. 개미 전사는 식량창고를 선택적으로 약탈할 것이다. 인접한 식량 창고가 공격을 받으면 메뚜기 정찰병들에게 들킨다. 개미 전사는 정찰병에게 들키지 않고 최대한 많은 식량을 얻기를 원한다. ⚾ 코드 n = int(input()) store = list(map(int, input().split())) dp = [0]*n dp[0] = store[0] dp[1] = max(store[0], store[1]) for i in range(2, n): dp[i] = max(dp[i-1], dp[i-2]+store[i]) print(dp[n-1]) 🔔 해결 과정..

🍎 1로 만들기 🏀 문제 정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지 이다. a. X가 5로 나누어 떨어지면, 5로 나눈다. b. X가 3으로 나누어 떨어지면, 3로 나눈다. c. X가 2로 나누어 떨어지면, 2로 나눈다. 정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. ⚾ 코드 num = int(input()) INF = 1e9 dp = [INF] * (num+1) for i in range(2, num+1): if i == 1: dp[i] = 0 elif i == 2 or i == 3 or i == 5: dp[i] = 1 else: if i % 2 == 0: dp[i] = min(dp[i], dp[i..

🍎 [백준 1260] DFS와 BFS 문제 링크 ⚾ 코드 from collections import deque # 정점의 개수 N(1 ≤ N ≤ 1,000) # 간선의 개수 M(1 ≤ M ≤ 10,000) # 탐색을 시작할 정점의 번호 V N, M, V = map(int, input().split()) graph = [[] for _ in range(N+1)] visited = [False]*(N+1) for _ in range(M): a, b = map(int, input().split()) # 양방향이기 때문에 리스트 두 군데 다 추가해주어야 한다. graph[a].append(b) graph[b].append(a) # 인접 리스트를 사용할 것이기 때문에 정렬이 필요함. for i in range(N..

🍎 Letter Combinations of a Phone Number 문제 링크 💿 문제 Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order. A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters. ⚾ 코드 def solution(digits): # 알파벳 매핑 alpha = [[], [], ['a', 'b', '..