본문 바로가기

프로그래밍

 (187)
백준 1912 연속합 - 파이썬 문제. 풀이. dp[0]에 arr[0]의 값을 넣어준 뒤 연속으로 더하는게 더 큰 숫자면 더한 값을 dp에 넣어주고 더하지 않고 새로운 숫자를 넣어주는게 값이 더 크다면 그 값을 dp에 넣어주는 방식으로 계속 진행을 한다. 그리고 dp에서 제일 큰 값을 출력한다. 소스코드. import sys n = int(sys.stdin.readline()) arr = list(map(int, sys.stdin.readline().split())) dp = [arr[0]] for i in range(n-1): dp.append(max(dp[i] + arr[i+1], arr[i+1])) print(max(dp))
백준 2565 전깃줄 - 파이썬 문제. 풀이. 2차원 배열로 입력을 받고 A또는 B 기준으로 정렬을 하고 A 기준으로 정렬을 했다면 B에 대하여 LIS를 구하여서 n 값에서 LIS를 빼면 된다. B 기준으로 정렬을 했다면 A에 대하여 LIS를 구하고 n 값에서 LIST를 뺀다. 소스코드. import sys n = int(sys.stdin.readline()) wire = [] dp= [0] * n for i in range(n): A, B = map(int, sys.stdin.readline().split()) wire.append([A, B]) wire = sorted(wire, key = lambda x: x[0]) for i in range(n): for j in range(i): if wire[i][1] > wire[j][1]..
백준 11054 가장 긴 바이토닉 부분 수열 - 파이썬 문제 풀이. 저번에 포스트 했던 LIS를 구하는 알고리즘을 응용한 문제이다. 앞에서 부터 구한 LIS와 뒤에서 부터 구한 LIS를 더해서 최댓값을 출력하면 된다. 단 두개를 더하고 숫자 하나는 겹치기 때문에 -1을 해줘야한다. 소스코드. import sys A = int(sys.stdin.readline()) seq = list(map(int, sys.stdin.readline().split())) dp1 = [0] * A dp2 = [0] * A result = [0] * A for i in range(A): for j in range(i): if seq[i] > seq[j] and dp1[i] < dp1[j]: dp1[i] = dp1[j] dp1[i] += 1 result[i] += dp1[i] fo..
백준 11053 - 가장 긴 증가하는 부분 수열 문제. 풀이. 첫번째 위치부터 수열의 길이의 최댓값을 저장하고 자기 자신보다 작은 숫자들 중 가장 큰 길이를 자기 위치에 넣고 +1을 하고 dp의 최댓값을 출력하면 된다. 소스코드. import sys A = int(sys.stdin.readline()) seq = list(map(int, sys.stdin.readline().split())) dp = [0] * A for i in range(A): for j in range(i): if seq[i] > seq[j] and dp[i] < dp[j]: dp[i] = dp[j] dp[i] += 1 print(max(dp))
백준 2156 포도주 시식 - 파이썬 문제. 풀이. 풀이 방법이 DP문제의 계단 오르기랑 많이 유사하다. 마지막을 번호를 기준으로 구해야하는 경우의 수는 총 3가지다. 예를 들어 1 2 3 4 가 있다면 마지막 4번을 기준으로 나올 수 있는 경우의 수는 (1, 2, 4), (1, 3, 4), (2, 3) 즉 마지막잔을 마신다면 그 이전 잔을 마시냐 안마시냐와 마지막잔을 안마시는 경우 이렇게 총 3가지로 나뉘어서 소스코드를 작성하면 된다. 소스코드. import sys n = int(sys.stdin.readline()) drink = [0] * 10000 dp = [0] * 10000 for i in range(n): drink[i] = int(sys.stdin.readline()) dp[0] = drink[0] dp[1] = drink[0..
백준 11444 피보나치 수 6 - 파이썬 문제. 풀이. 피보나치를 행렬의 거듭제곱으로 풀 수 있다는 사실을 몰랐었는데 이번 문제를 풀면서 알게되었다. 피보나치를 그냥 계산하면 시간 복잡도가 O(n)을 가지지만 행렬의 거듭제곱을 이용하면 O(logn)의 시간 복잡도를 가지게 된다. 식은 다음과 같다. 소스코드. import sys def Square(b): if b == 1: return matrix temp = Square(b // 2) if b % 2 == 0: result = matrix_multiple(temp,temp) return result elif b % 2 == 1: result = matrix_multiple(temp,temp) result = matrix_multiple(result, matrix) return result #..
백준 11401 이항 계수 3 - 파이썬 문제. 풀이. 페르마의 소정리를 이용하여 풀었다. 유클리드 확장법을 통하여서도 풀 수 있다고 한다. 우선 문제를보면 1,000,000,007은 소수이다. 페르마의 소정리는 p가 소수이고 a가 p의 배수가 아니면 a^(p-1) = 1 mod p 이다 더 자세한 내용은 https://www.acmicpc.net/board/view/15795 해당 링크를 참조해서 보면 될 것 같다. 소스코드. import sys def div_con(n, p): prime = 1000000007 if p == 0: return 1 temp = div_con(n, p//2) if p % 2 == 0: return (temp * temp) % prime elif p % 2 == 1: return (temp * temp * n) ..
백준 10830 행렬 제곱 - 파이썬 문제. 풀이. 분할정복의 제곱거듭 공식과 행렬의 공식을 합쳐서 풀면 된다. 지수가 짝 수이면 n^(지수/2) * n^(지수/2), 지수가 홀 수 이면 n^(지수/2) * n^(지수/2) * n 이런 방식으로 풀면 된다. 소스코드. import sys def Square(b): if b == 1: return matrix temp = Square(b // 2) if b % 2 == 0: result = matrix_multiple(temp,temp) return result elif b % 2 == 1: result = matrix_multiple(temp,temp) result = matrix_multiple(result, matrix) return result # 행렬 곱 def matrix_multi..

티스토리툴바