📌문제 출처 솔브닷 클래스 3+ 단계 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net ❓ 문제 ❗ 풀이 BFS 응용 📗 풀이 코드 import sys from collections import deque input = sys.stdin.readline # bfs 생성 def bfs(): # 익은 토마토 위치(y행, x열)로부터 다음날 익게되는 토마토 위치 추가 global stack, not_good cnt = 0 # 최초 날짜..
📌문제 출처 백준 단계별 문제풀이 - 동적계획법 2단계 https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net ❓ 문제 ❗ 풀이 deque와 defaultdict 사용 📗 풀이 코드 import sys input = sys.stdin.readline from collections import defaultdict, deque _ = int(input()) weights = deque(list(map(int,input().split()))) _ = int..
📌문제 출처 백준 단계별 문제풀이 - 동적 계획법 2단계 https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net ❓ 문제 ❗ 풀이 동적계획법 2단계 11066 파일합치기와 유사한 풀이 활용 https://nembizzang.tistory.com/135 📗 풀이 코드 import sys input = sys.stdin.readline n = int(input()) nums = [list(map(int,input().split())) for ..
📌문제 출처 솔브닷 class 3+ 단계 https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net ❓ 문제 ) ) ❗ 풀이 재귀, 분할 정복 📗 풀이 코드 import sys input = sys.stdin.readline def zearch(n,r,c): if n==0: return 0 nr,rr = divmod(r,2) nc,rc = divmod(c,2) return 2*rr + rc + 4*zearch(n-1,nr,nc) n,r,c = m..
📌문제 출처 솔브닷 class 1++ 단계 https://www.acmicpc.net/problem/2475 2475번: 검증수 컴퓨터를 제조하는 회사인 KOI 전자에서는 제조하는 컴퓨터마다 6자리의 고유번호를 매긴다. 고유번호의 처음 5자리에는 00000부터 99999까지의 수 중 하나가 주어지며 6번째 자리에는 검증수가 들 www.acmicpc.net ❓ 문제 ❗ 풀이 lambda 함수 활용 📗 풀이 코드 print(sum(map(lambda x : (x**2), map(int,open(0).read().split())))%10) 📗 코드 해설 open(0).read()로 입력값 한줄을 문자열 형태로 받고 split()으로 공백을 기준으로 숫자로 된 문자열들로 분리한다. 이후 map()함수 내에서 i..
📌문제 출처 솔브닷 class 3+ 단계 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net ❓ 문제 ❗ 풀이 dp 활용 📗 풀이 코드 import sys input = sys.stdin.readline for _ in range(int(input())): n = int(input()) dp = {i:[] for i in range(n+1)} dp[0]=[1,0] dp[1]=[0,1] for i in range(2,n+1): dp[i] = [dp[i-1][j]+dp[i-2][j] for j in range(2)] print(*dp[n]) 📗 코..
📌문제 출처 백준 단계별 문제풀이 - 분할 정복 https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net ❓ 문제 ❗ 풀이 dfs, 분할정복 알고리즘 사용 📗 풀이 코드 import sys input = sys.stdin.readline def dac(paper,len_set,n): if len_set == 1: # 종이의 원소 집합 길이가 1이라면 ans[paper[0][0]] += 1 else : # 그렇지 않다면 분할진행 for i in..
📌문제 출처 백준 단계별 문제풀이 - 그래프와 순회 https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net ❓ 문제 ❗ 풀이 bfs 활용 📗 풀이 코드 import sys from collections import deque input = sys.stdin.readline def bfs(sta_y,sta_x): # 최초 위치(x,y)를 넣고 최소이동횟수를 반환하는 bfs 생성 stack = deque([[sta_y,sta_x,0]]) while stac..