DP란?DP란 메모리 [ex) 데이터를 담아놓을 수 있는 변수 등]에 저장하여 수행시간을 비약적으로 향상시키는 방법연속적인 연산에 있어서 이미 계산된 결과를 메모리에 저장하여 다시 계산하지 않고 활용Top-Down, Bottom-Up 방식이 있음DP 알고리즘을 사용해야 하는 경우최적 부분 구조 : 큰 문제를 작은 문제로 나눌 수 있고, 작은 문제를 모아서 큰 문제를 해결할 수 있는 경우중복되는 부분 문제 : 동일한 문제를 반복적으로 해결해야 하는 경우DP 알고리즘을 사용해야 할 경우 가장 먼저 해야할 것제시된 문제에서 문제 해결을 위해 필요한 '일정한 규칙'을 찾고 이를 위한 점화식을 도출
공부
import sysinput = sys.stdin.readlinen = int(input())# 계단의 점수를 저장. 1층 부터 저장한다.stairs = [0] * 301for i in range(1, n + 1): stairs[i] = int(input())# 첫 번째 칸은 3칸 연속 밟을 수 없는 규칙에 해당하지 않음dp = [0] * 301dp[1] = stairs[1]dp[2] = stairs[1] + stairs[2]dp[3] = max(stairs[1] + stairs[3], stairs[2] + stairs[3])# 점화식을 계산for i in range(4, n + 1): # 계단은 3칸 연속 오를 수 없음 # 1. 현재 계단의 3칸 전까지의 dp값 + 한칸 전의 점수 + 현재 ..
import sysinput = sys.stdin.readline# dp는 연산 횟수의 최솟값 리스트dp = [0] * 1000001 n = int(input())# n이 1일 경우 아무런 연산할 필요 없이 연산 횟수는 0# 따라서 2부터 시작for i in range(2, n+1): # 1. 1을 빼는 경우 dp[i] = dp[i-1] + 1 # 2. 2로 나누는 경우 if i % 2 == 0: # 1번 경우와 2번 경우를 비교하여 작은 값을 dp[i]에 담는다 dp[i] = min(dp[i], dp[i//2] + 1) # 3. 3으로 나누는 경우 if i % 3 == 0: # 위에서 구한 연산 횟수와 3번..
import sysinput = sys.stdin.readlinen, m = map(int, input().split())pocket = {}for i in range(n): name = input().rstrip() pocket[i+1] = name# reversed로 dictionary의 key와 value를 바꿔줄 수 있음pocket_reversed = dict(map(reversed, pocket.items())) for _ in range(m): x = input().rstrip() # isdigit()으로 숫자 형식인지 판별 if x.isdigit(): x = int(x) print(pocket[x]) else: ..
1. %를 이용한 풀이import sysinput = sys.stdin.readlineN, K = map(int, input().split())array = [x+1 for x in range(N)]removed = []idx = 0while array: idx += K-1 # idx가 배열의 길이를 초과하면 다시 처음으로 돌아간다. idx = idx%len(array) removed.append(array.pop(idx))# f""과 join을 활용하여 출력print(f"") 2. deque를 이용한 풀이import sysfrom collections import dequeinput = sys.stdin.readlineN, K = map(int, input().split())que..
얼핏 보기엔 매우 간단한 A리스트에서 M리스트의 값을 찾는 문제이지만 시간 제한에 함정이 있다.처음엔 in으로 쉽게 풀어보려 했지만 시간 초과가 났다. 검색해보니 본 문제는 '이진 탐색' 알고리즘을 적용하여 풀어야 하는 문제였다. (in으로 풀지 못하는 건 아니다) in, 이진 탐색 두 가지 풀이로 풀어보았다. 1. in을 사용한 풀이import sysinput = sys.stdin.readlineN = int(input())# set으로 미리 중복을 제거해주지 않으면 시간 초과N_list = set(list(map(int, input().split())))M = int(input())M_list = list(map(int, input().split()))for i in M_list: if(i in..
import sysinput = sys.stdin.readlineN = int(input())# 리스트 컴프리헨션으로 words 생성words = [input().rstrip() for _ in range(N)]# 문자 리스트의 중복을 제거words = list(set(words))# sort를 2번 실행# words.sort() -> 1. 사전을 기준으로 정렬# words.sort(key=len) -> 2. 문자 길이를 기준으로 정렬# sort에 조건 2개 추가 (길이, 사전적 정렬)words.sort(key=lambda x: (len(x), x))# sorted 사용 (sort와 달리 결과 return)# words = sorted(words, key=lambda x: (len(x), x))for i..
import sysinput = sys.stdin.readlinen = int(input())member = []for _ in range(n): age, name = input().rstrip().split() age = int(age) # 간단한 정렬을 위해 key가 없는 tuple 형식으로 리스트에 입력 member.append((age, name)) # sorted 함수를 활용해 정렬# 정렬 기준인 key를 lambda 함수로 tuple의 0번째(age)를 기준으로 잡음member = sorted(member, key=lambda x: x[0])for i in member: print(i[0], i[1]) 참고한 블로그 파이썬 마스터하기 : 람다(Lambda..
import sysinput = sys.stdin.readlinewhile True: nums = list(map(int, input().split())) # a,b,c 모두가 0일 경우 break if sum(nums) == 0: break # nums 배열을 오름차순으로 정렬 nums.sort() # a제곱 + b제곱 = c제곱일 시 맞음 if nums[2] ** 2 == (nums[0] ** 2 + nums[1] ** 2): print("right") else: print("wrong")
import sysinput = sys.stdin.readline# X번 반복X = int(input())# 1픽셀당 1만큼 배열을 차지한다고 가정, 전체 = 100paper = [[0] * 100 for _ in range(101)]# 채워진 부분의 넓이area = 0for _ in range(X): h, v = map(int, input().split()) # 주어진 위치값에 해당하는 paper 부분을 1로 채워준다 for i in range(h, h+10): for j in range(v, v+10): paper[i][j] = 1 for i in range(len(paper)): # paper에서 1이 있는 만큼 넓이에 더함..
