Dev_Diary

https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 전형적인 그리디 알고리즘 문제로 큰 동전부터 차례로 빼나가면 쉽게 풀 수 있습니다. def solution(N, K, data_list): # 거꾸로 탐색하기 위해 리버스 data_list = sorted(data_list, reverse=True) # 동전의 수 coin_num = 0 # 값이 큰 동전부터 탐색 for val in ..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 경우의 수를 나누어 DP 배열을 채워갈 수 있다면 쉽게 풀 수 있습니다. def solution(N): # DP # 열은 자릿수 # 행은 자릿수에 들어가는 숫자 memo = [[0 for _ in range(N+1)] for _ in range(10)] # 1자리는 0 빼고 다 1 이니까 채워주기 for i in range(1, 10): memo[i][1] = 1 # n+1 번째 자리에서 n 번째 자리를 고려하면 # n+1 번째 자리가 0일 경우 2 한 가지 # n+1 번째 자리가 9일경우 8 한 가지 # 나머..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 일이 끝나는 날부터 마지막 날 까지 모든 날을 채워가며 업데이트 해야하는 점이 냅색 알고리즘(배낭문제) 와 비슷했습니다. 이 점만 생각하면 쉽게 풀 수 있습니다. def solution(N, data_list): # DP memo = [0 for _ in range(N+1)] # 일의 번호, data_list 인덱스 for work in range(N): # n 번째 시작한 일이 끝나는 날 end_day = work + data_list[work][0] # 퇴사하기 전에 끝날 경우에만 if end_day

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net https://dev-diary-0717.tistory.com/34 백준 11055 https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가하는 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, ..

https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 그림을 보며 규칙을 알아내기만 하면 쉽게 풀 수 있습니다. def solution(T, data_list): # 데이터 리스트 중 최댓값 max_list = max(data_list) # DP memo = [0 for _ in range(101)] # 앞부분 채우기 memo[0:6] = [1, 1, 1, 1, 2, 2] i = 6 while True: # 중단조건 if i == max_list + 1:..

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 처음에는 누적합 알고리즘으로 풀이를 시도했다가 시간이 부족해서 다른 방식으로 접근했습니다. DP 를 두 갈래로 나누어 썼는데, 현재 인덱스를 포함하는 최댓값을 기록하는 리스트와 그냥 최댓값을 기록하는 리스트 두 가지를 나누어 최댓값 리스트가 현재 인덱스를 포함하는 리스트를 비교하며 최댓값을 최신화하게 설계했습니다. def solution(n, data_list): # 인덱스 맞춰주기 data_list = [..

https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가하는 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 www.acmicpc.net 전형적인 LIS 알고리즘 문제입니다. 문제 시간이 넉넉해 DP 를 사용해 풀어주면 됩니다. 기본 아이디어는 현재 인덱스에서 거꾸로 인덱스를 줄여가며 현재 값보다 작은 값이 있다면 수열의 수를 더해주는 방식을 취했습니다. def solution(n, data_list): # 인덱스 맞춰주기 data_list = [0] + data_list..

https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 경우의 수를 나누는 기준만 잘 세우면 쉽게 풀 수 있는 문제입니다. def solution(n): # DP memo = [0 for _ in range(91)] # 앞 부분 미리 작성 memo[1] = 1 memo[2] = 1 i = 3 while True: # 중단 조건 if i >= n+1: return memo[n] # 맨 앞은 10 으로 고정되어 있음 # 그 뒤를 생각해야 하는데..

https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net https://dev-diary-0717.tistory.com/26 BaekJoon 11726 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방 dev-diary-0717.tistory.com 2xn 타일링 문제의 연장선상에 있는..

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 전형적인 DB 문제입니다. 위에서부터 아래로 점점 더해가며 비교하면 쉽게 풀 수 있습니다. def solution(n, data_list): # DP memo = [[0]*(i+1) for i in range(len(data_list))] # 최상단 채워주기 memo[0][0] = data_list[0][0] # 아래로 내려가면서 더함 # n 층에서 n+1 층으로 더함 for i in range(n-1): for j in range(len(data_list[i])): ..