📌문제 출처 솔브닷 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..
📌문제 출처 백준 단계별 문제풀이 - 스택 2 https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net ❓ 문제 ❗ 풀이 스택과 인덱스 활용 📗 풀이 코드 import sys input = sys.stdin.readline n = int(input()) nums = list(map(int,input().split())) ans = [-1]*n stack = [] # 오큰수를 찾아야하는 nums의 인덱스를 담아준다. for i in range(n): # stack이..
📌문제 출처 백준 단계별 문제풀이 - 동적 계획법 2 https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net ❓ 문제 ❗ 풀이 dp : 냅색 문제 응용 📗 풀이 코드 import sys input = sys.stdin.readline n,m = map(int,input().split()) memories = list(map(int,input().split())) costs = list(map(int,input().split())) dp = [[0]*(sum(..
📌문제 출처 백준 단계별 문제풀이 - 동적 계획법 2 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net ❓ 문제 ❗ 풀이 dp 활용 📗 풀이 코드 import sys input = sys.stdin.readline n,k = map(int,input().split()) coins = [int(input()) for _ in range(n)] dp = [0]*(k+1) dp[0] = 1 # 0으로 0을 만드는 방법 1가지 추가, 이걸 지정해줘야 첫번..
