본문 바로가기

Problem Solving/BOJ - Python

 (23)
[Python | 파이썬] 백준 17142 연구소3 [Python | 파이썬] 백준 17142 연구소3 이 문제는 itertools의 combinations을 이용해서 풀 수도 있지만 삼성 sw역량테스트에서는 itertools를 사용할 수 없는 경우가 있어서 저는 dfs를 이용해서 풀었습니다. 시간 제한을 해결하는 게 조금 어려운 문제였습니다. 1. 우선 virus는 2 => -2, 벽은 1 => -1로 변경하여 maps배열에서 최대시간을 계산하는 데 헷갈리지 않도록 구현하였습니다. 2. virus는 virus배열에 x, y를 넣어 추가하고 이후에 dfs에서 이 virus 배열을 이용하여 활성화시킬 바이러스가 m개가 되었을 때 바이러스를 퍼뜨리기 시작합니다. 3. 바이러스가 상하좌우로 도달한 위치에 있는 원소가 벽이 아니라면 이 위치에서 바이러스가 다시 ..
[Python | 파이썬] 백준 파일 합치기 11066 [Python | 파이썬] 백준 파일 합치기 11066 참고한 블로그 : https://inspirit941.tistory.com/254 더보기 # import sys INF = int(1e9) # input = sys.stdin.readline tc = int(input().rstrip()) for t in range(tc): n = int(input().rstrip()) arr = list(map(int, input().rstrip().split())) cumsum = {-1:0} for i in range(len(arr)): cumsum[i] = cumsum[i-1] + arr[i] dp = [[0 for _ in range(len(arr))] for _ in range(len(arr))] for ..
[Python | 파이썬] 백준 계단 오르기 2579 [Python | 파이썬] 백준 계단 오르기 2579 각 계단을 밟을때의 최대값을 dp배열에 저장한다. 이때 연속된 3개의 계단을 밟을 수 없다. 더보기 import sys input = sys.stdin.readline n = int(input()) step = [] for i in range(n): step.append(int(input())) dp = [] # 계단의 갯수가 1개,2개일 때를 생각해서 dp.append(step[0]) if n > 2: dp.append(max(step[0] + step[1], step[1])) dp.append(max(step[0] + step[2], step[1]+step[2])) for k in range(3, n): dp.append(max(dp[k-2]+st..
[Python | 파이썬] 백준 10844 쉬운 계단 수 [Python | 파이썬] 백준 10844 쉬운 계단 수 마지막 글자가 0부터 9까지 존재할 수 있으므로 이를 각 열로 하고 각 행은 0~n까지로 하는 배열 dp를 선언한다. 한 자릿수는 모두 1로 초기화한다. (i == 1) 두자리 이상의 수는 만약 맨 뒤에 글자가 0이라면 뒤에서 두번째 글자는 반드시 1이 와야 한다. 따라서 길이가 i-1이고 마지막 글자가 1인 dp[i-1][1]의 값으로 갱신한다. dp[i][0] = dp[i-1][1] 맨 뒤의 글자가 9인 경우에도 뒤에서 두번째 글자는 반드시 8이 와야 한다. 따라서 길이가 i-1이고 마지막 글자가 8인 dp[i-1][8]의 값으로 갱신한다. dp[i][9] = dp[i-1][8] 0과 9 이외에는 마지막에서 두번째에 올 수 있는 수는 마지막 수..
[Python | 파이썬] 백준 11053 가장 긴 증가하는 부분 수열 [Python | 파이썬] 백준 11053 가장 긴 증가하는 부분 수열 모든 인덱스에 대해 처음에는 자기자신 1개를 원소로 갖는 부분 수열의 길이 1을 최대 lcs의 길이로 한다. 그리고 0부터 각 인덱스-1까지 j를 증가하며 인덱스 j의 원소가 i번째 원소보다 작다면 dp[i] = max(dp[i], dp[j]+1) 로 초기화한다. 더보기 n = int(input()) arr = list(map(int, input().split())) dp = [1] * n for i in range(1, n): for j in range(i): if arr[i] > arr[j]: dp[i] = max(dp[i], dp[j]+1) print(max(dp)) https://www.acmicpc.net/problem/11..
[Python | 파이썬] 백준 11054 가장 긴 바이토닉 부분 수열 [Python | 파이썬] 백준 11054 가장 긴 바이토닉 부분 수열 이 문제는 앞에서부터 증가하는 부분 수열의 최대 길이를 구하고, 뒤에서부터 증가하는 부분 수열의 최대 길이를 구하여 각각 dp와 r_dp 배열에 저장한다. 예를 들어 1 2 3 5 4 2 1 배열에서 1,2,3,5 로 증가하는 부분 수열의 길이인 dp[3] = 4 5,4,2,1로 감소하는 부분 수열의 길이인 r_dp[7-1-3] = 4 의 합이 가장 크다. 이때 5는 반복되므로 4 + 4 - 1을 해줬을때 1, 2, 3, 5, 4, 2, 1로 전체 배열의 길이가 최대가 된다. 주의할 점은 dp와 r_dp의 합을 구할 때 같은 인덱스에 대해서 합을 계산해야 하므로, reversed된 배열인 r_d는 0부터 n-1까지 증가하는 인덱스 i..
[Python | 파이썬] 백준 12865 평범한 배낭 [Python | 파이썬] 백준 12865 평범한 배낭 배낭문제는 물건의 무게를 저장하는 배열 weight와 가치를 저장하는 배열 value를 각각 준비한다. 최대 담을 수 있는 무게가 k이고 물건의 개수가 n이라고 한다. dp배열은 행의 수를 각 물건의 개수 + 1으로 하고 열의 수를 배낭이 담을 수 있는 최대 무게 + 1로 한다. 만약 물건이 무게와 가치가 3, 10이라면 아래와 같다. 1 < 3, 2< 3이므로 dp[i][j] = dp[i-1][j]인 0이 된다. 3
[Python | 파이썬] 백준 1912 연속합 [Python | 파이썬] 백준 1912 연속합 이 문제는 현재까지 누적된 값의 최대값을 저장해두는 배열 sumarr을 준비하고, 만약 sumarr에 가장 최근에 저장된 값에 현재 인덱스에 해당하는 값을 추가한 값이 더 크다면 sumarr에 그 누적합을 저장하고, 그렇지 않다면 현재 인덱스에 해당하는 값 자체를 저장한다. 즉 현재값이 현재 값을 포함해 누적된 값의 합보다 크다면 현재값부터 누적합을 다시 세기 시작하는 것이다. sumarr[i+1] = max(sumarr[i] + arr[i+1], arr[i+1]) 이 된다. 더보기 n = int(input()) arr = list(map(int, input().split())) sumarr = [arr[0]] for i in range(n-1): suma..

티스토리툴바