본문 바로가기

전체 글

 (261)
[백준] 1912 : 연속합 python https://data-marketing-bk.tistory.com/52 백준 - 1912번 - 연속합[파이썬] 1. 문제 출처 백준 - 1912번: 연속합 문제로 이동하기 우선 링크로 가서 문제를 보도록 하자. 2. 문제 설명 문제 n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 data-marketing-bk.tistory.com 위 포스트를 참고했는데 이전까지의 합이 그냥 i번째 숫자보다 작은 경우 이전의 기록들은 무의미하다는 문장이 큰 도움이 됐다. 현재값보다 연속된 수들의 누적합이 더 크다면 그 값을 쓰고, 현재값이 더 크다면 이전 값은 의미가 없으니 현재값으로 갱신을 한다. 현재값과 그 이전값들의 합을 비교하는 것이니 메모리를 추가로 사용할 필요도 없다. n..
[백준] 2156 : 포도주 시식 python 세 잔을 연속해서 마실 수 없기 때문에 (마시는 걸 O, 마시지 않는 걸 X라고 했을 때) OXO : dp[i-3]+dp[i-2]+arr[i] XOO : arr[i-1]+arr[i] 이 두 가지 경우를 생각했는데 마지막잔을 마시지 않아도 된다는 점을 간과해서 문제가 풀리지 않았다. OOX : dp[i-1] 인 경우도 구해서 세 가지 경우 중 최댓값인 걸 dp[i]에 저장하도록 해서 해결했다. import sys input = sys.stdin.readline n=int(input()) arr = [int(input()) for _ in range(n)] dp = [0]*n dp[0] = arr[0] if n>1: dp[1] = arr[0]+arr[1] if n>2: dp[2] = max(dp[1], ar..
[SWEA] 1206 : [S/W 문제해결 기본] 1일차 - View python https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV134DPqAA8CFAYh&categoryId=AV134DPqAA8CFAYh&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com n을 입력받고 집의 높이들을 arr라는 리스트에 저장한다. arr[0], arr[1], arr[n-2], arr[n-1]은 0이기 때문에 arr[2]부..
[백준] 14002 : 가장 긴 증가하는 부분 수열 4 python n = int(input()) A = list(map(int,input().split())) # A에 저장된 각 값들까지의 가장 긴 증가하는 부분 수열의 길이를 저장하는 배열 # A에 저장된 0번째 수까지의 가장 긴 증가부분수열의 길이는 1이므로 # 1로 초기화함 dp=[1]*n # A에 저장된 1번째값부터 자신의 앞에 있는 수들과 비교를 함 for i in range(1,n): for j in range(i): # 자신이 더 크다면 기존의 증가부분수열의 길이와 # 부분수열에 자기자신을 추가했을 때의 길이 중 더 긴 것으로 업데이트함 if A[i]>A[j]: dp[i] = max(dp[j]+1, dp[i]) # 가장 긴 증가부분수열의 길이를 저장함 order = max(dp) # 증가부분수열의 실제 값을..
[백준] 1932 : 정수 삼각형 python 첫번째행부터 자신의 위에서 나올 수 있는 최대값에 자신을 더하는 방식으로 문제를 풀어나갔다. 0번째열이라면 dp[i-1][j]+자기자신이 답이니 바로 저장하고 열값이 0보다 크다면 dp[i-1][j-1]과 dp[i-1][j]중 더 큰 값에 자기자신을 더한 걸 dp테이블에 저장하도록 했다. n = int(input()) arr = [list(map(int,input().split())) for _ in range(n)] dp = [[0]*n for _ in range(n)] dp[0][0] = arr[0][0] # 1부터 n-1행까지 for i in range(1,n): # 0 부터 i까지 for j in range(i+1): # 0번째 열이면 if j ==0: dp[i][j]=dp[i-1][j]+arr[..
[백준] 12865 : 평범한 배낭 python [물건의 개수]x[가방에 넣을 수 있는 최대 무게] 크기의 dp행렬을 생성하고 0으로 초기화한다. 물건을 하나씩 보면서, 현재 물건을 넣을 수 없다면 기존의 가치값을 그대로 가져오고 넣을 수 있다면 기존의 가치와 현재 물건을 넣을 수 있는 시점에서의 가치 + 현재 물건의 가치 중 큰 값을 저장한다. n,k = map(int,input().split()) item = [[0]*2 for _ in range(n+1)] for i in range(1,n+1): item[i] = list(map(int,input().split())) dp = [[0]*(k+1) for _ in range(n+1)] for i in range(1,n+1): for j in range(1,k+1): weight = item[i][..
[백준] 1149 : RGB거리 python 전체 비용이 최소가 되기 위해서 마지막집이 R일 때, G일 때, B일 때 모두를 계산하고 그중 최소인 것을 출력한다. 이때 i번째 집은 i-1번째 집과 다른 색이어야 한다는 조건이 있기 때문에 i번째 집이 R인 경우에는 i-1번째 집이 G거나 B여야 하고 i번째 집이 G인 경우에는 i-1번째 집이 R이거나 B여야 하고 i번째 집이 B인 경우에는 i-1번째 집이 R이거나 G여야 한다. n = int(input()) color = [0]*(n) for i in range(n): color[i] = list(map(int,input().split())) for i in range(1,n): color[i][0] += min(color[i-1][1],color[i-1][2]) color[i][1] += min(..
[백준] 24416 : 알고리즘 수업 - 피보나치 수 1 문제에서 말하는 대로 풀었는데 Python3으로 제출하니 시간초과가 나왔고, PyPy3로는 정답판정이 나왔다. n = int(input()) def recursive_fibo(x): global cnt_recursive if x==1 or x==2: cnt_recursive +=1 return 1 return recursive_fibo(x-1)+recursive_fibo(x-2) def dp_fibo(x): global cnt_dp dp = [1]*(x+1) for i in range(3,x+1): dp[i] = dp[i-1]+dp[i-2] cnt_dp += 1 cnt_recursive = 0 cnt_dp = 0 recursive_fibo(n) dp_fibo(n) print(cnt_recursive, c..

티스토리툴바