티스토리

bright

검색하기

블로그 홈

bright

bright-code.tistory.com/m

알고리즘 자격증 2021 취업 목표 !!

구독자: 0

방명록 방문하기

주요 글 목록

# 10942 팰린드롬? 파이썬 www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net # 시간 초과 from collections import deque n = int(input()) data = list(map(int,input().split())) m = int(input()) result = [1]*m for i in range(m): s,e = map(int,input().split()) if e-s 1 : if d.pop() != d.popleft() : result[i] = 0 for i in range(m): print(.. 공감수 0 댓글수 0 2021. 4. 9.
# 10211 Maximum Subarray 파이썬 www.acmicpc.net/problem/10211 10211번: Maximum Subarray 크기 N인 정수형 배열 X가 있을 때, X의 부분 배열(X의 연속한 일부분) 중 각 원소의 합이 가장 큰 부분 배열을 찾는 Maximum subarray problem(최대 부분배열 문제)은 컴퓨터 과학에서 매우 잘 알려져 있 www.acmicpc.net t = int(input()) def max_sub(): n = int(input()) data = list(map(int,input().split())) for i in range(1,len(data)): data[i] += data[i-1] if data[i-1]>0 else 0 return max(data) p = [] for i in range(t).. 공감수 0 댓글수 0 2021. 4. 9.
# 1890 점프 파이썬 www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net import sys n = int(input()) graph = [list(map(int, input().split())) for i in range(n)] d = [ [0]*n for _ in range(n) ] d[0][0] = 1 for i in range(n): for j in range(n): if i == j == n-1 : break a = graph[i][j] if i+ a < n : .. 공감수 0 댓글수 0 2021. 4. 8.
# 9465 스티커 파이썬 www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net def sticker(n,data): data[0][1] += data[1][0] data[1][1] += data[0][0] for j in range(2,n): data[0][j] += max( data[1][j-2], data[1][j-1] ) data[1][j] += max ( data[0][j-2], data[0][j-1] ) return max(data[0][n-1], data[1][n-1.. 공감수 0 댓글수 0 2021. 3. 11.
# 11722 가장 긴 감소하는 부분 수열 n = int(input()) # n data[i]: dp[i] = max(dp[i], dp[j]+1) print ( max(dp) ) 공감수 0 댓글수 0 2020. 9. 17.
# 1965 상자넣기 # 가장 긴 증가하는 수열 찾기랑 비슷 n = int(input()) # n 공감수 0 댓글수 0 2020. 9. 17.
# 1904 01타일 n = int(input()) # n 공감수 0 댓글수 0 2020. 9. 17.
# 13301 타일 장식물 n = int(input()) dp = [0]*81 dp[0]=1 dp[1]=1 for i in range(2,n): dp[i] = dp[i-1]+dp[i-2] r = dp[n-1] + dp[n-1] + dp[n-2] print( r+r ) # 런타임 에러 이유 : dp = [0]*n 으로 했더니 런타임 에러가 났다. 크기는 항상 주어진 값 보고 그 것 보다 하나 더 크게 잡아줄 것. www.acmicpc.net/problem/13301 13301번: 타일 장식물 대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개�� www.acmicpc.net 공감수 0 댓글수 0 2020. 9. 17.
# 9252 LCS2 a = input() b = input() la, lb = len(a), len(b) dp = [ [0]*(lb+1) for _ in range(la+1) ] lcs = [ ['']*(lb+1) for _ in range(la+1) ] for i in range(1,la+1): for j in range(1,lb+1): if a[i-1] == b[j-1] : dp[i][j] = 1+ dp[i-1][j-1] lcs[i][j] = lcs[i-1][j-1] + b[j-1] else : if dp[i-1][j] > dp[i][j-1] : n,m = i-1, j else : n, m = i, j-1 dp[i][j] = dp[n][m] lcs[i][j] = lcs[n][m] print(dp[i][j]) print(.. 공감수 0 댓글수 0 2020. 9. 17.
# 9251 LCS ( 개념 ) a = input() b = input() la = len(a) lb = len(b) dp = [ [0]*(lb+1) for _ in range(la+1) ] for i in range(1,la+1): for j in range(1,lb+1): if a[i-1] == b[j-1] : dp[i][j] = 1+ dp[i-1][j-1] else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) # print(dp[i]) print( dp[la][lb] ) www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 .. 공감수 0 댓글수 0 2020. 9. 17.
# 11048 이동하기 n,m = map(int,input().split()) # n : 열 m : 행 candy = [] for i in range(n): candy.append(list(map(int,input().split()))) dp = [ [0]*m for i in range(n) ] for i in range(n): for j in range(m): a = i -1 b = j -1 tmp = [0] if a >= 0 : tmp.append( dp[a][j] ) if b >=0 : tmp.append( dp[i][b] ) if a >= 0 and b >=0 : tmp.append( dp[a][b] ) dp[i][j] = candy[i][j] + max(tmp) print(dp[n-1][m-1]) dp 에 각 칸에서 .. 공감수 0 댓글수 0 2020. 9. 15.
# 9625 BABBA k = int(input()) # 1 BA a ,b = [0]*(k+1), [0]*(k+1) a[0], b[0] = 1,0 for i in range(1,k+1): if i == 1 : a[1] = 0 b[1] = 1 continue a[i] = b[i-1] b[i] = a[i-1] + b[i-1] print (a[k],b[k]) # 다이나믹으로 풀면... k = int(input()) # 1 BA a ,b = 1, 0 for i in range(k): if i == 0 : a = 0 b = 1 continue tmp = a a = b b = tmp + b print (a,b) # 왜 다이나믹..? 공감수 0 댓글수 0 2020. 9. 15.
# 11660 구간 합 구하기 5 ( 다시 하기. . 시간 초과 해결 x ) # 시간 초과 ( 완전 탐색 ) n , m= map(int, input().split()) data=[] for i in range(n): data.append( list(map(int,input().split())) ) xy = [] for i in range(m): xy.append(list(map(int,input().split()))) def cal( xy ): s = 0 for i in range(xy[0]-1,xy[2]): for j in range(xy[1]-1,xy[3]): s += data[i][j] print (s) for i in range(m): cal(xy[i]) # 정답 ( 다이나믹 ) 공감수 0 댓글수 0 2020. 9. 14.
# 12865 평범한 배낭 - https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net n, k = map(int, input().split()) # n 은 물건의 수 k 는 총 무게 w = [0]*n v = [0]*n for i in range(n): w[i],v[i] = map(int,input().split()) dp = [ [0]*(k+1) for _ in range(n+1) ] for i in range(n+.. 공감수 0 댓글수 0 2020. 9. 14.
# 2502 떡 먹는 호랑이 d,k = map(int,input().split()) # d 는 넘어온 날 3 공감수 0 댓글수 0 2020. 9. 14.
# 2688 줄어들지 않아 def no_reduce(n): dp = [ [0]*10 for _ in range(n) ] dp[0] = [1]*10 for i in range(1,n): #dp[i][0] = dp[i-1][0] for j in range(0,10): for k in range(j+1): dp[i][j] += dp[i-1][k] print(sum(dp[n-1])) t = int(input()) data = [0]*t for i in range(t): data[i] = int(input()) for i in data: no_reduce(i) 1 자리 인 경우 0~9 까지 1개씩 가능함. -> dp[0] = [1]*10 2 자리 이상인 경우, 1자리 작은 경우의 수에서, 나보다 작거나 같은 수가 나오는 경우 만큼 내가 나.. 공감수 0 댓글수 0 2020. 9. 14.
# 9656 돌 게임 2 n = int(input()) if n % 2 == 1 : print("CY") else : print("SK") SK : n-1, n-3, n-5, n-7 ... CY : n-2, n-4, n-6, n-8 ... 내가 가져가서 돌이 0개 ( 이하 ) 가 되면 진다. SK 는 무조건 n 에서 홀 수 개의 돌을 뺀 만큼을 CY 에게 줄 수 있고 이로써 CY 는 항상 짝수의 값을 받아 SK 에게 홀수 로 돌려 준다. ( 홀수 - 홀수 = 짝수, 짝수 - 홀수 = 홀수 ) 따라서 n 이 짝수이면 SK가 이기고 ( CY 가 n-2k 해서 결국 마지막 돌을 가져감 ) n 이 홀수이면 CY가 이긴다. 공감수 0 댓글수 0 2020. 9. 14.
# 11055 가장 큰 증가 부분 수열 # 틀린 코드 n = int(input()) data = list(map(int,input().split())) dp = [ 0 for _ in range(n)] dp[0] = data[0] for i in range(n): max_sum = 0 for j in range(0,i): if max_sum data[j]: max_sum += data[j] dp[i] = max_sum + data[i] print( max(dp)) # 정답 n = int(input()) data = list(map(int,input().split())) dp = [ x for x in data] for i in range(n): for j in range(i): if data[i] > da.. 공감수 0 댓글수 0 2020. 9. 14.
# 1699 제곱수의 합 - # 시간 초과 n = int(input()) # 1 i: break dp[i] = min(dp[i], dp[i - j * j] + 1) print( dp[n]) # min 함수 사용 하지 말고 if 문 적용하기 n = int(input()) dp = [0] * (n+1) for i in range(1, n+1): dp[i] = i for j in range(1, i): if (j * j) > i: break dp[i] = min(dp[i], dp[i - j * j] + 1) print( dp[n]) .. 뭔가 비슷하게는 푸는 것 같은데 조금씩 어긋나는 기분.. 좀 더 생각하고 코딩하기.. 공감수 0 댓글수 0 2020. 9. 13.
# 2293 동전 1 # 틀린 코드.. 왜? n, k = map(int,input().split()) # n 개의 동전, k 원 coin = [0]*n for i in range(n): coin[i] = int(input()) dp = [10001]*(k+1) dp[0] = 1 for i in coin : for j in range(i, k+1): if dp[j-i] != 10001 : if dp[j] == 10001 : dp[j]= 0 dp[j] += dp[j-i] print(dp[k]) # 정답 n, k = map(int,input().split()) # n 개의 동전, k 원 coin = [0]*n for i in range(n): coin[i] = int(input()) dp = [0]*(k+1) dp[0]=1 for.. 공감수 0 댓글수 0 2020. 9. 13.
# 11057 오르막 수 n = int(input()) # 오르막 수 공감수 0 댓글수 0 2020. 9. 13.
# 1010 다리 놓기 t = int(input()) n = [0]*t m = [0]*t for i in range(t): n[i],m[i] = map(int,input().split()) for i in range(t): dp = [0]* n[i] dp[0] = m[i] for j in range(1,n[i]): dp[j] = dp[j-1]*(m[i]-j)//(j+1) print(dp[n[i]-1]) 공감수 0 댓글수 0 2020. 9. 13.
# 11052 카드 구매하기 - n = int(input()) # 사려는 카드의 개수 data = [0]+list(map(int,input().split())) # n 개를 사기 위해 가장 돈을 많이 내는 경우의 수.. dp = [0]*(n+1) dp[1] = data[1] for i in range(2,n+1): for j in range(1,i+1): if dp[i] < dp[i-j] + data[j]: dp[i] = dp[i-j]+ data[j] print(dp[n]) 공감수 0 댓글수 0 2020. 9. 13.
# 14501 퇴사 기본 식 : dp[i] = MAX(P[i] + dp[i+T[i]], dp[i+1]) n = int(input()) t = [0 for _ in range(n)] p = [0 for _ in range(n)] for i in range(n): t[i],p[i] = map(int,input().split()) dp = [0 for _ in range(n)] if t[n-1] == 1 : dp[n-1] = p[n-1] for i in range(n-2, -1, -1): day = i + t[i] if day == n : # 더 이상의 상담은 없음. dp[i]= max(p[i], dp[i+1]) elif day n : .. 공감수 0 댓글수 0 2020. 9. 13.
# 9461 파도반 수열 t = int(input()) n = [] for i in range(t): n.append(int(input())) data= [0]*101 data[0]=1 data[1]=1 data[2]=1 data[3]=2 data[4]=2 for i in range( 5, max(n)+1): if data[i] == 0: data[i] = data[i-1]+data[i-5] for i in n: print(data[i-1]) 공감수 0 댓글수 0 2020. 9. 12.
# 11727 타일링 2 n = int(input()) data=[0]*1001 data[1]=1 if n > 1: data[2]=3 for i in range(3,n+1): data[i]= data[i-2]*2+data[i-1] print(data[n]% 10007) 공감수 0 댓글수 0 2020. 9. 12.
# 10844 쉬운 계단 수 n = int(input()) # 1 공감수 0 댓글수 0 2020. 9. 11.
# 11053 가장 긴 증가하는 부분수열 (개념) n = int(input()) data = list(map(int,input().split())) m = [1]*n for i in range(n): for j in range(i): if data[j] < data[i]: m[i] = max( m[j]+1, m[i]) print(max(m)) - 점화식 헷갈리면 외워두기 - 만약 나보다 전 인덱스에 나보다 작은 값이 있다면, 그 값을 포함하는 것과 현재 값 중 큰 값 고르기 # 다른 폴이 n = int(input()) answer = list(map(int, input().split())) dp = [0] * n for i in range(0, n): if i == 0 : dp[i] = 1 else : max_dp = 0 for j in range(0,.. 공감수 0 댓글수 0 2020. 9. 11.
# 1912 연속합 n = int(input()) data = list(map(int,input().split())) result = [0]*n result[0] = data[0] tmp=data[0] for i in range(1,n): tmp= tmp+data[i] if tmp 공감수 0 댓글수 0 2020. 9. 11.
# 2748 피보나치 수2 # 런타임 에러 n = int(input()) # n 공감수 0 댓글수 0 2020. 9. 11.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.