SW개발/코딩테스트

    [백준]1912번 연속합 - DP
    SW개발/코딩테스트

    [백준]1912번 연속합 - DP

    n = int(input()) num = list(map(int, input().split())) dp = [0] * n dp[0] = num[0] for i in range(1, n): dp[i] = max(dp[i - 1] + num[i], num[i]) # 직전수+현재수와 현재수를 비교해 큰것을 저장 print(max(dp)) 코드 설명 먼저 n이 1인 경우를 대비해 dp[0]에는 num[0] 값을 넣어준다. 반복문을 통해 직전수+현재수 vs 현재수 중 큰 값을 저장시키면서 반복한다. 저장된 값중 가장 큰 값을 출력하면 연속합중 가장 큰 값을 구할 수 있다. Point : 큰 값을 저장시키기 위해서 직전까지 누적된 합과 현재의 수를 비교하여 큰 것을 저장한다. 이 과정을 진행하는 이유는 직전까지의 ..

    [백준]9251번 LCS - DP
    SW개발/코딩테스트

    [백준]9251번 LCS - DP

    string1 = "0" + input() string2 = "0" + input() dp = [[0] * len(string1) for i in range(len(string2))] for i in range(1, len(string2)): # 두번째 문자열을 한 개씩 반복하기 위해 for j in range(1, len(string1)): if string2[i] == string1[j]: # 만약 같은 문자인 경우 dp[i][j] = dp[i - 1][j - 1] + 1 # BG G -> BGC GC 가 된 경우 "C" 라는 값이 동일하게 들어온 것. # 따라서 대각선 왼쪽의 기억되어있는 값 + 1 else: # 다른 문자인 경우 dp[i][j] = max(dp[i - 1][j], dp[i][j -..

    [백준]2565번 전깃줄 - DP
    SW개발/코딩테스트

    [백준]2565번 전깃줄 - DP

    n = int(input()) line = [[0] * 2 for i in range(n)] for i in range(n): line[i][0], line[i][1] = map(int, input().split()) line.sort(key=lambda x: x[0]) length = [0] * n for i in range(n): length[i] = 1 for j in range(i): if line[j][1] < line[i][1]: length[i] = max(length[i], length[j] + 1) print(n-max(length)) 코드 설명 먼저 전깃줄의 이어진 정보를 line 이차원 리스트에 저장한다. 그 후 한쪽의 전봇대를 기준으로 번호를 정렬하여 준다. n 번의 반복문을 진행하..

    [백준]11054번 가장 긴 바이토닉 부분 수열 - DP
    SW개발/코딩테스트

    [백준]11054번 가장 긴 바이토닉 부분 수열 - DP

    n = int(input()) num = list(map(int, input().split())) dp1 = [0] * n dp2 = [0] * n for i in range(n): dp1[i] = 1 for j in range(i): if num[j] < num[i]: dp1[i] = max(dp1[i], dp1[j] + 1) num.reverse() for i in range(n): dp2[i] = 1 for j in range(i): if num[j] < num[i]: dp2[i] = max(dp2[i], dp2[j] + 1) dp2.reverse() ans = [0] * n for i in range(n): ans[i] = dp1[i] + dp2[i] - 1 print(max(ans)) 코드 설명..

    [백준]11053번 가장 긴 증가하는 부분 수열 - DP
    SW개발/코딩테스트

    [백준]11053번 가장 긴 증가하는 부분 수열 - DP

    n = int(input()) num = list(map(int, input().split())) length = [0] * n for i in range(n): length[i] = 1 for j in range(i): if num[j] < num[i]: length[i] = max(length[i], length[j] + 1) print(max(length)) 코드 설명 LIS 알고리즘을 구현하는 문제이다. 부분 수열의 길이를 저장하는 length 리스트를 [0] * n 의 길이만큼 초기화 한다. 반복문 안에서 기본길이는 1로 만들어 준다. i 번째 전에 존재하는 값들 중에 i 번째의 값보다 큰 수가 존재할 경우에는 현재 i 번째의 수열 길이와 j + 1 의 수열 길이중 큰 값으로 업데이트한다. le..

    [백준]2156번 포도주 시식 - DP
    SW개발/코딩테스트

    [백준]2156번 포도주 시식 - DP

    n = int(input()) grape = [0] * (n+2) dp = [0] * (n+2) for i in range(n): grape[i]= int(input()) dp[0] = grape[0] dp[1] = grape[0]+grape[1] dp[2] = max(grape[0]+grape[1], grape[0]+grape[2], grape[1]+grape[2]) # 포도주가 3개일 경우에서 최대 값. for i in range(3, n): dp[i] = max(dp[i-2]+grape[i], dp[i-3]+grape[i-1]+grape[i], dp[i-1]) # 포도주를 마시지 않는 경우 까지 고려. print(max(dp)) 코드 설명 먼저 인덱스의 에러를 피하기 위해 n+2 길이 만큼의 gra..

    [백준]10844번 쉬운 계단 수 - DP
    SW개발/코딩테스트

    [백준]10844번 쉬운 계단 수 - DP

    n = int(input()) dp = [[0] * 10 for i in range(n)] # 0~9의 인덱스를 가지고, n의 자릿수를 가진 이중 리스트 초기화. dp[0] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1] # 한자리 숫자일 때 미리 초기화. for i in range(1, n): for j in range(10): if j == 0: # 0이면 전 자릿수의 j+1 만 더함 dp[i][j] = dp[i - 1][j + 1] elif j == 9: # 9 이면 전 자릿수의 j-1 만 더함 dp[i][j] = dp[i - 1][j - 1] else: # 1~8 은 전 자릿수의 j-1, j+1 이 올 수 있으므로 두개를 더함 dp[i][j] = dp[i - 1][j - 1] + dp[..

    [백준]1463번 1로 만들기 - DP
    SW개발/코딩테스트

    [백준]1463번 1로 만들기 - DP

    n = int(input()) dp = [0] * (n + 1) for i in range(2, n + 1): dp[i] = dp[i - 1] + 1 # 1로 구하는 경우. if i % 3 == 0: # 3으로 구하는 경우. dp[i] = min(dp[i], dp[i // 3] + 1) if i % 2 == 0: # 2로 구하는 경우. dp[i] = min(dp[i], dp[i // 2] + 1) print(dp[-1]) 코드 설명 n+1 만큼의 길이를 가진 dp 리스트를 생성함으로써 index 를 문제와 맞춰준다.(0 인덱스 사용 X) 값이 1을 입력 받는 경우에는 연산의 횟수가 0 이므로 반복문을 수행하지 않고 그냥 출력하게 한다. 값이 2이상인 경우에는 2 부터 n 까지 반복을 진행한다. 1을 빼는..

    [백준]2579번 계단 오르기 - DP
    SW개발/코딩테스트

    [백준]2579번 계단 오르기 - DP

    n = int(input()) stair = [0 for i in range(301)] # 계단의 최대 수 300 개 point = [0 for i in range(301)] # 계단이 3개 이하일 경우, 인덱스 에러를 방지하기 위해 0으로 초기 for i in range(n): stair[i] = int(input()) point[0] = stair[0] point[1] = stair[0] + stair[1] point[2] = max(stair[0] + stair[2], stair[1] + stair[2]) # 무조건 3번째 계단을 밟아야 하므로 0,2 와 1,2 중 큰거로 저장 for i in range(3, n): # 2칸 올라온 경우 전 계단은 신경 안씀, 1칸만 올라온 경우 연속 3칸 올라오지..

    [백준]1932번 정수 삼각형 - DP
    SW개발/코딩테스트

    [백준]1932번 정수 삼각형 - DP

    n = int(input()) num = [] for i in range(n): num.append(list(map(int, input().split()))) for i in range(n-1, 0, -1): for j in range(len(num[i-1])): num[i-1][j] += max(num[i][j], num[i][j+1]) print(num[0][0]) 코드 설명 먼저 주어진 삼각형 모양의 수를 입력을 받는다. 삼각형의 아래부분 부터 반복문을 시작한다. 내부 반복문은 층의 수만큼 반복한다. 위층에 있는 수와 아래 층의 왼쪽, 오른쪽의 수에서 더한 값이 큰 값을 선택한다. 끝까지 반복하면 num[0][0] 리스트에 가장 큰 값이 저장되어 있다. Point : 아래부터 시작하여 위로 가는 b..

티스토리툴바