Python 42

python 백준 11660 구간 합 구하기 5

dp 활용 시작지점부터 현재 좌표까지의 합을 dp에 기록 dp에 기록된 값을 활용하여 값 계산 (x1,y1)~(x2,y2)의 합은 dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1] (이건 겹치는 부분) 그림으로 그리면 이해가 쉬울텐데 그림 그릴 도구가 없다.. import sys N,M = map(int,sys.stdin.readline().split()) arr = [list(map(int,sys.stdin.readline().split())) for _ in range(N)] dp = [[0]*(N+1) for _ in range(N+1)] for i in range(1,N+1): for j in range(1,N+1): if j == 0: dp[..

python 백준 9251 LCS

https://www.acmicpc.net/problem/9251 dp 활용 dp의 크기는 (문자 길이 * 문자 길이) + 패딩 비교하는 알파벳이 같아야 길이가 1 증가 이 경우 최대 길이 == 두 문자에서 각각의 해당 알파벳 선택 전의 길이 + 1 비교하는 알파벳이 다를 경우 최대 길이 == 기존 값의 최대 길이 def solve(): for i in range(n1): for j in range(n2): if t1[i] == t2[j]: dp[i+1][j+1] = dp[i][j]+1 else: dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j]) t1 = input() t2 = input() n1 = len(t1) n2 = len(t2) dp = [[0]*(n2+1) for _ ..

python 백준 15663 N과 M (9)

https://www.acmicpc.net/problem/15663 최적화 하는데 좀 힘들었다. counting 배열을 적극 활용 주어진 숫자 counting 경우의 수로 만들고 있는 수열에 사용된 숫자 counting 두 counting 을 비교한 결과를 이용하여 백트래킹 재귀활용 수열의 길이가 M이 될때까지 재귀 def solve(ls,l): # ls = 현재 만들고 있는 순열, l = 순열의 길이 if l == M: sol.append(ls) return for num in nums: # 초기 nums에 들어있던 숫자 보다 작은 개수만 사용하게 설계 if lscount[num] < count_num[num]: lscount[num] += 1 solve(ls+[num],l+1) lscount[num]..

python 백준 11053 가장 긴 증가하는 부분 수열

dp 활용 index : index번호가 수열의 마지막 번호 일 때 될 수 있는 수열의 최장 길이 기본값 1 : 자기 자신 하나로 이루어진 수열은 최소 존재해서 1로 설정 solve 함수 앞에서 부터 차근차근 진행(i는 0부터 N까지) 기존의 값들과 비교 (j는 0부터 i까지) A[j] < A[i] 이면 그 숫자 뒤에 연결하여 수열을 만들 수 있으므로 이 경우 최대값이 갱신 되면 갱신 def solve(): for i in range(N): for j in range(0,i): if A[j] < A[i]: dp[i] = max(dp[i],dp[j]+1) N = int(input()) A = list(map(int,input().split())) dp = [1]*N solve() print(max(dp))

python 백준 16953 A - > B

https://www.acmicpc.net/problem/16953 BFS 방식 활용 que에 2배를 곱한 경우, 1을 맨 오른쪽에 추가한 경우를 추가 // 이 모든 경우는 값이 증가하는 방향 que에서 나온 숫자가 목표인 B 보다 클 경우 더 이상의 연산을 하여도 B가 될 수 없기에 continue를 이용하여 연산 포기 from collections import deque def transnum(): que = deque() que.append(A) cnt = 0 while que: cnt += 1 for _ in range(len(que)): # BFS 깊이를 계산하기 위해 FOR문 사용 t = que.popleft() if t == B: # 연산 결과가 B가 될 경우 return cnt if t >..

python 백준 1753 최단경로

https://www.acmicpc.net/problem/1753 다익스트라 활용 처음 해보는 다익스트라, 많이 부족 현재 코드로는 pypy 제출시에만 통과가 가능 가장 짧은 길이를 가진곳 찾는건 heap을 쓰면 최적화가 가능할듯 싶다. for _ in range() 대신 while heap 형태 import sys def dijkstra(): # 모든 번호에 대한 최단거리 찾아야 하므로 for _ in range(V): minlength = INF select = 0 # 방문한 적은 없고, 가장 짧은 길이를 가진곳 찾기 for i in range(1, V + 1): if not visited[i] and sol[i] < minlength: minlength = sol[i] select = i visit..

python 백준 2407 조합

https://www.acmicpc.net/problem/2407 1C0 = 1 , 1C1=1 2C0 = 1 , 2C1 = 2 , 2C2 = 1 3C0 = 1 , 3C1 = 3 , 3C2 = 3 , 3C3 = 1 4C0 = 1 , 4C1 = 4 , 4C2 = 6 , 4C3 = 4, 4C4 = 1 nCm = (n-1)C(m-1) + (n-1)C(m) 이라는 규칙이 있음을 활용 (n-1)C(m-1) = (n-2)C(m-2) + (n-2)C(m-1) (n-1)C(m) = (n-2)C(m-1) + (n-2)C(m) 계산기 (n-2)C(m-1)을 이미 계산했는데 또 계산해야 하는 상황 발생 dp를 활용하여 계산 횟수를 줄임 def combination(a,b): if dp[a][b]: return dp[a][b]..

python 18511 큰 수 구성하기

https://www.acmicpc.net/problem/18511 브루트포스 형식으로 경우의 수 구성 목표인 N과 동일한 자리수를 가진경우 목표인 N의 자리수보다 1 만큼 작은 경우(N = 100인데 사용 가능한 숫자가 9인경우 99를 만들기 위해) 이미 N값보다 커졌을 경우 가지치기 def check(i,total): global ans if total > N: return if i < 0 : if ans < total: ans = total return for num in nums[::-1]: # 디버깅 쉽게 하려고 [::-1] check(i-1,total+num*10**i) N,K = map(int,input().split()) n=len(str(N))-1 nums = list(map(int,in..

Python Print

print() : () 안의 값을 출력해주는 함수 print('hello world') # hello world 출력 str.format() yourname = 고객 myname = ljm print('안녕하세요, {}님! 제 이름은 {}입니다'.format(yourname,myname) # 안녕하세요, 고객님! 제 이름은 ljm입니다 %-formatting %s : 문자열 출력 %d : 정수 출력 %f : 실수 출력 say = world score = 4.4 print('Hello, %s' % say) # Hello, world print('내 성적은 %d' % score) # 내 성적은 4 print('내 성적은 %f' % score) # 내 성적은 4.4 f-strings (개인적으로 제일 자주 사..

SW/python 2022.04.14